ebook img

NASA Technical Reports Server (NTRS) 20030034662: Decision-Theoretic Control of Planetary Rovers PDF

19 Pages·1.1 MB·English
Save to my drive
Quick download
Download
Most books are stored in the elastic cloud where traffic is expensive. For this reason, we have a limit on daily download.

Preview NASA Technical Reports Server (NTRS) 20030034662: Decision-Theoretic Control of Planetary Rovers

Decision-Theoretic Control of Planetary Rovers Shlomo Zilbersteinl. Richard Washington2, Daniel S. Bernstein', and Abdel-Illah Mouaddib3 Univ. of Massachusetts, Dept. of Computer Science, Amherst, MA 01003, USA RIACS, NASA Ames Research Center, MS 269-3, Moffett Field, CA 94035, USA Laboratoire GREYC, UniversitC de Caen, F14032 Caen Cedex, FRANCE Abstract. Planetary rovers are small unmanned vehicles equipped with cameras and a variety of sensors used for scientific experiments. They must operate under tight constraints over such resources as operation time, power, storage capacity, and communication bandwidth. Moreover, the limited computational resources of the rover limit the complexity of on-line planning and scheduling. We de- scribe two decision-theoretic approaches to maximize the productivity of plane- tary rovers: one based on adaptive planning and the other on hierarchical rein- forcement learning. Both approaches map the problem into a Markov decision problem and attempt to solve a large part of the problem off-line, exploiting the structure of the plan and independence between plan components. We examine the advantages and limitations of these techniques and their scalability. 1 Towards Autonomous Planetary Rovers The power of a mobile platform to perform science and explore the surface of distant planetary surfaces has long attracted the attention of the space exploration community. Unmanned rovers have been deployed on the Moon and on Mars, and they have been proposed for exploring other planets, moons, and small bodies such as asteroids and comets. The challenges and goals of planetary exploration pose unique constraints on the control of rovers, constraints that differentiate this domain from others that have traditionally been considered in mobile robotics. In addition, operation of a rover on a planetary surface differs significantly from operation of other distant spacecraft. In this paper, we describe the problem of rover control and illustrate its unique as- pects. We show how these characteristics have led us to consider utility as a fundamental concept underlying planetary exploration; this in turn directed our attention and effort to decision-theoretic approaches for planetary rover control. We will survey these ap- proaches, particularly concentrating on two methods: one based on adaptive planning and the other on hierarchical reinforcement learning. A planetary rover is first and foremost a science tool, carrying a suite of instruments to characterize a distant environment and to transmit information to Earth. These instru- ments may include cameras, spectrometers, manipulators, and sampling devices. Under some level of control from Earth-bound scientists and engineers, the rover deploys the instruments to gain information about the planetary surface. For example, in the Mars Smart Lander mission, currently planned for 2009, a rover will traverse a few kilome- ters between scientifically interesting sites. At each site, the rover will visit a number of targets (typically rocks) and deploy instruments on each one. In the current mission scenario, the targets and rover actions will be completely specified by scientists and rover engineers. The work presented in this paper would enable the rover to perform many of these steps autonomously. The level of success of a rover mission is measured by the “science return,” or amount of useful scientific data returned to the scientists on Earth. Although it is diffi- cult to measure concretely, some attempts have been made to characterize it precisely for particular scenarios [30]. Criteria such as rover safety, navigation accuracy and speed, data compression ratios, and resource management contribute to science return. An important characteristic of using science return as a mission success criterion is that it is a quantity to be maximized, not a discrete goal to be achieved. This differs markedly from traditional applications of planning technology to mobile robotics. From the early days of planning, applications to robotics have typically concentrated on achieving dis- crete goals [ 18, 15,281. More recently, decision-theoretic planning has extended beyond all-or-none goals to handle overall reward [21,29], offering a more suitable framework for planetary rover control. Autonomous control of rovers on distant planets is necessary because the round- trip time for communication makes tele-operation infeasible. Many earth-based rovers, as well as lunar rovers to a certain extent, can be controlled via tele-operation, using advanced user interfaces to compensate for latency in communication links [ 11,1]. For Martian or other distant planetary exploration, the latency increases beyond the limits of tele-operation. In addition, because of constraints on communication resources and cost, currently envisioned missions will limit communications to once or twice daily. Between these communication opportunities, the rover must operate autonomously. An important and distinctive feature of planetary robotics, and a challenge for au- tonomous operations, is uncertainty. With planetary rovers, there is uncertainty about many aspects of sequence execution: exactly how long operations will take, how much power will be consumed, and how much data storage will be needed. Resources such as power and data storage are critical limits to rover operations; resource limits must be respected, but unused resources generally translate to wasted mission time and thus decreased productivity. Furthermore, there is uncertainty about environmental factors that influence such things as rate of battery charging or which scientific tasks are possi- ble. In order to allow for both sources of uncertainty, a traditional spacecraft command plan is conservative: only limited operations are allowed within a single uplink, time and resource usage are based on worst-case estimates, and the plan contains fail-safe checks to avoid resource overruns. If an operation takes less time than expected, the rover waits until the time prescribed for the next operation. If an operation takes longer than expected, it may be terminated before completion; in some cases, all non-essential operations may be halted until a new command plan is received. These situations result in unnecessary delays and lost science opportunities. An example is the Mars Smart Lander mission, where the rover will visit at most one target in a single uplink, and in fact the rover will only approach a target and place an instrument before waiting for the next command plan [22]. Although conservative, this is still an advance over previous rovers (Sojourner [23] or the 2003 Mars Explo- ration Rovers), which required multiple days to accomplish as much. The techniques t Fig. 1. Increasing levels of capability for planetary rovers. described in this paper provide the rover with the ability to select and balance tasks across multiple targets, allowing more ambitious exploration. The highly uncertain operational environment distinguishes rover control from other spacecraft control. A deep space probe works in a harsh but stable environment, and its actions have relatively predictable effects, barring anomalies. Planning procedures de- signed for spacecraft [25,17] do not explicitly handle all the types of uncertainty; appli- cations of these technologies to the problem of rover control [ 141 rely on the presence of planners on board to replan when execution diverges from a single nominal plan. The computational power of planetary rovers is also severely limited by the use of radiation-hardened, low-power processors and electronics. Increases in processor per- formance are more than made up for by the desire for increased on-board processing of images and science data, as well as improved navigation. In addition, the processor is a draw on the overall power budget. Thus control approaches that minimize on-board computation are preferable. Constrained by action and environmental uncertainty, and limited computational resources, our objective is to increase the science productivity possible within a single uplink. To this end, we are pursuing a program of increasing capabilities, illustrated in Figure 1. Starting from the capabilities of the Sojourner rover, which used detailed, time-stamped scripts of low-level commands, we are moving toward autonomous goal selection and ordering. The latter is the main focus of this paper. Before presenting that work, we first review the steps along this spectrum of capabilities. In all past and currently planned missions, the command plans for the rover are completely specified on the ground. In this case, additional flexibility in terms of time and state conditions, as well as contingent branches, may allow a wider range of behav- iors than fixed-time sequences [6]. Additional capability can be realized by calculating utilities of plan branches with respect to the situation at execution time [7]. If we allow limited innovation on board, the rover can adapt its plan to the situation by skipping Fig. 2. The K9 Rover. steps or merging in plan fragments from a plan library constructed and verified on the ground [8]. The capabilities described to this point make use of plans that have been pre- specified to full detail. To specify plans at a higher level of abstraction, such as desired science targets, the decomposition of the high-level tasks into detailed actions must be performed on board in a way that is sensitive to the execution context. Decision- theoretic planning and control methods can perform this dynamic choice to maximize science return. If science targets are considered individually, the problem is a local problem of tusk selection. The control problem in this case is to decide which experiments to perform and when to move to another target [3]. The latter depends on the expected information to be gained from other targets and the difficulty of reaching them. The former depends on the available resources as well as characteristics of the target. Alternatively, we may reason about a group of targets together; in planetary ex- ploration this is often referred to as a site. By considering the activities within a site together, the overall science return can be improved compared to target-specific control policies. It is at this level of capability that we concentrate for the remainder of the paper. The planning and execution techniques described in this paper allow the rover to re-prioritize and reorder scientific activities based on progress made, scientific observa- tions, and the success or failure of past activities. The solution relies on off-line anal- ysis of the problem and on pre-compilation of control policies. In addition, we have Decision-Theorcw Controller ‘v‘ ~_______ Conditional Executive Fig. 3. Layers of rover software in the existing K9 rover software architecture. used the independence between various mission tasks and goals to reduce the com- plexity of the control problem. The rest of the paper is organized as follows. Section 2 sketches the multiple layers of control and the way the decision-theoretic planning component interacts with the lower-levels. The section also provides a general intro- duction to decision-theoretic control and the two approaches we have developed. These approaches, adaptive planning and hierarchical reinforcement learning are detailed in sections 3 and 4. We conclude with a discussion of the merits of these two approaches and future work. 2 Layers of Control The focus of this paper is on high-level, decision-theoretic control. However, the decision- theoretic component does not interact directly with the rover’s actuators. It rests on a number of existing layers of control, which bridge the gap between decision-theoretic plans and the low-level control of the robotic mechanisms. In this section we describe the entire control architecture and the experimental platform for which it has been de- veloped. We are targeting our work for the NASA Ames “K9” rover prototype, pictured in Figure 2. The existing rover software architecture in place on the K9 rover consists of four distinct layers, as shown in Figure 3. Low-level device drivers communicate with hardware. Mid-level component controllers receive simple commands (such as di- rect movement, imaging, and instrument commands) and communicate with the device drivers to effectuate the commands. Abstract commands implement compound or com- plex actions (such as movement with obstacle avoidance, visual servoing to a target, and arm placement). A plan executive interprets command plans and calls both simple and abstract commands as specified in the plan. For more details on this architecture, see [9 1. A high-level, decision-theoretic controller interacts with this architecture by propos- ing high-level actions, potentially more abstract than commands within the architecture. The high-level actions are then decomposed into small command plans; these command plans are provided to the rover plan executive, which in turn manages the execution and monitoring of the low-level commands within the command plans. Information about success of the high-level action and the resulting state of the system is returned to the decision-theoretic controller at the end of execution of each command plan. The rover control problem, at the level that we are addressing, consists of a set of science-related goals. These science goals identify a set of targets, each of which has particular scientific interest. The rover has a set of instruments available, and thus a set of possible experiments, to gather relevant information about the targets. Given the set of targets and desired information, the rover's task is to choose activities that provide the maximum information possible about the targets within resource and time constraints and to return that information to the scientists. 3 Decision-Theoretic Control The high-level control of the rover presents a sequential decision problem under uncer- tainty. At each point, the rover must select the next action based on the current state and the remaining plan. The state in this case includes both features characterizing the environment and features characterizing the rover itself, such as an indication of the remaining resources. Such problems can be modeled as a Markov decision pro- cess (MDP), assuming that each action transforms the current state into one of several possible outcome states with some fixed transition probability. This assumption is also referred to as the Markov assumption. More formally, an MDP is defined by a finite set of states, S; a finite set of possible actions, A; and a transition probability function Pr(s'Is,a ) that indicates the probabil- ity that taking action a E A in state s E S results in a transition to state s' E S. Each transition has an associated reward, R(s,a ),w hich can capture the cost of the action, the value of the outcome, or some combination of both. The objective is to maximize the reward over a finite- or infinite-horizon. In the later case, future reward is typically discounted by a factor of -y', where i is the number of steps. Partially-observable MDPs (or POMDPs) generalize the MDP model by allowing the agent to have only partial in- formation about the state. At the end of each action, the agent can make an observation o E R. A belief function over states can be maintained using Bayesian updating given the observation probability function, Pr(ols, a).( In general, both transition probabili- ties and observation probabilities may also depend on the outcome state.) We limit our discussion in this paper to MDPs, which provide adequate model for high-level rover control. A solution to an MDP can be represented as a mapping from states to actions, + ?r : S A, called a policy. Several dynamic programming algorithms (such as value iteration and policy iteration) have been developed for finding optimal control policies for MDPs [27,31]. It has also been shown that MDPs can be solved using heuristic search by such algorithms as LAO* [ 191. The advantage heuristic search has over dy- namic programming is that, given an initial state, it can find an optimal solution without evaluating the entire state space. Dynamic programming, in contrast, evaluates the en- tire state space, finding a policy for every possible starting state. For problems with large state spaces, heuristic search offers substantial computational savings. One important characteristic of the rover control problem is the explicit modeling of the amount of resources action use. Extensions of MDPs to handle duration of ac- tions have been previously studied. For example, in Semi-Markov Decision processes (SMDPs) actions can have stochastic durations and state transitions are stochastic [27]. In Stochastic Time Dependent Networks (STDNs) actions can have stochastic dura- tions, but state transitions are deterministic [34]. In Time-Dependent MDPs (TMDPs) actions can have stochastic, time-dependent durations and state transitions are stochas- tic [5].T he model we use in this paper have both stochastic state transitions and actions that consume varying levels of resources (not just time). In this sense, the model is a proper extension of the previous ones. While modeling the consumption of resources by actions is not difficult, it increases the state space dramatically. The number of states grow linearly with the number of resource units (which could be large) and exponen- tially with the number of resources. However, resources have additional characteristics that simplify their treatment: all the units of a resource are typically exchangeable, the number of units goes down as they are consumed (unless the resource is renewable), and the amount of resources used by an action typically depends only on the action itself. Therefore, treating resources as just any other component of the state is wasteful. In the following two sections we examine two decision-theoretic techniques that take advantage of the unique characteristics of the rover control problem in order to simplify it. both approaches are based on modeling the rover set of activities as a loosley-coupled MDP. The scientific experiments the rover performs in each location are largely independent, but they share the same resources. The first approach develops a local policy for each activity that takes into account the remaining plan by computing a cost function over resources. By estimating quickly this cost function at run-time, we can avoid solving the entire MDP while producing near-optimal control policies. The second approach is based on a hierarchical reinforcement learning algorithm designed to take advantage of the natural decomposability offered by loosely-coupled MDPs. It maintains two different value functions: a low-level state-action value function de- fined over all state-action pairs and a high-level state value function defined only over “bottleneck” states that bridge the components of the MDP. The two approaches share the ability to accelerate policy construction by exploiting the structure of the MDP, but they offer different advantages and disadvantages. The first approach exploits a model of the domain and allows for off-line policy construction and compact policy representation, both important issues in rover control. The second approach is model free and is particularly suitable for operation in poorly modeled environments or for adaptation of an existing policy to new environments. The next two sections describe the two approaches and examine their characteristics. 4 Adaptive Planning Approach The adaptive planning approach is based on off-line analysis of each possible rover activity and construction of policies for each possible activity using dynamic program- ming. The key question is how to adapt pre-compiled policies at run-time to reflect the dynamic execution state of the plan. The dynamic information includes the remaining workload and the remaining resources, both of which can be captured by the notion of opportunity cost. Each plan assigned to a rover is composed of a sequence of target activities repre- sented as progressive processing task structures [24,35]. An initial resource allocation is also specified. Resources are represented as vectors of discrete units. We assume here that the plan is totally ordered and that resources are not renewable. A generalization of the technique to acyclic graphs has been examined in [lo]. 4.1 The Rover Model The rover can perform a certain set of predefined activities, each of which has an asso- ciated fixed task structure. The task structure is represented as a progressive processing unit (PRU), which is composed of a sequence of steps or processing levels, (11,lz, . . .). Each step, li, is composed of a set of alternative modules, {mi,m f,. . .). Each module of a given step can perform the same logical function, but it has different computa- tional characteristics defined by its descriptor. The module descriptor, P/ ((q’, Ar)Iq), of module mi is the probability distribution of output quality and resource consump- tion for a given input quality. Module descriptors are similar to conditional performance profiles of anytime algorithms. When the rover completes an activity, it receives a reward that depends on the qual- ity of the output and the specific activity. Each PRU has an associated rewardfunction, U(q),t hat measures the immediate reward for performing the activity with overall qual- ity q. Rewards are cumulative over different activities. Given a plan, a library of task structures that specify a PRU for each activity in the plan, the module descriptors of all the components of these PRUs, and corresponding reward functions for each activity, we want to select the best set of alternative modules to maximize the overall utility or scientific return of the rover. 4.2 Optimal Control of a Single Activity We begin with the problem of meta-level control of a single progressive processing unit corresponding to a single activity. This problem can be formulated as a Markov deci- sion process (MDP) with states representing the current state of the activity. The state includes the current level of the PRU, the quality produced so far, and the remaining resources. The rewards are defined by the utility of the solution. The possible actions are to execute one of the modules of the next processing level. The transition model is defined by the descriptor of the module selected for execution. State transition model. The execution of a single progressive processing unit can be seen as an MDP with a finite set of states S = {[l,,q,r]}w, here i indicates the last executed level, q is the quality produced by the last executed module, and r is the remaining resources. When the system is in state [l,, q, r],o ne module of the i-th level has been executed. (The first level is i = 1; i = 0 is used to indicate the fact that no level has been executed.) The initial state of the MDP is [lo,0 , r],w here r is the available resources for plan execution. (Additional resources may be reserved for rover operation once execution of the plan is complete.) The initial state indicates that the system is ready to start executing a module of the first level of the PRU. The terminal states are all the states of the form [ l ~q,, r ],w here L is the last level of the PRU. In particular, the state [ l ~0,, 7- 1 represents termination with no useful result and remaining resources r. Termination with r = 0 is also possible; if that happens during the execution of an intermediate level of the PRU, a last transition is made to the end of the PRU by skipping all the levels that cannot be performed. In every nonterminal state, [l,, q, r],t he possible actions, designated by E:,,, ex- ecute the j-th module of the next level. The outcome of action is probabilistic. Resource consumption and quality uncertainties define the new state as follows. Rewards and the value function. Rewards are determined by the given reward func- tion applied to the final outcome. Note that no rewards are associated with intermediate results, although this could be easily incorporated into the model. The value function (expected reward-to-go) over all states is defined as follows. The value of a terminal state is based on the utility of the results. V(VL9 Q, 7-11 = U(q) (2) This concludes the definition of a finite-horizon MDP, or equivalently, a state-space search problem that can be represented by a decision tree or AND/OR graph. It can be solved using standard dynamic programming or using a search algorithm such as AO*. Because the rover model satisfies the Markov property, it is easy to show that given an arbitrary PRU, an initial resource allocation and a reward function, the optimal policy for the corresponding MDP provides an optimal control strategy for the rover [36]. We note that the number of states of the MDP is bounded by the product of the number of levels, the maximum number of alternative modules per level, the number of discrete quality levels, and the number of possible resource vectors. While resources could vary over a wide range, the size of the control policy can be reduced by using coarse units. Therefore, unit choice introduces a tradeoff between the size of the pol- icy and its effectiveness. An implementation of the policy construction algorithm for problems that involve one resource confirms the intuition that the optimal policy can be approximated with a coarse resource unit [36]. This observation leads to a significant reduction in policy size and construction time. 4.3 Optimal Control of Multiple Activities Using Opportunity Cost + Consider now the control of a complex plan composed of n 1 PRUs. One obvious approach is to generalize the solution for a single PRU to sequences of PRUs. That is, one could construct a large MDP for the combined sequential decision problem includ- + ing the entire set of n 1 PRUs. Each state must include an indicator of the activity (or PRU) number, i, leading to a general state represented as [i, I, q, r],i E {0,1,. . . ,n }. However, our objective is to eliminate the need to solve complex MDPs on-board by the rover. Transmitting to the rover a very large policy for the entire plan is also unac- ceptable. Instead, we examine a technique to factor the effect of the remaining plan on the current policy using the notion of opportunity cost. We want to measure the effect of the remaining n PRUs on the execution of the first one. This can be expressed in a way that preserves optimality while suggesting an efficient approach to meta-level control that does not requires run-time construction of the entire policy. + Definition 1 LetV*(i,r)= V([i,Io,O,r])for5i n,a ndV*(n 1,r) = 0. V*(i,r) denotes the expected value of the optimal policy for the last n - i PRUs with resources r. To compute the optimal policy for the i-th PRU, we can simply use the following mod- ified reward function. + + Ui(q,r)= Ua(q) V*(i 1,r) (4) In other words, the reward for completing the i-th activity is the sum of the immediate reward and the reward-to-go for the remaining PRUs using the remaining resources. Therefore, the best policy for the first PRU can be calculated if we use the following reward function for final states: W Q , T ) = Vo(q)+ V*(LT) (5) Definition 2 Let OC(r,A T)= V*( 1, T)- V' (1, r - AT)b e the resource opportunity cost function. The opportunity cost measures the loss of expected value due to reduction of Ar in resource availability when starting to execute the last n PRUs. Definition 3 Let the OC-policy for the$rst PRU be the policy computed with the fol- lowing rewardfunction: Ui(q,r)= Uo(q) - OC(r0,ro - ) . The OC-policy is the policy computed by deducting from the actual reward for the first task the opportunity cost of the resources it consumed.

See more

The list of books you might like

Most books are stored in the elastic cloud where traffic is expensive. For this reason, we have a limit on daily download.