Research Abstracts - 2007

Introduction

Planning for real-world robot missions, such as planetary rover exploration, unmanned aerial vehicle team coordination or autonomous underwater vehicle (AUV) surveys, is drawing more and more attention from the research community. It would be ideal if the human operator only needs to give a high level goal, for example, "let the AUV survey along this line on the map with as little battery usage as possible", and the planner outputs the optimal trajectory for the robot so that the high level goal is accomplished. We call such a problem Hybrid Planning (HP). It is hybrid because it plans with both discrete and continuous actions.

Previous research has divided the problem into two parts: first, discrete action planning; and second, continuous trajectories planning that takes into account robot dynamics and obstacles. In realistic problems, however, this decomposed approach often does not lead to optimal solutions and sometimes is not feasible to execute. We propose to combine the two steps into one. To address the problem that incorporating trajectory design into action planning often makes the problem computationally intractable in real time, we propose that with a smart encoding that formulates the problem as a constraint optimization problem and efficient inference methods the problem can become manageable.

Motivating Example

As mentioned before, high level planning is usually separate from trajectory planning for its manageable computation requirement. However, without considering the environment and dynamics the higher level plan can be sub-optimal or even infeasible to execute. Consider the following example.

Problem Statement

The problem I am solving in my thesis is the HP problem, the input to which includes the initial state of the world, the goal state, a set of possible discrete actions, the environment, robot dynamics, temporal constraints, a cost function and the relation between the symbolic world and the continuous state space. The initial state, goal state and possible discrete actions are all encoded in the planning language PDDL [4]. For each discrete action, there are continuous constraints associated on the robot's state variables. The environment file contains the coordinates of points of interest and obstacles. Robot dynamics includes kinematic and dynamic constraints on the robot's state vector, e.g. maximum acceleration. Temporal constraints restrict both discrete actions and continuous state variables. The cost function specifies the cost associated with each variable assignment. It can be total mission time or energy consumption or something else. The relation maps the initial, goal states and pre, post conditions of the discrete actions to regions in the robot's state space.The output is an optimal sequence of actions for the robots so that they reach the goal state from their initial state with the least cost.

There are mainly two challenges in solving the problem. One is encoding. It is not clear how to fold the discrete variable assignment with the continuous optimization together, so that they can be efficiently solved. The other is coming up with a fast search-and-inference approach for maneuvering in the huge search space.

Related Work

A large number of STRIPS and PDDL planners have been extended to handle time and other simple numeric constraints [2][5][6][7][8][9][10]. However, the gap from real world applications is still big, since those planners do not take into account robot dynamics or environment details. On the other hand, research has been done in trajectory design based on low level plans [3]. Task assignment on top of trajectory design for UAVs has also been intensely studied [12][13]. However, none can perform plan generation.

The closest existing planner is aSyMov [11], a hybrid planner which combines symbolic action planning with geometric motion planning. It interleaves between a numeric FF planner and a probabilistic roadmap planner. The main difference from the problem I'm solving is that it does not involve temporal planning or vehicle dynamics; rather it focuses more on the configuration space and it includes roadmap expansion. The approach is also very different and it will be discussed in the next section.

Real-world Application Scenarios

During the visit to the Monterey Bay Aquarium Research Institute (MBARI), three real AUV application scenarios were collected. In this section I will introduce the first scenario in details and use it as a walk-through example, and briefly introduce the rest two.

23m Isobath Survey

Ocean scientists ask an AUV to be planned to survey along the isobath line that is approximately 23m deep, where interesting scientific features appear. The goal is to visit the four waypoints defined by the scientists along the line, and collect vertical data on the way. The total mission time should be minimized. The possible discrete actions of the AUV are listed below in PDDL in Fig. 2.

Fig. 2. Discrete AUV actions in the survey mission

Sea Floor Mapping

The sea floor mapping mission consists of planning for an AUV to map the square area defined by 4 corners from 100m above the sea floor. A low resolution map of the area is used as input, and the goal is to get a high resolution map, while minimizing the battery use.

Adaptive Survey Enabled By Feature Detection

Although very interesting from both the science and autonomy point of view, the feature detection enabled adaptive survey mission cannot currently be carried out, due to the lack of onboard feature detection devices at MBARI. The mission consists of a survey like the first scenario, but on the way if some special science feature is detected, the AUV should be able to adapt the plan for a timed detour, in order to characterize the horizontal volume of the feature.

Proposed Approach

This section will first introduce the encoding we use for the HP problem and then discuss efficient solution methods.

Problem Encoding

We formulate the HP problem as a type of mixed discrete continuous optimization problem, CCSP-LP, which combines conditional CSP and LP to incorporate finite and infinite domain variables, along with logical and continuous constraints. For simplicity we focus on linear constraints, but the formulation can be extended to non-linear constraints. The CCSP-LP problem is formally defined in Definition 1 and its solution defined in Definition 2.

Solution Methods

I will investigate two ideas for solving the problem, and describe them in this subsection.

- Alternating Between Discrete And Continuous -

In this approach, we use A*-like search for discrete action planning with heuristics taking into account costs of the corresponding continuous problem. The search starts from the initial state and needs to reach the goal state. It can be carried out by alternating the following two steps.

First, suppose variable v_i represented by a node in the search tree, is in front of the search queue, we assign a value from d_i to it, making sure that C^V constraints are satisfied. That corresponds to connecting an eligible action to a pre-condition. We also estimate the distance from the effect of the action to the goal state, in terms of the number of actions, which is kept as part of the cost associated with the variable assignment.

Second, the other part of the cost associated with the variable assignment comes from the continuous problem. More specifically, the pre-condition, the chosen action and its effects impose a set of linear constraints on which regions in the robot's state space the robot needs to traverse from and to. If the regions are all convex, then an LP can be formed and solved very efficiently, so that the exact cost can be computed. Otherwise, if the resulting linear optimization problem is hard to solve, we compute the relaxed problem by ignoring all disjunctions and estimate the cost.

We combine the cost from each part and attach it to the current node, which is in turn inserted in the queue based on the cost. The optimal solution then is a connected sequence of actions that reaches the goal state from the initial state with the least cost. This way the continuous part serves as a guide for the search in the discrete space. The alternating structure of the approach is somewhat similar to that of aSyMov [11], which interleaves between symbolic action selection and action validation in the configuration space. The approach is the more feasible one of the two ideas, but it is not as interesting as the other as far as theory is concerned.

- In One Giant Graph -

The second idea involves putting all discrete and continuous variables and constraints in one giant dependency graph, and then turning it into a Directed Acyclic Graph (DAG) so that efficient shortest path algorithms can be applied.

The first and very important step of the approach is to construct the dependency graph. We do this based on the Planning Graph and the relations between the symbolic world and the continuous world. First, all variables in V are nodes; we draw a directed edge from one node to another if the two corresponding propositions in the Planning Graph are connected by an action; and bi-directional edges are for mutex actions. Second, every action is the source of a one-directional edge that goes into a hyper-node that contains the corresponding linear constraints based on the action. Only the hyper-nodes within the same Graphplan level share the same variables. For example, based on the Planning-Graph piece in Fig.3, we can construct a dependency graph piece as shown in Fig.4.

Fig. 3. Planning Graph	Fig. 4. Dependency Graph

The next step is to cluster the strongly connected components and turn the graph into a DAG. It can be done by blindly running tree decomposition [1], but without considering the problem structure the resulting clusters could be random and therefore not helpful. More work needs to be done in such respect.

References:

[1] Kalev Kask and Rina Dechter and Javier Larrosa and Avi Dechter. Unifying Cluster-Tree Decompositions for Reasoning in Graphical Models. Artificial Intelligence Journal. 2005.

[2] S. Wolfman and D. Weld. The LPSAT Engine and its Application to Resource Planning. IJCAI. 1999.

[3] Thomas Leaute and B. Williams. Coordinating Agile Systems Through the Model-based Execution of Temporal Plans. AAAI. 2005.

[4] Alfonso Gerevini and Derek Long. Plan Constraints and Preferences in PDDL3. The Language of the Fifth International Planning Competition. 2006.

[5] D. Smith and D. Weld. Temporal planning with mutual exclusion reasoning. IJCAI. 1999.

[6] D. Long and M. Fox. Fast Temporal Planning in a Graphplan Framework. ICAPS. 2002.

[7] Kautz, H. and Selman, B. Unifying SAT-based and graph-based planning. IJCAI. 1999.

[8] Minh B. Do and Subbarao Kambhampati. Sapa: A Domain-Independent Heuristic Metric Temporal Planner. ECP. 2001.

[9] J. Hoffmann. Extending FF to numerical state variables. ECAI. 2002.

[10] Gerevini, A. and Serina, I. and Saetti, A. and Spinoni, S. Local Search for Temporal Planning in LPG. ICAPS. 2003.

[11] S. Cambon, F. Gravot, R. Alami. A Robot Task Planner that Merges Symbolic and Geometric Reasoning. ECAI. 2004.

[12] J. Bellingham and M. Tillerson and A. Richards and J. How. Multi-Task Allocation and Trajectory Design for Cooperating UAVs. Coordination, Control and Optimization. 2001.

[13] M. Alighanbari and J. How. Cooperative Task Assignment of Unmanned Aerial Vehicles in Adversarial Environments. IEEE American Control Conference. 2005.