Heuristic searches such as A* search are a popular means of finding least-cost plans due to their generality, strong theoretical guarantees on completeness and optimality, simplicity in implementation and consistent behavior. In planning for robotic manipulation, however, these techniques are commonly thought of as impractical due to the high-dimensionality of the planning problem. In this paper, we present a heuristic search-based approach to motion planning for manipulation that does deal effectively with the high-dimensionality of the problem. The paper presents a summary of the approach along with applications to single-arm and dual-arm motion planning with upright constraints on a PR2 robot operating in non-trivial cluttered spaces. An extensive experimental analysis in both simulation and on a physical PR2 shows that, in terms of runtime, our approach is on par with other most common sampling-based approaches and due to its deterministic cost-minimization, the computed motions are of good quality and are consistent, i.e. the resulting plans tend to be similar for similar tasks.

Focused D* and D*-Lite are two popular incremental heuristic search algorithm amenable to goal-directed navigation in partially known terrain. Recently it has been shown that, unlike commonly believed, a version of A* is in many cases faster than D*-Lite, posing the question of whether or not there exist other variants of A* which could outperform algorithms in the D* family on most problems. In this paper we present Multipath Adaptive A* (MPAA*), a simple, easy-to-implement modification of Adaptive A* (AA*) that reuses paths found in previous searches to speed up subsequent searches, and that almost always outperforms D*Lite. We evaluate MPAA* against D*-Lite on random maps and standard game, room, and maze maps, assuming partially known terrain. In environments comparable to indoor and outdoor navigation (room and game maps) MPAA* is 35% faster than D*Lite on average, while on random maps MPAA* is over 3 times faster than D*Lite. D*Lite is faster than MPAA* only in mazes; notwithstanding, we show that if a small percentage of obstacle cells in a maze are made traversable, MPAA* outperforms D*Lite. In addition, we prove MPAA* is optimal and that it finds a solution if one exists. We conclude that for most real-life goal-directed navigation applications MPAA* should be preferred to D*Lite.

Earth observation satellites are space sensors which acquire data, compress and record it on board, and then download it to the ground. Because of the use of more and more sophisticated compression algorithms, the amount of data resulting from an acquisition is more and more unpredictable. In such conditions, planning satellite data download activities offline on the ground is more and more problematic. In this paper, we report the results of a work aiming at evaluating the positive impact of planning downloads onboard when the amount of data produced by each acquisition is known. The data download problem to be solved on board is an assignment and scheduling problem with unsharable resources, precedence constraints, time-dependent minimum durations, and a complex optimization criterion. The generic InCELL library is used to model constraints and criterion, to check non temporal constraints, to propagate temporal constraints, and to evaluate the criterion. On top of this library, greedy and local search algorithms have been designed to produce download plans with limited time and computing resources available on board.

Partial states are states in which the truth value of one or more propositions is unknown. Such states are usually generated in regression and represent not a single state but rather a set of states. Because of this, a new partial state can be a subset of another existent partial state, phenomenon known as subsumption of states. Subsumed states can be pruned as if they were a duplicate. However, regular duplicate detection methods cannot detect such cases. Furthermore, subsumption of states also occurs when forward and backward search algorithms are integrated into a bidirectional planner. In these cases, the forward frontier contains only complete states and the backward frontier will often contain partial states. In this work, we analyze the impact that subsumption of states has on search and propose methods for duplicate detection and detection of collision of frontiers.

In previous work we have shown that grounding, while used by most (if not all) modern state-of-the-art planners, is not necessary and is sometimes even undesirable. In this paper we extend this work and present a novel forward-chaining planner that does not require grounding and can solve problem instances that are too large for current planners to handle. We achieve this by exploiting equivalence relationships between objects whist constructing a lifted version of the relaxed planning graph (RPG) and extracting a relaxed plan. We compare our planner to FF and show that our approach consumes far less memory whist still being competitive. In addition we show that by not having to ground the domain we can solve much larger problem instances.

We introduce a family of MDP reduced models characterized by two parameters: the maximum number of primary outcomes per action that are fully accounted for and the maximum number of occurrences of the remaining exceptional outcomes that are planned for in advance. Reduced models can be solved much faster using heuristic search algorithms such as LAO*, benefiting from the dramatic reduction in the number of reachable states. A commonly used determinization approach is a special case of this family of reductions, with one primary outcome per action and zero exceptional outcomes per plan. We present a framework to compute the benefits of planning with reduced models, relying on online planning when the number of exceptional outcomes exceeds the bound. Using this framework, we compare the performance of various reduced models and consider the challenge of generating good ones automatically. We show that each one of the dimensions---allowing more than one primary outcome or planning for some limited number of exceptions---could improve performance relative to standard determinization. The results place recent work on determinization in a broader context and lay the foundation for efficient and systematic exploration of the space of MDP model reductions.

Real-time search methods, such as LRTA*, have been used to solve awide variety of planning problems because they can make decisions fastand still converge to a minimum-cost plan if they solve the sameplanning task repeatedly. In this paper, we perform an empiricalevaluation of two existing variants of LRTA* that were developed tospeed up its convergence, namely HLRTA* and FALCONS. Our experimentalresults demonstrate that these two real-time search methods havecomplementary strengths and can be combined. We call the new real-timesearch method eFALCONS and show that it converges with fewer actionsto a minimum-cost plan than LRTA*, HLRTA*, and FALCONS.

One of the most promising trends in Domain Independent AI Planning, nowadays, is state-space heuristic planning. The planners of this category construct general but efficient heuristic functions, which are used as a guide to traverse the state space either in a forward or a in backward direction. Although specific problems may favor one or the other direction, there is no clear evidence why any of them should be generally preferred. This paper proposes a hybrid search strategy that combines search in both directions. The search begins from the Initial State in a forward direction and proceeds with a weighted A* search until no further improving states can be found. At that point, the algorithm changes direction and starts regressing the Goals trying to reach the best state found at the previous step. The direction of the search may change several times before a solution can be found. Two domain-independent heuristic functions based on ASP/HSP planners enhanced with a Goal Ordering technique have been implemented. The whole bi-directional planning system, named BP, was tested on a variety of problems adopted from the recent AIPS-00 planning competition with quite promising results. The paper also discusses the subject of domain analysis for state-space planning and proposes two methods for the elimination of redundant information from the problem definition and for the identification of independent sub-problems.

Forward chaining is a popular strategy for solving classical planning problems and a number of recent successful planners exploit it. To succeed, a forward chaining algorithm must carefully select its next action. In this paper, we introduce a forward chaining algorithm that selects its next action using heuristics that combine backward regression and goal ordering techniques. Backward regression helps the algorithm focus on actions that are relevant to the achievement of the goal. Goal ordering techniques strengthens this filtering property, forcing the forward search process to consider actions that are relevant at the current stage of the search process. One of the key features of our planner is its dynamic application of goal ordering techniques: we apply them on the main goal as well as on all the derived sub-goals. We compare the performance of our planner with FF — the winner of the AIPS'00 planning competition — on a number of well-known and novel domains. We show that our planner is competitive with FF, outperforming it on more complex domains in which sub-goals are typically non-trivial.

Automatic extraction of heuristic estimates has been extremely fruitful in classical planning domains. We present a simple extension to the heuristic extraction process from the well-known HSP and FF systems which allow us to apply them to reward maximisation problems. These extensions involve computing an estimate of the maximal reward obtainable from a given state when ignoring delete lists, which are then used to guide the backward search in the FF system. The heuristics are evaluated in a simple robotic delivery task and shown to be effective in reducing the number of nodes evaluated. In this way we seek to apply recent advances in classical planning to a broader range of problems.