Our approach builds upon the vast literature of related work in robotics and planning. The field of discrete planning has made several advances in scope and scalability, mainly through the development of efficient methods for computing heuristic functions automatically from a domain definition (e.g. (Helmert et al., 2007)). This results in task and domain-independent methods for directed search. Being able to utilize this powerful capability was one of our motivations in developing an approach that utilizes arbitrary task planners. Various researchers have investigated the problem of combining task and motion planning (Alami et al., 1998; Volpe et al., 2001; Plaku et al., 2010; Hauser, 2010). However, to the best of our knowledge, very few approaches are able to utilize off-the-shelf task and motion planners and most rely on specially designed task and/or motion planning algorithms. Those that use off-the-shelf task planners make minimal use of task plans: typically as one of the inputs in a heuristic function for guiding search in a configuration space. These approaches do not address the fundamental problems of the task planning description being incomplete and do not attempt to (a) represent geometric information in a form that task planners can use or (b) correct the task planner's representation with information gained through geometric reasoning. In contrast, our approach attempts to refine task plans into motion planning solutions and to provide the task planner with corrected geometric information if necessary.
Cambon et al. (2009) propose an approach that bears similarity to ours in using location references. The references in their approach however are not developed into a system for communicating geometric information to the task planner and correcting its domain definition. They are also not derived from a specification of action preconditions and effects. This approach requires the motion planner to use probabilistic roadmaps (PRMs) (Kavraki et al., 1996) with one roadmap per movable object, and per permutation of a movable object in each gripper for robots like the PR2. The role of the task plan is also limited to its length, which is one of the inputs in a heuristic function for search. However, their approach is probabilistically complete. Kaelbling et al. (2011) combine task and motion planning using an input hierarchy and a specifically designed regression-based planner that is equipped to be able to utilize task-specific reasoning components and regress useful geometric properties.
Erdem et al. (2011) propose an approach for combined task and motion planning that uses a grid based discretized representation for the task planning problem with an ASP solver that supports external predicates. The truth values of these predicates are computed using dedicated modules written in any programming language. However, discretization with even 2 discretized points per pose-dimension would result in intractable task planning problems in our test scenarios, which involve high-dimensional robot poses. In contrast, our focus in this paper was on utilizing task planners without requiring external predicates and task level discretization. In developing such an approach we addressed the key problem of communicating with the task planner using references.
Grasping objects in a cluttered environment is still an open problem in robotics. Dogar et al. (2011) present an approach for replacing pick-and-place in cluttered environments with push-grasps. This is an interesting approach for dealing with obstructions while grasping, and would be promising as an additional primitive action in our overall approach. An interesting direction of research would be to use simulations to determine when the preconditions for safe push-grasps hold. In some of our clutterred table test problems for example, it would be useful to employ push-grasps when it can be determined that none of the objects will be pushed off the table. Approaches have also been developed for motion planning in the presence of movable objects (Levihn et al., 2012), but they do not address the general problem of combining task and motion planning.
Reinvoking task planners relates to replanning for partially observable or non-deterministic environments (Talamudapula et al., 2010; Yoon et al., 2007). However, the focus of this paper is on the substantially different problem of providing the task planner with information gained through geometric reasoning. An alternate representation for dealing with large sets of relevant facts in the initial state would be to treat them as initially unknown and use a partially observable planner with non-deterministic "sensing" actions (Bonet et al., 200). Finding offline contingent solutions would be impractical in our setting; furthermore, they typically don't exist for all possible truth values of geometric predicates. Wolfe et al. (2010) use angelic hierarchical planning to define a hierarchy of high-level actions over primitive actions. Although they do not address the problem of dealing with geometric preconditions like obstructions, our approach could be viewed as using an angelic interpretation: pose references in task plans are assumed to have a value that satisfies the preconditions, and the interface layer attempts to find such values. Approaches for planning modulo theories (PMT) (Gregory et al., 2012) and planning with semantic attachments (Hertle et al., 2012) address related problems high-level planning in hybrid domains. These approaches require an extended planning language and corresponding, extended planners.