A systematic analysis of levels of integration between high-level task planning and low-level feasibility checks

Abstract

We provide a systematic analysis of levels of integration between discrete high-level reasoning and continuous low-level feasibility checks to address hybrid planning problems in robotic applications. We identify four distinct strategies for such an integration: (i) low-level checks are done for all possible cases in advance and the results are used during plan generation; (ii) low-level checks are done exactly when they are needed during the search for a plan; (iii) low-level checks are done after a plan is computed, and if the plan is found infeasible then a new plan is computed; (iv) similar to the previous strategy but the results of previous low-level checks are used during computation of a new plan. We analyze the usefulness of these strategies and their combinations by experiments on hybrid planning problems in different robotic application domains, in terms of computational efficiency and plan quality (relative to its feasibility).

Keywords

Task planning motion planning hybrid planning knowledge representation and reasoning answer set programming cognitive robotics experimental analysis

1. Introduction

Successful deployment of robotic assistants in our society requires these systems to deal with high complexity and wide variability of their surroundings to perform typical everyday tasks robustly and without sacrificing safety. Consequently, there exists a pressing need to furnish these robotic systems not only with discrete high-level reasoning (e.g., planning, diagnostic reasoning) and continuous low-level feasibility checks (e.g., trajectory planning, deadline and stability enforcement, collision checks), but also their tight integration resulting in hybrid planning.

Consider, for instance, a mobile robot tidying up a house. This task requires ordering of robotic actions of moving from one location to another one, picking objects from some locations, and placing objects to their desired locations, considering the preconditions and effects of these actions as well as other changes (e.g., ramifications of actions) in the domain. Therefore, motion planning (e.g., finding a continuous trajectory from one configuration of the robot to another configuration) and other low-level feasibility checks are not sufficient to solve this problem. On the other hand, tidying up a house also requires feasibility checks, such as whether the robot will be able to move from one location to another location without colliding with any objects, whether the robot will be able to reach the object on the table and grasp it without any collisions, or whether the stack of objects will be stable once the robot puts an object at the very top. Therefore, task planning only (e.g., finding a sequence of robotic actions from an initial state to a goal state) is not sufficient to solve the problem either. These examples illustrate the necessity for a hybrid approach to planning, that integrates task planning with feasibility checks.

Motivated by the importance of hybrid planning, recently there have been some studies on integrating discrete task planning and continuous motion planning, presented at various special sessions and workshops organized at major conferences at AAAI 2010, ICAPS 2012, AAAI 2013, RSS 2013, ICRA 2013, ICLP 2013, IROS 2013, AAAI 2014, IROS 2014, ECAI 2014, ICAPS 2014, AAAI 2015, RSS 2015, IJCAI 2015, IROS 2015. These studies can be discussed in two groups, where integration is done at the search level or at the representation level.

For instance, at the search level, the related studies [32,33,38,39,42,60,61,64,70] take advantage of a search algorithm to incrementally build a task plan, while checking its kinematic/geometric feasibility at each step by a motion planner; all these approaches use different methods to utilize the information from the task-level to guide and narrow the search in the configuration space. In this way, the task planner helps the search process during motion planning. Each one of these approaches presents a specialized combination of task and motion planning at the search level, and does not consider a general interface between task and motion planning.

On the other hand, at the representation level, the related studies [1,4,7,11,12,24,34–36] integrate task and motion planning by considering a general interface between them, using “external atoms” (in the spirit of semantic attachments in theorem proving [69]). External atoms are predicate/function atoms whose values are computed by an external mechanism, e.g., by a C++ program. The idea is to use external atoms in the representation of actions, e.g., for checking the feasibility of a primitive action by a motion planner. So, instead of guiding the task planner at the search level by manipulating its search algorithm directly, the motion planner guides the task planner at the representation level by means of external atoms. In [4,12,34], this approach is applied in the action description language $C +$ [31] using the causal reasoner CCalc [50]. In [1,11,35], it is applied in Answer Set Programming (ASP) [2,46,47,49,54] using the ASP solver Clasp [26]. Some studies [7,36] extend the planning domain description language PDDL [23] to support external atoms and modifies the planner FF [37] and the TFD [21] accordingly; the extended PDDL is called PDDL/M, the extended versions of FF and TFD are called FF/M and TFD/M respectively. Hybrid planning is also studied [24] using the PKS planner [57,58] whose language is an extension of STRIPS [22] with databases.

The focus of this paper is to investigate the usefulness of different methods and levels of integration between high-level (discrete) action planning and low-level (continuous) feasibility checks, at the representation level. For this purpose, (i) we identify different integration methods that are applicable to hybrid planning, (ii) propose a general representation and reasoning framework that allows us to implement all these integration methods and their combinations by modifying the representation of the robotic domain rather than by modifying the planners, solvers, and feasibility checkers, (iii) we perform a systematic empirical analysis of the usefulness of different methods and levels of integration over two robotic domains that involve a variety of navigation and manipulation tasks and feasibility checks.

Methods and levels of integration. The representation-level integration of task planning with feasibility checks can be achieved with different strategies and at various levels. For instance, some related studies [1,4,11,12,35] implement some of the feasibility checks as external atoms and use these external atoms in action descriptions to guide task planning when needed. Meanwhile, for a tighter integration, feasibility of task plans is checked by a dynamic simulator; in case of infeasible plans, the planning problem is modified with respect to the causes of infeasibilities, and the task planner is asked to find another plan.

We identify four distinct strategies to integrate a set of continuous feasibility checks into high-level reasoning, grouped into two: directly integrating low-level checks into high-level reasoning while a feasible plan is being generated, and generating plans and then post-checking the feasibility of these plans with respect to the low-level checks. For direct integration, we investigate two methods of integration:

low-level checks are done for all possible cases in advance and then this information is used during plan generation,

low-level checks are done when they are needed during the search for a plan.

For post-checking, we study two methods of integration:

low-level checks are done after a plan is computed, and then a new plan is computed if the plan is found infeasible;

similar to the previous strategy of replanning but a new plan is computed subject to the constraints obtained from the previous feasibility checks.

We consider these four methods of integration, as well as some of their combinations. For instance, some geometric reasoning can be integrated within search as needed, whereas some temporal reasoning is utilized only after a plan is computed in a replanning loop. Considering each method and some of their combinations provides us different levels of integration.

Hybrid planning framework. To investigate the usefulness of these levels of integration at the representation level, we consider the expressive representation formalisms and the state-of-the-art efficient solvers of ASP. In particular, we use hex programs [9] to describe actions and change, and the efficient ASP solver dlvhex [10] to compute plans.

Unlike the formalisms and solvers used in other approaches [1,4,7,11,12,24,34–36], that study integration at representation level, hex and dlvhex [10] allow external atoms to take relations (e.g., a fluent describing locations of all objects) as input without having to explicitly enumerate the objects in the domain. Other formalisms and solvers allow external atoms to take a limited number of objects and/or object variables as input only, and thus they do not allow embedding all continuous feasibility checks in the action descriptions. In that sense, the use of hex programs with dlvhex extends the scope of our experiments with different levels of integration.

It is important to emphasize here that we do not investigate the applicability of ASP for robotic planning, nor do we claim that ASP should be used in robotic planning via hex formalism and the dlvhex solver. Our choices of hex and dlvhex are due to the expressivity of the formalism and the utilities of the solver, as discussed above.

Benchmarks and experiments. We perform experiments on hybrid planning problems in two robotic domains: housekeeping domain (like in [1,11]) and robotic manipulation (like in [12]). The housekeeping domain involves two sorts of feasibility checks: geometric reasoning (e.g., collision checks with static objects, and with movable objects, while finding continuous trajectories) and temporal reasoning (e.g., restrictions on the total duration of plans). The robotic manipulation domain involves geometric reasoning (e.g., collision checks of robots and payloads with each other and the environment).

We analyze the usefulness of different levels of integration in these domains, both from the point of view of computational efficiency (in terms of computation time and space) and from the point of view of plan quality relative to its feasibility (in terms of the number of feasible plans, infeasible plans, and low-level feasibility checks).

Raw data on benchmarks (i.e., experimental results for each problem instance) and the ROS-dlvhex plug-in used for the experiments are available at http://cogrobo.sabanciuniv.edu/?p=854.

It is important to emphasize here that, since our focus is on the integration of task planning with feasibility checks, we consider offline hybrid planning (under the assumption of complete knowledge of the world) in our experiments. Therefore, execution monitoring of plans is out of the focus and the scope of this paper. Various uses of hybrid planning in the context of different execution monitoring frameworks have been studied in some other papers (e.g., [11,15,34]).

Summary of contributions. The main contributions of our study can be summarized as follows:

We have identified and categorized four distinct strategies to integrate a set of continuous feasibility checks into high-level reasoning.

We have determined evaluation metrics to characterize performance of integration methods in terms of solution quality and computational efficiency.

We have designed and implemented an experimentation platform that utilizes a common ASP solver (dlvhex), such that all integration methods can be evaluated in a fair manner. As part of this experimentation platform, we have implemented all the necessary API’s to embed external computations for the feasibility checks.

We have empirically characterized performance of each integration method, as well as their combinations, under two realistic robotic domains, by considering multiple scenarios for each domain.

We have determined general guidelines that may help end-users select proper integration methods for their domains.

Results of our initial studies on systematic analysis of different methods of integration are presented at ICRA 2013 Workshop on Combining Task and Motion Planning [18], AAAI 2013 Workshop on Intelligent Robotic Systems [17], and the 21st RCRA International Workshop on Experimental Evaluation of Algorithms for solving problems with combinatorial explosion [19]. The results presented in this manuscript are significantly more systematic and comprehensive. In particular, in our earlier workshop papers [17,18], the experiments for direct integration were done using the ASP solver dlvhex, whereas the experiments for post-checking were done using the ASP solver Clasp. In this paper, use of a common platform for all experiments based on the ASP solver dlvhex enables a much more fair comparison of different integration approaches. Furthermore, the benchmarks used in this study involve are comprehensive: they include (i) two robotic domains that require feasibility checks with different characteristics, and (ii) more number of instances than the benchmarks used in our earlier papers.

Outline of the paper. In the following, we first present some preliminaries on ASP (Section 2), hybrid planning in ASP (Section 3), and feasibility checks (Section 4). After that, we discuss different methods and levels of integration (Section 5). Then we set the stage for experiments by describing the evaluation criteria (Section 6), the robotic domain descriptions (Section 7), and the experimental setup (Section 8). We discuss the experimental results (Section 9) and the related work (Section 10), and we conclude (Section 11).

2. Answer set programming

Answer Set Programming (ASP) [2,46,47,49,54] is a form of knowledge representation and reasoning paradigm oriented towards solving combinatorial search problems as well as knowledge-intensive problems. The idea is to represent a problem as a “program” whose models (called “answer sets” [28,29]) correspond to the solutions. The answer sets for the given program can then be computed by special implemented systems called answer set solvers. ASP has a high-level representation language that allows recursive definitions, aggregates, weight constraints, optimization statements, and default negation. ASP also provides efficient solvers, such as Clasp [26], which has recently won first places at various automated reasoning competitions, such as SAT competitions and ASP competitions.

Due to the continuous improvement of the ASP solvers and highly expressive representation language of ASP which is supported by a strong theoretical background that results from a years of intensive research, ASP has been applied fruitfully to a wide range of areas. Here are, for instance, three applications of ASP used in industry: decision support systems [55] (used by United Space Alliance), automated product configuration [68] (used by Variantum Oy), and workforce management [63] (used by Gioia Tauro seaport).

ASP has also been used for various robotic applications, such as housekeeping robotics [1,11], cognitive factories [13,15,16], and multi-path finding [14].

hexprograms. In our studies, we use hex programs to describe actions and change. As defined in [9], a hex program consists of rules of the form: $\begin{matrix} (1) & \begin{matrix} α_{1} \lor \dots \lor α_{k} \leftarrow \\ β_{1}, \dots, β_{n}, not β_{n + 1}, \dots, not β_{m}, \end{matrix} \end{matrix}$ where $m, k ⩾ 0$ , each $α_{i}$ is an atom, and each $β_{i}$ is an atom or an external atom.

An external atom is an expression of the form $\begin{matrix} & g [Y_{1}, \dots, Y_{n}] (X_{1}, \dots, X_{m}), \end{matrix}$ where $Y_{1}, \dots, Y_{n}$ and $X_{1}, \dots, X_{m}$ are two lists of terms (called input and output lists, respectively), and g is an external predicate name. Intuitively, an external atom provides a way for deciding the truth value of an output tuple depending on the extension of a set of input predicates. External atoms allow us to embed results of external computations into ASP programs. Therefore, external atoms are usually implemented in a programming language of the user’s choice.

We refer the reader to [9] for detailed information about the semantics of hex programs, and we give some examples of the use of external atoms.

For instance, to describe a precondition of a robot moving from one location to another, we define external atoms of the form $& path_exists_static [x_{1}, y_{1}, x_{2}, y_{2}] ()$ in such a way that it returns true if and only if there is a continuous collision-free trajectory between two locations $(x_{1}, y_{1})$ and $(x_{2}, y_{2})$ . This external atom can be implemented in C $+ +$ , utilizing the bidirectional RRT (Rapidly Exploring Random Trees) [41] as implemented in the OMPL [67] library. Once the external atom is defined and implemented, we can use it to represent a precondition of a robot $r_{1}$ moving from one location $(x_{1}, y_{1})$ to another $(x_{2}, y_{2})$ at time step t as follows: $\begin{array}{l} \leftarrow at (r_{1}, x_{1}, y_{1}, t), goto (r_{1}, x_{2}, y_{2}, t), \\ not & path_exists_static [x_{1}, y_{1}, x_{2}, y_{2}] () . \end{array}$

However, these collision checks are performed considering only the static objects in the environment: the external computation is performed considering only the two locations. To be able to check for collisions of movable objects as well, external computations should also take into account locations of other robots as well as their movements. For that, we can define external atoms of the form $& path_exists_dynamic [goto, at] ()$ . This external atom gets as input the set of atoms of the form $goto (r, x, y, t)$ (describing which robot is moving where at time step t) and of the form $at (r, x, y, t)$ (describing the locations of all robots at time step t). It returns true if and only if for each time step and each robot there is a collision-free motion plan from the location given by $at$ at step t to the location given by $goto$ at step t. Therefore, we can utilize this external atom to ensure collision-free moves of robots between locations as follows: $\begin{matrix} (2) & \leftarrow not & path_exists_dynamic [goto, at] () . \end{matrix}$

dlvhex. Given a hex program, the ASP solver dlvhex computes an answer set for it, if there exists one.

Fig. 1.

Internals of hex evaluation.

dlvhex evaluates a hex program as depicted in Fig. 1. First, the hex program is preprocessed: external atoms are replaced by auxiliary atoms. The resulting auxiliary program (now without external atoms) is instantiated by the ASP grounder Gringo [27]. Next, the ASP solver Clasp searches for an answer set for the auxiliary program. As partial/full answer set candidates are examined, dlvhex uses special callbacks (propagators) of Clasp to evaluate the external atoms. This feature of dlvhex ensures that there is a one-to-one correspondence between auxiliary answer sets (i.e., answer sets for the auxiliary program) and hex answer sets (i.e., answer sets for the hex program), and allows transformation of the former to the latter by removing auxiliary atoms. For more details about hex evaluation, we refer the reader to [8].

When the Clasp callbacks perform external computations (either as soon as possible, or as late as possible), and how the results of failed checks are integrated into the search process (either by just discarding the failed solution candidate, or by also adding constraints that prevent finding further candidates that contain the same failed check) are determined by the external atom evaluation configuration. Therefore, the external atom evaluation configuration plays a significant role in our study to implement different integration methods. For instance, feasibility checks can be done as late as possible after a task plan is computed, or they can be done as soon as it is possible to do so. When dlvhex performs external checks as needed, infeasible plans are eliminated while they are being computed. To put in other words, a plan does not need to be completely computed if its infeasibility is detected by the externally defined feasibility checks.

3. ASP planning

ASP planning [6,45,46,54,65] is based on the idea of reducing a planning problem to the problem of finding an answer set for a program and then computing a plan using an ASP solver. In that sense, it is similar to SAT planning [40], which reduces a planning problem to the problem of finding a satisfying interpretation for a set of propositional formulas and then computes a plan using a SAT solver. ASP planning differs from SAT planning in that it uses programs instead of propositional formulas, and ASP solvers instead of SAT solvers. Also, it is easier to describe some properties and constraints of robotic domains in ASP due to the special constructs its formalism and its solvers support (e.g., default negation, aggregates, optimization statements, cardinality constraints).

In ASP planning, we (i) represent the robotic domain as a program, (ii) represent the planning problem instance as a program, (iii) compute an answer set for the union of these two programs using an ASP solver, and (iv) extract the plan characterized by the answer set. Let us describe this process with an example in the robotic navigation domain mentioned in the previous section. ASP formulations of two other example robotic domains (used in our experiments) are provided in the Appendix.

3.1. Representing a planning problem in ASP

A representation of an action domain in ASP consists of descriptions of actions by means of their preconditions and direct effects, descriptions of ramifications of actions, the commonsense-law of inertia, constraints (such as state, transition, noconcurrency, cardinality constraints), auxiliary definitions (such as derived predicates), optimization statements.

Fluents and actions. To describe the robotic actions and how the world state changes over time, we need to introduce atoms to represent occurrences of actions and values of fluents at a given time step. We denote occurrence of an action A at time step t by $A (t)$ and the value of a fluent F at time step t by $F (t)$ . In the sample navigation domain, the robots move to their destination locations. We introduce atoms of the forms $goto (r, x, y, t)$ to denote the occurrence of action $goto (r, x, y)$ (“robot r goes to location $(x, y)$ ”) at time step t. To describe the preconditions and effects of this action, fluents are needed to represent locations of robots. Thus, we introduce atoms of the form $at (r, x, y, t)$ to denote the values of Boolean fluent $at (r, x, y)$ (“robot r is located at $(x, y)$ ”) at time step t.

Background knowledge. In addition to the fluents and the actions, whose values may change over time, we need to represent background knowledge whose values do not change over time (e.g., locations of static objects, or common sense knowledge). For instance, to describe the locations $(x, y)$ occupied by static obstacles, we introduce atoms of the form $occupied (x, y)$ .

Direct effects of actions. Suppose that the transitions in this sample navigation domain have Markovian property: direct effects of an action executed at a state (at time step t) are observed at the next state (at time step $t + 1$ ).

(Conditional) direct effects of an action are described by HEX rules (1) where $k ⩾ 1$ , $n ⩾ 1$ . The direct effects observed as changes in the fluent values are represented by $α_{1}, \dots, α_{k}$ . The occurrences of actions are represented by some $β_{i}$ ( $1 ⩽ i ⩽ n$ ). The conditions under which these direct effects take place are described by the rest of the atoms $β_{i}$ ( $1 ⩽ i ⩽ m$ ). In the sample navigation domain, as a direct effect of the action $goto (r, x, y)$ , the location of the robot changes to $(x, y)$ ; this direct effect is described by an ASP rule as follows: $\begin{matrix} at (r, x, y, t + 1) \leftarrow goto (r, x, y, t) . \end{matrix}$

Preconditions of actions. Preconditions of actions are represented by means of nonexecutability conditions. Nonexecutability conditions of an action are described by constraints (HEX rules (1) where $k = 0$ ). The occurrences of actions are represented by some $β_{i}$ ( $1 ⩽ i ⩽ n$ ), and the nonexecutability conditions are described by some other atoms $β_{i}$ ( $1 ⩽ i ⩽ m$ ). In the navigation domain, a robot can neither move to an occupied location nor to its current location; these nonexecutability conditions are represented by the rules: $\begin{array}{l} \leftarrow goto (r, x, y, t), occupied (x, y), \\ \leftarrow goto (r, x, y, t), at (r, x, y, t) . \end{array}$ As discussed in the previous section, some preconditions of actions are determined by feasibility checks whose values are computed externally. This is possible thanks to external atoms.

Ramifications (or indirect effects) of actions. Ramifications of actions are described by HEX rules (1) where $k ⩾ 1$ , $n ⩾ 1$ . These rules do not mention any action atoms. A ramification of the $goto (r, x, y)$ action is that “if a robot/object is at a location then it is not anywhere else”: $\begin{array}{l} \neg at (r, x, y, t) \leftarrow at (r, x_{1}, y_{1}, t) (x \neq x_{1}), \\ \neg at (r, x, y, t) \leftarrow at (r, x_{1}, y_{1}, t) (y \neq y_{1}) . \end{array}$

The commonsense law of inertia. Formalizing the commonsense law of inertia is proposed as a solution to the frame problem [51]. According to the commonsense law of inertia, an action can be assumed not to change the value of a fluent unless there is evidence to the contrary. ASP allows us to easily formalize the commonsense law of inertia, thanks to its nonmonotonic negation $not$ . Indeed, we can describe the commonsense law of inertia by HEX rules (1) of the form $\begin{array}{l} F (t + 1) \leftarrow F (t), not \neg F (t + 1), \\ \neg F (t + 1) \leftarrow \neg F (t), not F (t + 1) \end{array}$ for each fluent atom F. For instance, in the robotic navigation domain, we represent the commonsense law of inertia by the rules: $\begin{array}{l} at (r, x, y, t + 1) \leftarrow \\ at (r, x, y, t), not \neg at (r, x, y, t + 1), \\ \neg at (r, x, y, t + 1) \leftarrow \\ \neg at (r, x, y, t), not at (r, x, y, t + 1) . \end{array}$

Constraints. We can express various sorts of constraints (about states, transitions, concurrency of actions, cardinality of a set of atoms, durations of actions, etc.) using HEX rules (1) where $k = 0$ . For instance, the state constraint that “no two robots occupy the same location at any time step” can be expressed by the following rules: $\begin{matrix} \leftarrow at (r_{1}, x, y, t), at (r_{2}, x, y, t) (r_{1} < r_{2}) . \end{matrix}$

Planning problem. An initial state of a planning problem instance can be described as a set of facts (HEX rules (1) where $k = 1$ , $n = m = 0$ ) using fluent atoms. For instance, the following facts describe an initial state (at time step 0) for two robots: $\begin{array}{l} at (R_{1}, 0, 0, 0) \leftarrow, \\ at (R_{2}, 0, 3, 0) \leftarrow . \end{array}$

The goal is described as a set of HEX rules (1) where $k = 0$ , $n = 0$ , and each goal condition is represented by $β_{i}$ ( $n < i ⩽ m$ ). For instance, the following rules express that the robots are expected to be located at $(3, 4)$ and $(7, 8)$ in a goal state: $\begin{array}{l} \leftarrow not at (R_{1}, 3, 4, maxstep), \\ \leftarrow not at (R_{1}, 7, 8, maxstep), \end{array}$ where $maxstep$ is the specified makespan for a plan.

3.2. Solving a planning problem in ASP

Suppose that the robotic actions and the change of worlds states are described by a set D of HEX rules, and a planning problem instance P is described by another set P of HEX rules, as shown by examples above. We can present the union $D \cup P$ of these two programs to the ASP solver dlvhex, in its input language. Then, for a specified plan length $maxstep$ for a plan, dlvhex tries to find an answer set for the program $D \cup P$ . If the program has an answer set then the action atoms in this set characterize a plan.

Once a maximum makespan $maxmakespan$ for a plan is specified, an optimal plan of length $maxstep$ can be computed by trying to find a plan using the ASP solver dlvhex with $maxstep = 1, 2, 3, \dots, maxmake span$ .

3.3. Discussion

ASP provides a general declarative problem solving framework for a wide variety of combinatorial search problems. Therefore, its formalism and its solvers support many utilities. In that sense, its formalism is different from action languages [30] (introduced to represent dynamic systems), planning languages [22,52] (introduced to represent planning problems). Its solvers are different from reasoning systems (implemented to solve various reasoning problems, such as prediction, planning, postdiction) and planners (implemented to solve planning problems, such as classical planning, conditional planning, conformant planning).

4. Feasibility checks

There are various feasibility checks to consider while planning in a robotic domain, and each feasibility check is a well-studied computational problem in robotics. For instance, feasibility of the action of a mobile robot moving from one location to another as described in Section 2, can be modeled as a motion planning problem with collision checks.

Let us formally define the motion planning problem. We first present some preliminary definitions as in [59].

A continuous state consists of a collection of variable values that completely describe a dynamic system at any given instant in time. The set of all continuous states constitutes the state space of a system.

For instance, the continuous state of a 2D polygonal robot consists of variables that specify the position $(x, y)$ and orientation θ of the polygon with respect to a frame of reference. In this case, the state space is commonly referred to as the configuration space. In case of a simple car, the state space of the system consists of the velocity v and steering angle ϕ in addition to the configuration $(x, y, θ)$ of the car.

Please note that, despite the identical terminology, the notion of a state in dynamic systems is different from the notion of a state in task planning. In particular, in dynamics terminology, a state of a system essentially consists of continuous variables that uniquely define the configuration of the system augmented with variables that define its velocity. In this paper, the term “state” will be reserved for task planning, and the term “continuous state” will be used for dynamic systems.

Continuous state constraints indicate a desired invariant that each continuous state should satisfy. In motion planning, common continuous state constraints include collision avoidance with obstacles and other robots, joint limits, limits on accelerations and radius of curvature avoid abrupt motions.

The motion-planning goal is specified as desired constraints that a continuous goal state should satisfy. Such constraints may include a desired position or orientation. In motion-planning with dynamics, it is also common to require that a robot’s velocity remain within certain bounds.

Finally, a trajectory indicates the evolution of a system’s continuous state with respect to time. In particular, a trajectory is a function $γ : [0, T] \to S$ , parameterized by time $T \in R ⩾ 0$ .

Given these definitions, a motion-planning problem can be defined as a tuple $P = (S, Valid, s_{init}, Goal)$ , where

$S$ represents a state space consisting of a finite set of variables that completely describe the continuous state of the system;

$Valid : S \to {⊤, ⊥}$ is a continuous state constraint function, i.e., $Valid (s) = ⊤$ iff $s \in S$ satisfies the continuous state constraints;

$s_{init} \in S$ is an initial continuous state;

$Goal : S \to {⊤, ⊥}$ is a goal function, i.e., $Goal (s)$ is ⊤ iff $s \in S$ satisfies the motion-planning goal.

A solution to the motion-planning problem P is a valid trajectory $γ : [0, T] \to S$ that starts at $s_{init}$ and satisfies the motion-planning goal, i.e., $γ (0) = s_{init}$ ; $Goal (γ (T)) = ⊤$ ; and $\forall t \in [0, T] : Valid (γ (t)) = ⊤$ .

The basic motion planning is proven to be PSPACE-complete [62], like propositional action planning [3,20].

There are various books that describe motion planning [5,44], and software libraries [67] that gather implementations of various motion planners. There are also software libraries [56] that include implementations of various collision check algorithms. Our methods of integration allow the use of these existing libraries as they are.

5. Levels of integration

An action domain description can be viewed as a transition system, i.e., a directed graph whose nodes correspond to world states and edges to transitions between states via execution of actions. Transitions in such a domain can be formalized in ASP over time steps $0, \dots, t$ , whereas a planning problem instance can be formalized in ASP by an initial state $S_{0}$ (as facts) and goal conditions (as constraints) in such a domain. Then an answer set for the union of these two ASP programs, if there exists one, characterizes a history for a plan $⟨ A_{0}, A_{1}, \dots, A_{n - 1} ⟩$ , i.e., a path $⟨ S_{0}, A_{0}, S_{1}, A_{1}, \dots, S_{n - 1}, A_{n - 1}, S_{n} ⟩$ in the transition system described by the action domain where goal conditions are satisfied at $S_{n}$ .

A low-level continuous reasoning module gets as input, a part of a plan history and returns whether this part of the plan history is feasible or not with respect to some geometric, dynamic or temporal reasoning. For example, the feasibility of a robot’s action of moving from a location $(x, y)$ to another location $(x^{'}, y^{'})$ characterized by a part of the history of a plan, can be checked by a low-level continuous reasoning module that takes these locations as input and utilizes a motion planner to do collision checks.

Let L denote a low-level reasoning module that can be used for feasibility checks of plans for a planning problem instance H. We consider four different methods of utilizing L for computing feasible plans for H, organized into two groups: directly integrating reasoning L into H, and post-checking plans of H using L.

5.1. Direct integration of feasibility checks

For directly integrating low-level reasoning into plan generation, we propose two methods of integration: Precomputation (Pre) and Interleaved Computation (Int).

Pre– precomputation. This method first performs all possible feasibility checks of the low-level reasoning module L that may be required by the planning problem instance H, in advance. The results of these feasibility checks are represented by a new predicate. For instance, the results of feasibility checks of a robot r’s action of moving from a location $(x, y)$ to another location $(x^{'}, y^{'})$ can be represented by atoms of the form $path_exists (x, y, x^{'}, y^{'})$ , where $1 ⩽ x, x^{'} ⩽ n$ and $1 ⩽ y, y^{'} ⩽ m$ .

Then, these new atoms are used (like external atoms) to express constraints (like preconditions of actions). For instance, to express that a robot r cannot go from a location $(x, y)$ to a location $(x^{'}, y^{'})$ , if there is no collision-free continuous trajectory between these two locations, a constraint of the form $\begin{array}{l} \leftarrow at (r, x, y, t), goto (r, x^{'}, y^{'}, t), \\ not path_exists (x, y, x^{'}, y^{'}) \end{array}$ is added to the ASP formulation of the robotic domain. Such constraints ensure that infeasible actions do not occur in a plan computed for H.

Next, the method tries to find a plan for H with respect to the modified domain description.

Clearly, in a robotic domain without movable obstacles, every plan obtained with this method satisfies all low-level feasibility checks of L. Another advantage of this method is that, since the domain description is augmented with constraints, the search space is pruned.

In robotics, it is common to precompute and cache the results of such feasibility checks to speed up computations, such as, determining robot base locations for reachability, calculating stable grasps between robot gripper and object pairs. These results can be utilized for hybrid planning in robotic domains via the method Pre.

Note that, since the results of feasibility checks are represented by atoms, they can be easily utilized for describing the preconditions of actions in other action description formalisms (like PDDL). In that sense, Pre can be applied with other formalisms and solvers.

On the other hand, in some robotic domains, Pre has severe practical limitations due to the need for too many feasibility checks. For instance, in the navigating robot example above, Pre is feasible for low-level motion planning queries if we do not consider movable obstacles in the world because the number of queries is polynomial in the size of the world: for a world with $n \times m$ locations, there are $O (n^{2} m^{2})$ motion planning queries. However, if we consider movable obstacles in the world and since these obstacles can cover any location at any time, then the number of queries may be beyond exponential in the size of the world (i.e., due to $O (n^{2} m^{2} (n m)!)$ motion planning queries), rendering precomputation infeasible.

Applications of the method Pre to hybrid planning can be found in various related studies [24,35].

Int– interleaved computation. This method interleaves feasibility checks with high-level reasoning in the search of a plan for H, by means of external atoms that are externally evaluated by a low-level reasoning module L that implements these feasibility checks.

Consider, for instance, the navigating robot example, and suppose that there are no movable objects in the environment. This method first introduces external atoms of the form $& path_exists_static [x, y, x^{'}, y^{'}] ()$ whose values are computed by L as follows: L returns true if and only if there is a continuous collision-free trajectory between the locations $(x, y)$ and $(x^{'}, y^{'})$ .

Then, for every pair $(x, y)$ and $(x^{'}, y^{'})$ of locations, a constraint of the form $\begin{array}{l} \leftarrow at (r, x, y, t), goto (r, x^{'}, y^{'}, t), \\ not & path_exists_static [x, y, x^{'}, y^{'}] () \end{array}$ is added to the ASP formulation of the robotic domain. This constraint ensures that, at any time step t, if there is no collision-free continuous trajectory between the locations $(x, y)$ and $(x^{'}, y^{'})$ , the robot r does not move from $(x, y)$ to $(x^{'}, y^{'})$ in a plan computed for H.

Next, the method tries to find a plan for H with respect to the modified domain description.

With external atoms included in the constraints, for each action considered during the search, the relevant feasibility checks implemented in L are immediately performed to find out whether including this action will lead to an infeasible plan. An action is included in the plan only if it is feasible. The results of feasibility checks of actions can be stored not to consider infeasible actions repeatedly in the search of a plan. Plans generated by the method Int satisfy all feasibility checks.

If there are movable objects in the environment, then the method Int introduces a different form of external atom, like $& path_exists_dynamic [goto, at] ()$ , and adds a different form of constraints (i.e., constraints (2)) to the robotic domain description as described in Section 2.

As discussed in Section 2, external atoms are evaluated when needed, so are the feasibility checks in L. In this way, infeasible plans are eliminated while they are being computed, so a plan does not need to be completely computed if its infeasibility is detected by the externally defined feasibility checks.

On the other hand, despite these advantanges, the method Int can be utilized in some formalisms (e.g., $C +$ , ASP, PDDL/M) and solvers (e.g., CCalc, Clasp, FF/M, TFD/M, PKS) to some extent [1,4,7,11,12,24,36], since external atoms whose inputs involve predicate names cannot be utilized in these formalisms and solvers. Int can be utilized completely in hex programs and the dlvhex solver.

The applications of the method Int to hybrid planning can be found in various related studies [1,4,7,11,12,35,36].

5.2. Post-checking plan feasibility

Alternatively, the feasibility checks of the low-level reasoning module L can be integrated with high-level reasoning in the search for a plan for the planning problem instance H, by post-checking the feasibility of a computed plan for H relative to L and replanning if the plan is found infeasible. We propose two methods of integration to perform post-checking on solutions: Replanning (Repl) and Guided Replanning (Grepl).

Repl– replanning. This method first generates a plan for H, and then checks its feasibility using L. The plan is discarded if it is found infeasible and a new plan is generated for H. This process continues until a feasible plan is obtained or all possible candidates are discarded, since a feasible plan does not exist.

The method Repl provides no guidance while generating a new plan; hence, it may seem somewhat not useful. However, Repl is commonly used in robotics, mainly due to the fact that many of the planners do not allow for addition of sophisticated constraints to planning problem descriptions.

Also, it is good to include this method in our systematic analysis of different methods and levels of integration, to better understand the usefulness of providing guidance to generation of new plans.

Grepl– guided replanning. This method generates a plan for H, and then checks its feasibility using L. Whenever a feasibility check fails, the conditions that cause the failure are identified, and constraints are added to the formulation of H ensuring that these conditions do not occur in a plan computed for H. Then, the method tries to generate a plan for the modified planning problem instance $H^{+}$ , and performs the feasibility checks in L over the generated plan (if exists). This process of modifying the planning problem description, generating a plan for it, and checking the plan’s feasibility continues until a feasible plan is computed for H, or it is find out that a feasible plan does not exist.

Consider, for instance, a robot R navigating in an environment. Suppose that a plan is computed for a planning problem H, and the plan involves the robot’s action of moving from location $(1, 3)$ to location $(3, 3)$ . Suppose that the plan is found infeasible since the feasibility check of existence of a continuous collision-free trajectory implemented in the module L failed for this action. Then, the method Grepl adds the following constraints $\begin{array}{l} \leftarrow at (R, 1, 3, t), goto (R, 3, 3, t) \\ (0 ⩽ t ⩽ maxstep) \end{array}$ to the ASP formulation of H, and tries to find a plan for the modified problem.

Applications of the method Grepl to hybrid planning can be found in various related studies [1,4,11,12,34,35].

A remark about replanning: The replanning problem considered in the methods above involves the same domain description as in the original planning problem, the same initial state, the same goals, and possibly some additional constraints. Therefore, replanning may extend the original planning problem by adding constraints. In that sense, replanning as in the methods above is different from replanning in the context of execution monitoring of plans, where the replanning problem involves the same domain description, the current state, and the same goals.

5.3. Comparison of integration methods

A comparison of these methods, in terms of their applicability with existing planners and reasoners and in terms of bilateral guidance between task planning and feasibility checks, is presented in Table 1.

Table 1
A comparison of methods of integration: Benefits (+) and drawbacks (−)

Pre Int Repl Grepl

Applicability with existing tools + − + +/−

Low-level guides task planning + + − +

Task planning triggers low-level − + + +

	Pre	Int	Repl	Grepl
Applicability with existing tools	+	−	+	+/−
Low-level guides task planning	+	+	−	+
Task planning triggers low-level	−	+	+	+

The methods Pre and Repl do not need any special constructs, so they are applicable with a wide range of planners and reasoners. On the other hand, Int requires special constructs like external atoms; therefore, it is applicable with planners and reasoners that support such constructs. Similarly, Grepl requires representation of planning problems with complex goals and temporal constraints; therefore, it is applicable with planners and reasoners that support representation of such problems.

The methods Pre and Int utilize all relevant information conveyed from low-level feasibility checks for planning. Grepl utilizes such information for replanning, only after infeasibility of plans are detected. Repl does replan with no such guidance, so low level feasibility checks do not trigger task planning.

Low-level feasibility checks are triggered by task planning in all the methods except Pre, where they are all performed before planning.

5.4. Implementation of integration methods

In our studies, the integration methods Pre, Int, Repl, and Grepl are realized in ASP as follows.

Consider the same planning problem instance (i.e., same initial state, same goal conditions); suppose that no additional constraints are added for Grepl. The hex program that represents the hybrid planning domain description is the same for Int, Repl, Grepl. Therefore, only the dlvhex solver’s configuration for evaluation of external computations is different: for Int, we configure the solver dlvhex in a way that it checks feasibility of actions as soon as all inputs of a feasibility check are available; for Grepl, we require a fully specified solution candidate to perform this check; for Repl we additionally deactivate “external nogood learning” in the solver so that the solver can no longer remember previously failed feasibility checks.

For Pre, we replace external atoms in the domain description by new atoms, whose values are evaluated beforehand and described as a set of facts.

These minimal changes in the implementation of the four strategies aim at keeping the high-level planning engine the same while changing only the method of low-level integration. This way we know that differences in results are really just because of the type of integration and not because of other effects.

5.5. Combinations of integration methods

Let us denote by $L_{P RE}$ and $L_{I NT}$ the low-level feasibility checks directly integrated into plan generation, with respect to Pre and Int, respectively. Let us denote by $L_{P OST}$ the low-level feasibility checks performed after plan generation, with respect to Repl or Grepl.

In our systematic analysis of levels of integration, we do consider the hybrid framework depicted in Fig. 2: by selectively enabling some of the feasibility checks, we consider combinations of feasibility checks being performed by different types of integration. For instance, to analyze the usefulness of Pre, we disable the other integrations (i.e., $L_{I NT} = L_{P OST} = \emptyset$ ); to analyze the usefulness of a combination of Pre and Repl, we disable other integrations (i.e., $L_{I NT} = \emptyset$ ).

6. Evaluation criteria

We consider two quantitative metrics to evaluate different types and levels of integration: solution quality and computation time.

Fig. 2.

Different levels of integration.

We quantify solution quality by addressing the following two questions:

How many feasible plans are found in a given time?

How many infeasible plans are discarded meanwhile?

In this study, we are not concerned with optimization of plans and thus we do not consider other measures for plan quality.

Note that, with the methods Pre and Int, since all relevant information from feasibility checks are utilized for task planning, all computed plans are feasible. With the other methods, Repl and Grepl, some infeasible plans may be generated and discarded until a feasible plan is computed. Since such infeasible plans guide replanning in Grepl by means adding constraints to planning problems, solution quality of Grepl is expected to be higher than Repl.

We quantify computational efficiency by means of

CPU time to find the first feasible plan,

total CPU time to find the first 10,000 feasible plans, and

total CPU time for low-level feasibility checks.

In some cases, the first feasible plan can be computed in a short amount of time. Therefore, for a better understanding of planning efficiency, we also consider the computation time of first 10,000 feasible plans.

Independent from the number of low-level feasibility checks, the duration of external computations can dominate the overall planning time, or it can be negligible depending on the computational burden of performing the feasibility check. Therefore, we measure not only the number of computations of low-level feasibility checks but also the time spent for these computations.

7. Overview of the robotic domains

For a systematic empirical evaluation of integration methods, we consider various planning problem instances in two action domains: housekeeping domain (like in [1,11]) and robotic manipulation domain (like in [12]). Both of these domains require hybrid planning.

7.1. Housekeeping domain

In the housekeeping domain [1,11], the goal is for multiple autonomous PR2 robots to collaboratively tidy up a house, by putting items to their proper places, within a given amount of time. For example, dirty dishes are put into the dishwasher, books into the bookcase, and pillows into the cupboard. Robots can perform the following actions: they can move from one location to another location, attach to and detach from objects. Therefore, a task plan consists of these three forms of actions.

In this domain, there are two sorts of feasibility checks: checking that a plan can be completed with a given deadline, and checking whether a plan is geometrically and kinematically feasible for each robot. These checks require utilization of both geometric and temporal reasoning.

Table 2
Overview of low-level checks for housekeeping domain

Check Description

Relevant input

Realization

$Pe$ Check whether a robot can move from one coordinate to another one.

Start and goal coordinate (precomputation possible).

RRTconnect motion planning via MoveIt! using FCL/OMPL, 3 attempts, 0.5 s time limit.

$Po$ Check whether a robot can move from one coordinate to another one, considering movable objects (obstacles) in the world.

Start and goal coordinate for the robot, coordinate and type for k objects distinct inputs: (precomputation infeasible for $k \neq 0$ ).

RRTconnect motion planning via MoveIt! using FCL/OMPL, 3 attempts, 1 s time limit.

$Ti$ Estimate the time a robot needs to move from one coordinate to another one by performing multiple motion plans and measuring the length of the shortest one (disregarding obstacles).

Start and goal coordinate (precomputation possible).

RRTconnect motion planning via MoveIt! using FCL/OMPL, 9 attempts, 1.5 s time limit.

Check	Description
$Pe$	Check whether a robot can move from one coordinate to another one.
Start and goal coordinate (precomputation possible).
RRTconnect motion planning via MoveIt! using FCL/OMPL, 3 attempts, 0.5 s time limit.
$Po$	Check whether a robot can move from one coordinate to another one, considering movable objects (obstacles) in the world.
Start and goal coordinate for the robot, coordinate and type for k objects distinct inputs: (precomputation infeasible for $k \neq 0$ ).
RRTconnect motion planning via MoveIt! using FCL/OMPL, 3 attempts, 1 s time limit.
$Ti$	Estimate the time a robot needs to move from one coordinate to another one by performing multiple motion plans and measuring the length of the shortest one (disregarding obstacles).
Start and goal coordinate (precomputation possible).
RRTconnect motion planning via MoveIt! using FCL/OMPL, 9 attempts, 1.5 s time limit.

Coordinates are pairs $⟨ x, y ⟩$ with $x, y \in {1, \dots, 8}$ .

Table 2 presents an overview of low-level reasoning modules used in the housekeeping domain. In particular, $Po$ and $Pe$ are utilized to check whether a collision-free path exists from one coordinate to another, with and without consideration of dynamic obstacles in the environment, respectively. To ensure deadlines can be met, $Ti$ is used to estimate the time required to traverse such a collision-free path. These feasibility checks are realized using bidirectional RRT as implemented in the OMPL library, which we use via the MoveIt! [66] and FCL [56] libraries.

As shown in Table 2, for each check, different settings are used for the motion planner. In particular, we increase the planning time limit for $Po$ and increase the number of planning attempts for $Ti$ . If the motion planner does not return a solution within a given amount of time (which is determined empirically) and after a preset number of trials, the corresponding move action is considered infeasible.

7.2. Robotic manipulation domain

We consider a mobile manipulation problem, as in [12], where two Kuka youBots arrange elongated payloads in a space that contains obstacles by performing one of the three forms of actions: moving from one location to another location, picking and dropping an endpoint of a payload. The payloads can only be carried cooperatively by both robots. Therefore, task plans in this domain are composed of these actions.

To find a feasible plan, we need to ensure that objects do not collide with each other or with the environment, and robots do not collide with each other. Some collision checks between objects can be realized in the high-level representation of the action domain, whereas most collision checks require use of geometric models of the robot and the environment. For instance, collision-free paths for robots for particular collaborative actions can only be determined using low-level geometric reasoning and cannot be represented at the high-level.

Table 3
Overview of low-level checks for robotic manipulation domain

Check Description

Relevant input

Realization

$Ro$ Given two robot poses check whether they are collision-free among the robots and between robots and the environment.

Two robot poses (precomputation possible).

Collision check via MoveIt! using FCL.

$Pa$ Given two payload poses check whether they are collision-free among the payloads and between payloads and the environment.

Two payload poses (precomputation possible).

Collision check via MoveIt! using FCL, representing each payload as a robot.

$Mo$ Given start and goal positions of two robots, positions of payloads, and whether the robots are carrying one of the payloads, check whether a collision-free motion plan exists.

Start and goal poses of two robots, poses of k payloads, carried payload (precomputation impossible).

RRTconnect motion planning via MoveIt! using FCL/OMPL, 3 attempts, 4 s time limit.

Check	Description
$Ro$	Given two robot poses check whether they are collision-free among the robots and between robots and the environment.
Two robot poses (precomputation possible).
Collision check via MoveIt! using FCL.
$Pa$	Given two payload poses check whether they are collision-free among the payloads and between payloads and the environment.
Two payload poses (precomputation possible).
Collision check via MoveIt! using FCL, representing each payload as a robot.
$Mo$	Given start and goal positions of two robots, positions of payloads, and whether the robots are carrying one of the payloads, check whether a collision-free motion plan exists.
Start and goal poses of two robots, poses of k payloads, carried payload (precomputation impossible).
RRTconnect motion planning via MoveIt! using FCL/OMPL, 3 attempts, 4 s time limit.

Poses are triples $⟨ x, y, direction ⟩$ with $x, y \in {1, \dots, 11}$ and $direction \in {n, s, w, e}$ .

Table 3 presents an overview of low-level reasoning components used in the robotic manipulation domain. In particular, given position and orientation of two robots, $Ro$ verifies if this configuration is collision-free, while $Pa$ checks whether two payloads can be located in particular positions and orientations without collisions with environment or each other. Furthermore, $Mo$ verifies if it is possible to generate a motion plan for moving robots and payloads from one configuration to another one.

For this domain, we perform motion planning and collision checking for one or two independently moving Kuka youBot bases, or for two Kuka youBot bases connected by a payload. Similar to the housekeeping domain, we realize motion planning using bidirectional RRT using the MoveIt!, OMPL, and FCL libraries.

7.3. Discussion

The domains used as benchmarks have been carefully designed, taking into account the following aspects.

They represent real world robotic domains, such that they can be dynamically simulated and/or physically implemented using real robots, as in [1,11,12].

The domains involve a variety of robotic actions, involving both navigation [1,11] and manipulation [12].

The problem sizes are reasonable not only from the perspective of the real world applications, but also from the point of view of related work on robotic planning. For instance, in planning problem instances of our housekeeping domain, we view the workspace as an $8 \times 8$ grid, which indicates 64 abstract locations of interest for the robots. We consider up to 5 robots and 8 objects of interest. The plans require up to 45 robotic actions. The robotic manipulation instances are even larger in size. The related work [64] considers a domain where a robot transfers some objects from one place to another, one at a time, as part of the experimental evaluation. The largest instance involves up to 40 objects, and the maximum makespan is 40. The other related works [7,24,36,42] consider smaller instances.

The domains involve a variety of feasibility checks whose computations necessitate the use of different algorithms or external computations of different complexity. For instance, in the housekeeping domain, all the low-level reasoning modules perform motion planning to check feasibility of actions, but the motion planners are used with different parameters. In robotic manipulation domain, there are two types low-level reasoning: (i) object collision checks $Pa$ and $Ro$ operate on 3D models of robots, objects, and the environment; and (ii) the motion planning check $Mo$ performs motion planning and internally performs many collision checks as in (i). Hence, for $Pa$ and $Ro$ checks, a collision checker is used while a motion planner is used for $Mo$ .

To be able to use the method Pre, enumeration of feasibility checks is required. The types of feasibility checks considered in our domains require different computational effort for enumeration. The feasibility checks $Pe$ and $Ti$ in the housekeeping domain take a pair of coordinates as input, similarly checks $Ro$ and $Pa$ in the robotic manipulation domain take a pair of poses. If there are $n \times m$ coordinates, in the housekeeping domain, we need to perform the checks $Pe$ and $Ti$ $O (n^{2} m^{2})$ times; in the robotic manipulation domain, since there are 4 possible orientations for a robot and 2 possible orientations for a payload endpoint, we need to perform $Ro$ $O (n^{2} m^{2})$ number of times and $Pa$ $O (n^{2} m^{2})$ number of times.

On the other hand, the checks $Po$ and $Mo$ include all objects in the environment as inputs; therefore, the number of potential distinct feasibility checks significantly exceeds the number of the checks discussed in the previous paragraph, rendering precomputation of these feasibility checks infeasible. For instance, in the housekeeping domain, if we consider all movable objects, then the number of the check $Po$ increases to $O (n^{2} m^{2} (n m)!)$ . Similarly, the number of feasibility checks $Mo$ increases by a factor of $(n m)!$ . Performing a high number of feasibility checks as in these domains can require a large amount of time; but even if that is not the case, the results of these checks must be represented in the domain to constrain high-level reasoning, and this requires a large amount of space.

8. Experimental setup

We applied different variations of integration methods to planning problem instances in the housekeeping domain, with varying size and difficulty. In particular, we performed tests on 20 Housekeeping instances (over $8 \times 8$ grid) with up to 5 robots and 8 objects, which require plans up to 12 steps (average 8.2 steps) and up to 45 actions (average 24.0 actions) in a single plan. We experimented with 20 Robotic Manipulation instances (over a $11 \times 11$ grid) that require plans of up to 21 (average 8.3) steps, and involving up to 63 (average 23.4) actions.

All experiments were performed on a Linux server with 32 2.4 GHz Intel^® E5-2665 CPU cores and 64 GB memory. We realized hybrid planning using the dlvhex solver (tag 2_1_0_loi) using the backends Gringo (3.0.4) and Clasp (2.1.1). We used ROS (groovy) to manage robot descriptions of the PR2 robots and Kuka robots. Motion planning queries were realized using bidirectional RRT as implemented in the OMPL library, which we used via the MoveIt! and FCL libraries. Note that we used multi-threading (limited to 4 threads) for motion planning but not within Gringo and Clasp. We considered a timeout of 10 h (36,000 s) per planning problem instance. We obtained the results of experiments, considering the metrics explained in Section 6, for

first: obtaining the first feasible plan, and for

all: obtaining a maximum of 10,000 feasible plans.

The measurements for enumerating up to 10,000 plans reveal information about solution quality and provide a more complete picture of the behavior of each method: one method might find a feasible solutions very fast by chance, whereas finding many (or all) solutions fast by chance is unlikely.

Table 4
Computational effort of precomputation

Domain Check # of checks Time (s)

Housekeeping $Pe$ 4,096 268.3

$Ti$ 4,096 271.8

Robotic manipulation $Ro$ 125,840 35.4

$Pa$ 9,669 2.1

Domain	Check	# of checks	Time (s)
Housekeeping	$Pe$	4,096	268.3
$Ti$	4,096	271.8
Robotic manipulation	$Ro$	125,840	35.4
$Pa$	9,669	2.1

Table 5

Housekeeping: Comparison between integration methods

Integration			first					all

			Quality		Efficiency			Quality			Efficiency

			Timeouts	Infeasible plans	Low-level checks	Low-level time	first time	Timeouts	Feasible plans	Feasible plans	Low-level checks	Low-level time	all time

$Pe$	$Po$	$Ti$	#	#	#	%	s	#	#	%	#	%	s
Repl	Repl	Repl	16.0	12,384,934	17	0.0	28,865	16.0	2,584	0.0	19	0.0	28,893
Pre	Repl	Pre	8.3	4,144,063	947	0.4	15,660	8.7	5,603	0.1	1,404	0.5	16,338
Grepl	Grepl	Grepl	2.3	174,148	30,034	70.3	4,948	2.3	8,321	4.5	30,156	69.6	5,013
Pre	Grepl	Pre	1.0	11,804	13,043	67.6	2,645	1.0	7,472	33.8	13,735	66.0	2,776
Pre	Int	Pre	0.0	0	2,642	34.7	1,025	0.0	7,599	100.0	3,569	37.3	1,198
Int	Int	Int	0.0	0	5,873	56.2	1,019	0.0	8,517	100.0	6,118	53.1	1,112

Table 6

Robotic manipulation: Comparison between integration methods

Integration			first					all

			Quality		Efficiency			Quality			Efficiency

			Timeouts	Infeasible plans	Low-level checks	Low-level time	first time	Timeouts	Feasible plans	Feasible plans	Low-level checks	Low-level time	all time

$Ro$	$Pa$	$Mo$	#	#	#	%	s	#	#	%	#	%	s
Repl	Repl	Repl	1.0	1,925	1,925	82.6	2,000	1.0	2,549	24.2	7,988	88.7	3,748
Grepl	Grepl	Grepl	0.7	1,564	1,564	33.4	1,937	1.0	2,559	27.1	6,872	59.6	3,363
Pre	Pre	Int	0.0	0	42	1.8	663	0.0	2,527	100.0	3,613	72.2	2,691
Pre	Pre	Grepl	0.0	4	4	0.2	661	0.0	2,527	45.3	3,047	70.4	2,582
Pre	Pre	Repl	0.0	4	4	0.2	655	0.0	2,527	45.4	3,035	70.4	2,552
Int	Int	Int	0.0	0	171	3.7	267	0.0	2,755	100.0	5,800	82.8	1,977

9. Experimental results

In the following, the reported numbers of performed low-level feasibility checks indicate distinct low-level reasoning tasks, as we implement a basic cache for low-level check results. In case of a timeout, a run was counted to use the full time, i.e., 36,000 s, in order to avoid that timeouts decrease the reported average time. Precomputation effort (i.e., performing all feasibility checks in advance) is given in Table 4. The other tables do not include precomputation counts and times in the reported values.

We discuss the results of our experiments in two parts, by comparing methods of integration and by comparing levels of integration.

9.1. A comparison of integration methods

The feasibility checks $Po$ and $Mo$ include all objects in the environment as inputs; therefore, the number of potential distinct low-level checks significantly exceeds the number of other checks, rendering precomputation of these feasibility checks infeasible. Therefore, we compare integration methods described in Section 5, in two stages: first we use Int, Grepl, and Repl for all low-level checks (i.e., $L_{P RE} = \emptyset$ ), and then we investigate how the inclusion of Pre affects the results (i.e., for cases where $L_{I NT} \cup L_{P OST}$ does not include all feasibility checks, $L_{P RE} \neq \emptyset$ contains the rest).

9.1.1. Computational effort

Experimental results for comparing these integration methods, in terms of computational efficiency, are summarized in Tables 5 and 6, and Fig. 3.

Fig. 3.

Comparison of computational effort depending on integration method.

According to these results, if we only look at the methods where Pre is not considered in combination with other methods, then we observe that Int by far outperforms Grepl, and Grepl outperforms Repl in Housekeeping and has similar performance in Robotic Manipulation. We illustrate this as follows: $\begin{array}{l} R EPL < G REPL ≪ I NT . \end{array}$ For example, in Housekeeping, Int requires on average 1,019 s to find the first feasible plan of an instance, while Grepl and Repl require 4,948 s and 28,865 s, respectively. For Robotic Manipulation, Int requires on average 267 s for first, while Grepl and Repl require 1,937 s and 2,000 s, respectively.

If we compare methods that involve Pre, we observe that for Grepl and Repl the addition of Pre always increases efficiency significantly. For example, in Housekeeping, 4,948 s is required for first with pure Grepl, while using Pre for $Pe$ and $Ti$ reduces this time to 2,645 s. In Robotic Manipulation, 1,937 s is required with Grepl and 661 s is required when Pre is used for $Ro$ and $Pa$ .

For the combination of Int and Pre the picture is different: in Housekeeping, the usage of Pre increases runtimes slightly from 1,019 s to 1,025 s for first and from 1,112 s to 1,198 s for all; in Robotic Manipulation, the usage of Pre increases runtimes from 267 s to 663 s for first and from 1,977 s to 2,691 s for all. For Housekeeping, the $Po$ check eliminates many infeasible plans, so computation time does not differ much for integration scenarios with Pre. In fact, due to many constraints added as a result of Pre, the computation time may get worse. For Robotic Manipulation, we observe that all methods using Pre for checks $Ro$ and $Pa$ perform very similar – whichever way we integrate $Mo$ . Both effects can be explained by a low relevance of the $Mo$ check on solutions of Robotic Manipulation. Once precomputation has eliminated infeasible plans, few infeasible plans remain for $Mo$ to eliminate so the method of integration makes no big difference, hence all methods with Pre show similar performance. Furthermore, adding all check results of Pre to the Robotic Manipulation domain introduces many irrelevant constraints which can make the search slower, while using Int instead of Pre will only use relevant constraints.

Fig. 4.

Comparison of solution quality depending on integration method.

In summary, the effect of Pre on other methods depends on the relevance of low-level checks on feasibility of plans in the domain. If low-level feasibility checks necessitate a small number of inputs, such that precomputation is a feasible option, then Pre may be a good choice. However, precomputation should be used cautiously with Int, since it can decrease its computational performance by adding many (partially irrelevant) constraints and requiring significantly more memory. $\begin{array}{l} R EPL < {R EPL, P RE}, \\ G REPL < {G REPL, P RE}, \\ I NT \approx {I NT, P RE} (Housekeeping), \\ {I NT, P RE} < I NT (Robotic Manipulation) . \end{array}$

9.1.2. Solution quality

Experimental results for comparing integration methods, in terms of solution quality, are summarized in Tables 5 and 6, and Fig. 4. These results depict solution quality measurements, including the number of feasible plans found. As the number of infeasible plans varies greatly between methods (cf. Table 6), we use a logarithmic scale in Fig. 4.

According to these results (and as discussed in Section 5), the methods Pre and Int do not generate infeasible solutions, as they use all low-level checks already in search. Therefore, we cannot show these zero values on the logarithmic scale (recall that $log (0) = - \infty$ ).

In the Housekeeping domain, we obtain a clear order: Repl produces the fewest number of feasible plans (0.0%), Grepl creating significantly more number of feasible plans (4.5%), and Int producing only feasible plans (100%). Using Pre improves solution quality for Repl and Grepl. As with computational effort, the difference between first and all is not significant from the perspective of solution quality in this domain.

In the Robotic Manipulation domain, Repl is also the worst method (24.2% feasible plans), followed by Grepl (27.1% feasible plans) with Int being the best method (only feasible plans). Similar to the analysis of computational effort, Pre makes Grepl and Repl behave in a similar way and without a clear winner; the precomputed low-level checks manage to eliminate most infeasible solutions already without considering the $Mo$ check.

Based on these results, we can conclude that, with respect to solution quality, Int and ${I NT, P RE}$ always perform the best, followed by non-integrated methods combined with Pre, followed by Grepl and then by Repl: $\begin{array}{l} R EPL < G REPL ⟨\begin{matrix} {G REPL, P RE} \\ {R EPL, P RE} \end{matrix} ⟨\begin{matrix} I NT \\ {I NT, P RE} \end{matrix} . \end{array}$

9.1.3. Additional observations

Number of low-level feasibility checks. When we compare Repl with Repl + Pre in Tables 5 and 6, we see that the number of low-level checks in Housekeeping increases while it decreases for Robotic Manipulation.

In Housekeeping, Repl requires only very little effort in low-level checks. This might seem unintuitive at first; however, both $Pe$ and $Ti$ depend on a small set of inputs. As Repl is not guided by earlier failed checks and the solver generates many similar solutions, similar and infeasible solutions can be discarded without considerable effort by few distinct low-level checks (recall that we use a basic cache).

In Robotic Manipulation, the importance of low-level checks for solution feasibility is not as high as in Housekeeping. Therefore, few infeasible plans are produced without low-level checks, and using Pre in this domain achieves that all runs terminate within the time limit. The checks integrated with Pre do not need to be performed anymore with Repl. Therefore, the number of checks decreases in the Robotic Manipulation domain.

For Grepl, adding Pre decreases the number of low-level checks for both domains, because Grepl is a method where checks guide the search process so no failed check is encountered again.

Difference betweenfirst andall. If we compare the time required to find solutions and the number of infeasible solutions between the two domains in Figs 3 and 4, we observe that in Housekeeping there is only a small difference between first and all, while in Robotic Manipulation initial feasible plans are found much earlier than enumeration ends, and the number of infeasible plans shows a similar difference.

This observation can be explained by the different levels of relevance of low-level checks for these domains. In Housekeeping, it takes significant effort to find an initial solution that does not violate any low-level check, and similar solutions can be found easily afterwards. On the contrary, in Robotic Manipulation, low-level checks play a less important role so finding the next feasible plan is as hard as finding the first feasible plan.

Memory usage. We measured peak memory usage over the whole runtime of each instance. The maximum memory usage for Housekeeping stayed below 2 GB, for Robotic Manipulation below 5 GB.

Memory usage increases drastically when using precomputation, as a larger amount of constraints must be processed by the solver. Apart from that, we could not observe significant differences in memory usage between different methods of integration.

In Housekeeping, memory usage of integration scenarios that include Pre uses around 750 MB (±50) while not using Pre brings down memory usage to 425 MB (±25). Similarly for Robotic Manipulation, using Pre requires on average 1,900 MB (±100) while not using Pre requires merely 600 MB (±50).

9.2. A comparison of levels of integration

According to the results of our experiments to compare methods of integration, we can observe that the most promising two methods are Grepl and Int. With this motivation, to better understand these methods and levels of their integration, we compare all combinations of Grepl and Int for low-level feasibility checks (i.e., $L_{I NT} \cup L_{P OST}$ contains all feasibility checks). Thus these experiments allow us to measure the influence of integrating low-level checking results during reasoning (Int) or only after finding a solution that satisfies all checks registered so far (Grepl). Experimental results are summarized in Tables 7 and 8, and Figs 5 and 6.

Table 7
Housekeeping: Comparison between levels of integration

Integration first all

Quality Efficiency Quality Efficiency

Timeouts Infeasible plans Low-level checks Low-level time first time Timeouts Feasible plans Feasible plans Low-level checks Low-level time all time

$Pe$ $Po$ $Ti$ # # # % s # # % # % s

Grepl Grepl Grepl 2.3 174,148 30,034 70.3 4,948 2.3 8,321 4.5 30,156 69.6 5,013

Grepl Int Grepl 1.3 5 29,386 71.9 3,562 1.3 8,411 99.7 29,615 70.8 3,642

Grepl Grepl Int 1.0 10,795 19,329 77.8 2,800 1.3 8,415 33.4 26,263 79.1 3,390

Int Int Grepl 0.7 4 18,384 68.8 2,393 0.7 8,466 99.8 20,718 66.5 2,644

Grepl Int Int 0.7 3 15,197 78.4 2,371 0.7 8,466 100.0 15,379 76.3 2,452

Int Grepl Int 0.0 0 18,870 66.0 2,240 0.0 8,517 38.7 19,348 64.3 2,345

Int Grepl Grepl 0.7 13,966 19,670 70.4 2,077 0.7 8,466 31.6 19,800 68.4 2,150

Int Int Int 0.0 0 5,873 56.2 1,019 0.0 8,517 100.0 6,118 53.1 1,112

Integration	first	all
Grepl	Grepl	Grepl	2.3	174,148	30,034	70.3	4,948	2.3	8,321	4.5	30,156	69.6	5,013
Grepl	Int	Grepl	1.3	5	29,386	71.9	3,562	1.3	8,411	99.7	29,615	70.8	3,642
Grepl	Grepl	Int	1.0	10,795	19,329	77.8	2,800	1.3	8,415	33.4	26,263	79.1	3,390
Int	Int	Grepl	0.7	4	18,384	68.8	2,393	0.7	8,466	99.8	20,718	66.5	2,644
Grepl	Int	Int	0.7	3	15,197	78.4	2,371	0.7	8,466	100.0	15,379	76.3	2,452
Int	Grepl	Int	0.0	0	18,870	66.0	2,240	0.0	8,517	38.7	19,348	64.3	2,345
Int	Grepl	Grepl	0.7	13,966	19,670	70.4	2,077	0.7	8,466	31.6	19,800	68.4	2,150
Int	Int	Int	0.0	0	5,873	56.2	1,019	0.0	8,517	100.0	6,118	53.1	1,112

Table 8

Robotic manipulation: Comparison between levels of integration

Integration			first					all

			Quality		Efficiency			Quality			Efficiency

			Timeouts	Infeasible plans	Low-level checks	Low-level time	first time	Timeouts	Feasible plans	Feasible plans	Low-level checks	Low-level time	all time

$Ro$	$Pa$	$Mo$	#	#	#	%	s	#	#	%	#	%	s
Grepl	Grepl	Grepl	0.7	1,564	1,564	33.4	1,937	1.0	2,559	27.1	6,872	59.6	3,363
Grepl	Grepl	Int	0.0	156	1,662	53.2	771	0.0	2,589	77.9	5,841	82.1	2,680
Int	Grepl	Int	0.0	56	1,151	44.8	736	0.0	2,922	66.8	7,839	82.7	2,570
Int	Int	Grepl	0.0	188	336	13.3	300	0.3	2,989	33.0	6,971	85.3	2,359
Grepl	Int	Grepl	0.0	111	224	11.3	296	0.0	2,405	33.3	5,818	84.5	2,316
Int	Grepl	Grepl	0.0	120	151	5.6	279	0.0	3,220	81.9	6,084	83.7	2,095
Grepl	Int	Int	0.0	6	169	5.8	272	0.0	2,412	33.7	4,795	83.3	2,064
Int	Int	Int	0.0	0	171	3.7	267	0.0	2,755	100.0	5,800	82.8	1,977

9.2.1. Computational effort

From the results presented in Tables 7 and 8 and Fig. 5, we observe that integrating more low-level checks with Int than with Grepl generally increases efficiency.

The results of Housekeeping show a significant increase in computational efficiency when going from pure Grepl to any integration that uses Int. Combinations where some checks are integrated with Int and some checks are handled with Grepl do not exhibit such a strong difference in performance among one another. However, the difference between mixed integration levels and the full integration of all low-level checks with Int again shows a strong improvement of efficiency.

For Robotic Manipulation there is also a significant increase in computational efficiency when integrating any low-level check with Int, compared to integrating all checks with Grepl. However, between the remaining checks and full integration, the picture is slightly different from the one in Housekeeping. Full integration with Int is the most efficient combination; however, the computational efficiency does not improve much over levels of integration that are mixed between Int and Grepl. This observation can be explained by the structure of low-level checks in this domain: $Mo$ requires motion planning that involves collision checks $Ro$ and $Pa$ . Motion planning in $Mo$ is much more expensive than collision checks. Therefore, integrating only $Mo$ with Int is the slowest level of integration; all other combinations improve upon that.

9.2.2. Solution quality

Figure 6 depicts measurements from Tables 7 and 8 regarding solution quality compared to levels of integration.

Fig. 5.

Comparison of computational effort vs. levels of integration.

Fig. 6.

Comparison of solution quality vs. levels of integration.

In Housekeeping, according to Table 7, integrating only $Po$ with Int leads to a significantly better solution quality for all (99.7% feasible plans) than integrating only $Pe$ (31.6% feasible plans) or only $Ti$ (33.4% feasible plans) with Int. This is intuitively clear because $Po$ subsumes the $Pe$ check (if there is no path considering obstacles, then there is no path without obstacles) and it also subsumes parts of the $Ti$ check (if there is no path considering obstacles, then there is no time estimate for a path). Then we can infer that $Po$ is more significant for solution quality than the other low-level checks of Housekeeping.

We can conversely observe this significance of $Po$ by comparing runs where $Po$ was the only check performed with Grepl: in this case we obtain 38.7% feasible plans for all while handling $Pe$ or $Ti$ with Grepl yields nearly 100.0% feasible plans (in absolute numbers 3 and 14 infeasible plans, respectively).

For Robotic Manipulation, we observe that handling only $Mo$ with Grepl, i.e., not integrating it, yields 33.0% feasible plans; only pure Grepl yields less number of feasible plans. From this observation, we can infer that $Mo$ has the highest significance for solution quality among the Robotic Manipulation low-level checks.

If we compare the variation in number of infeasible plans between both domains, we see that Housekeeping has either small (<30) or large (>10,000) values, while Robotic Manipulation shows a more gradual difference between numbers of infeasible plans. The reason for that is our limit of enumerating only 10,000 plans for all: in Robotic Manipulation most instances have fewer feasible plans, hence also the lower average of feasible plans; on the contrary, several Housekeeping instances have much more than 10,000 feasible plans, and these plans exhibit similar subsequences of actions. Therefore, in Housekeeping we can enumerate many similar plans in a short time, hence once a feasible plan is found, similar feasible plans can be found easily. On the other hand, in Robotic Manipulation, every enumerated plan requires significant additional search effort and additional verification of low-level checks.

The limitation of 10,000 plans for all is necessary to obtain comparable efficiency and solution quality results in both domains, and at the same time it shows the diversity of the properties of our two experimental domains.

10. Related work

We discuss the related work in two parts: related work that integrates task planning with feasibility checks at the representation level, in a robotic domain; and related work that studies the usefulness of integration of task planning with feasibility checks, but at the search level.

Table 9
Related work on integration of task planning with feasibility checks at the representation level

Study Formalism Solver Robotic domain Feasibility checks (Integration method)

Caldiran et al. [4] $C +$ CCalc Mobile manipulation (with concurrency) Collision checks (Int)

Collision free trajectory with moveable objects (Grepl)

Erdem et al. [12] $C +$ CCalc Manipulation (with concurrency) Collision checks (Int)

Collision free trajectory with moveable objects (Grepl)

Havur et al. [34] $C +$ CCalc Tower of Hanoi (manipulation with concurrency) Collision free trajectory for a plan (Grepl)

Aker et al. [1,11] ASP iClingo Housekeeping domain (navigation and manipulation with concurrency) Collision free trajectory without moveable objects (Int)

Temporal constraints over trajectory (Int)

Collision free trajectory with moveable objects (Grepl)

Havur et al. [35] ASP dlvhex Geometric rearrangement (mobile manipulation with concurrency) Reachability and force closure checks (Pre)

Collision free trajectory with moveable objects (Int)

Collision free trajectory for a plan (Grepl)

Dornhege et al. [7] PDDL/M FF/M Manipulation (without concurrency) Collision checks (Int)

Hertle et al. [36] PDDL/M TFD/M Room scanning domain (navigation) Collision free trajectory without moveable objects (Int)

Gaschler et al. [24] STRIPS extension PKS Bartenter domain (manipulation) Collision free trajectory without moveable objects (Pre)

Study	Formalism	Solver	Robotic domain	Feasibility checks (Integration method)
Caldiran et al. [4]	$C +$	CCalc	Mobile manipulation (with concurrency)	Collision checks (Int)
Collision free trajectory with moveable objects (Grepl)
Erdem et al. [12]	$C +$	CCalc	Manipulation (with concurrency)	Collision checks (Int)
Collision free trajectory with moveable objects (Grepl)
Havur et al. [34]	$C +$	CCalc	Tower of Hanoi (manipulation with concurrency)	Collision free trajectory for a plan (Grepl)
Aker et al. [1,11]	ASP	iClingo	Housekeeping domain (navigation and manipulation with concurrency)	Collision free trajectory without moveable objects (Int)
Temporal constraints over trajectory (Int)
Collision free trajectory with moveable objects (Grepl)
Havur et al. [35]	ASP	dlvhex	Geometric rearrangement (mobile manipulation with concurrency)	Reachability and force closure checks (Pre)
Collision free trajectory with moveable objects (Int)
Collision free trajectory for a plan (Grepl)
Dornhege et al. [7]	PDDL/M	FF/M	Manipulation (without concurrency)	Collision checks (Int)
Hertle et al. [36]	PDDL/M	TFD/M	Room scanning domain (navigation)	Collision free trajectory without moveable objects (Int)
Gaschler et al. [24]	STRIPS extension	PKS	Bartenter domain (manipulation)	Collision free trajectory without moveable objects (Pre)

10.1. Integrating task planning with motion planning at the representation level

Recently, there have been some studies [1,4,7,11,12,24,34–36] on integrating discrete task planning and continuous motion planning, at the representation level. For each one of these studies, Table 9 provides information about the representation formalism, reasoner/planner, robotic domain, feasibility checks considered in the study.

The studies [4,12,34] consider the action description language $C +$ [31] to represent robotic domains and use the causal reasoner CCalc [50] to compute hybrid plans. Caldiran et al. [4] studies mobile manipulation where two mobile robots manipulate a payload in a maze-like environment. In this domain, robots need to move concurrently among the obstacles while holding the endpoints of a payload. Two sorts of feasibility checks are considered: collision checks between robots/payloads and the obstacles at every state, and collision avoidance while the robots are moving from one state to another. The former checks are similar to $Pa$ and $Ro$ ; Int is applied to integrate these checks into planning. The latter feasibility check is similar to $Mo$ , but the pose of the payload is not considered since $C +$ and CCalc do not allow external atoms whose inputs include predicate names; so Grepl is applied to integrate this check into task planning. Erdem et al. [12] study robotic manipulation (as in our benchmarks), where two robots change the configurations of multiple payloads with respect to the specified goal. Feasibility checks of [4] (i.e., $Pa$ and $Ro$ ) are considered with similar integration methods. Havur et al. [34] apply hybrid planning to a variation of Tower of Hanoi, where disks have some orientations, have to be carried by two robots, and their initial and goal configurations may be any possible configuration. Here, while the robots rotate a disk they are carrying, there may be some collisions between them. Therefore, the authors consider collision checks between robots, and apply Grepl to integrate these checks in task planning using CCalc.

The studies [1,11,35] formulate the robotic domains in ASP; Aker et al. [1,11] use the ASP solver iClingo [25], whereas Havur et al. [35] use dlvhex to compute hybrid plans. Aker et al. [1,11] study the housekeeping domain (as in our benchmarks), considering the feasibility checks $Pe$ , $Ti$ and $Po$ . Int is applied for $Ti$ and $Pe$ . Since iClingo (like CCalc) does not allow external atoms whose inputs include predicate names, Int could not be applied for $Po$ ; instead, Grepl is applied to integrate $Po$ into task planning. Havur et al. [35] apply hybrid planning to rearrangement of objects on a cluttered surface with a mobile manipulator. Authors consider reachability of the robot arm, finding a proper location for the mobile base and feasibility of grasps using Pre; and collision checks among objects and the robot arm, collision free trajectories for placing and/or pushing objects among movable obstacles utilizing Int, since dlvhex allows external atoms whose inputs include predicate names. Furthermore, Grepl is used to ensure proper propagation of object locations from one state to another.

The studies [7,36] extend the planning domain description language PDDL [23] to support external atoms, and modify the planners FF [37] and TFD [21] accordingly to compute hybrid plans; the extended PDDL is called PDDL/M, the extended versions of FF and TFD are called FF/M and TFD/M, respectively. Dornhege et al. [7] use PDDL/M and FF/M for hybrid planning in a manipulation domain where a robot aims to transfer objects from a table to a shelf. Depending on the continuous grasp direction, collisions may occur. The authors thus integrate collision checks into task planning; they use Int method for that. Hertle et al. [36] use PDDL/M and TFD/M for hybrid planning in a room scanning domain where a robot aims to scan all target locations in every room in a minimal amount of time. Checking whether there is collision-free path from one location to another one is integrated into task planning, using the Int method.

Gaschler et al. [24] use the PKS planner [57,58] to apply hybrid planning to a manipulation domain, where a bartender robot detects bottles located on the bar and removes all empty bottles to a special dishwasher location at the right of the robot. The language of PKS is an extension of STRIPS [22]. To be able to grasp the bottles without any collisions, the feasibility check of collision-free trajectory is integrated in task planning. Due to the small number of bottles, the authors use Pre method for integration.

In the studies above, we see various applications of hybrid planning. However, there is no experimental evaluation over different integration methods.

10.2. A systematic analysis of integration at the search level

Recently, Lagriffoul et al. [43] have investigated the usefulness of integration of task planning with geometric reasoning at the search level. In that study, geometric checks are embedded into symbolic search trees (for task planning) up to some depth D of the symbolic search tree. After depth D of the symbolic search tree, no geometric reasoning is considered until a goal state is reached. When a goal state is reached then the plan’s feasibility is checked; if the plan is not feasible, then the search over the symbolic search tree continues. In such a platform, levels of integration is characterized by this depth. Effects of level of integration is studied by measuring the number of visited symbolic search states and the number of visited geometric configurations until a feasible plan is found.

For their experiments, the authors modify the planner JShop2 [53] according to the experimental framework described above. They consider a robotic domain that consists of picking cups from a table and putting them into a box on the table. The problem instances they experiment with involve two or three cups; the maximum makespan for a task plan (and thus maximum value for D) is 8 and the maximum threshold for the number of geometric configurations is 200.

From the results of their experiments, the authors make several interesting observations. In particular, they observe that, as the value of D changes, there is a trade-off between the number of visited symbolic search states and the number of visited geometric configurations until a feasible plan is found. They suggest (a) a tight integration (i.e., a larger D) for domains with lower geometric success rate (i.e., the ratio of the average branching factor of the symbolic search tree with geometric checks to the average branching factor of the symbolic search tree without any geometric search), and (b) no tight integration for domains with high geometric success rate.

Lagriffoul et al.’s observations (a) are inline with our experimental results for interleaved method (Int). According to our results, if a geometric check plays a significant role on finding a feasible plan, then it is better to interleave this check in task planning. Indeed, as discussed above, the geometric check $Po$ plays a significant role on the feasibility of a plan in Housekeeping, and integrating $Po$ only with Int, leads to a significantly better solution quality (99.7% feasible plans, Table 7).

Lagriffoul et al.’s observations (b), on the other hand, do not confirm with our experimental results for Int. According to our results, it is still better to interleave a geometric check in task planning, even if it does not play as much significant role on finding a feasible plan. Indeed, although the geometric check $Pe$ plays a less significant role on the feasibility of a plan in Housekeeping compared to $Po$ (31.7% feasible plans, Table 7), integrating this check with Int only, leads to a significant improvement on computational efficiency (reducing the computation time from 4,948 s to 2,077 s, Table 7). Similar observations are made for the Manipulation domain as well, suggesting a tight integration with Int.

The different observations are not surprising, considering that the experiments are conducted with two different integration approaches (search level vs representation level). Also, in Lagriffoul et al.’s analysis, experiments are performed over one robotic domain and over instances with short makespans, effect of levels of integration on computational efficiency (computation time) is not considered, and effects of various combinations of levels of integration for feasibility checks are not investigated.

11. Discussion and conclusion

We have identified four different methods of integrating high-level task planning with low-level feasibility checks, and introduced a computational method for systematically analyzing the efficacy of these methods of integration through a comprehensive empirical study. Our method also involves a detailed study of levels of integration by considering various uses of combinations of methods. Based on this systematic approach, we have performed experiments in housekeeping and robotic manipulation domains with different feasibility checks. Results of these experiments suggest the following conclusions.

If low-level feasibility checks have a high influence on plan feasibility, then using full interleaved reasoning (Int) is the most promising approach. Int not only consistently achieves the best performance with respect to computation times, but also can enumerate most number of solutions compared to other approaches, since Int uses only those low-level checks which are necessary (they are computed on demand) and therefore does not overload the solver with redundant information (as Pre does). Furthermore, Int considers results of failed feasibility checks (as constraints) in the search process, and thereby never picks an action where it is known that the action will violate a low-level feasibility check.

If low-level feasibility checks necessitate a small number of inputs, such that precomputation is a feasible option, then Pre may be a good choice. However, precomputation should be used cautiously with Int, since it can decrease its computational performance by adding many (partially irrelevant) constraints and requiring significantly more memory.

The Repl approach performs the worst, because nothing guides the search into the direction of a feasible solution; Repl is not robust and enumerates many infeasible solutions.

If both Pre and Int are not possible (e.g., if the state of inputs is large, and additionally we have to use a certain planner that does not support interleaved computation) then Grepl should be used. This approach is robust but less efficient than Int, as the integration is less tight than with Int. Nevertheless, it is a very robust approach as it is guided by its wrong choices – we can think of the use of constraints that are obtained from failed low-level feasibility checks and added to the planning problem description, as an approach of “learning from its mistakes”.

Footnotes

Acknowledgement

This work is partially supported by TUBITAK Grants 111E116, 113M422, 114E491 (ChistEra COACHES), 114E430.

P. Schüller’s work was carried out while visiting the Cognitive Robotics Lab at Sabancı University.

Housekeeping domain description

The Housekeeping domain used in our experiments is essentially the one described in [1,11]. Let us briefly review the formulation of this domain in ASP.

Planning problem: Input and output. An initial state of a planning problem instance is described as a set of facts using simple fluents of the forms

$at (t h, x, y, t)$ (“robot/object $t h$ is at location $(x, y)$ at time step t”) and

$connected (r, e, t)$ (“robot r is attached to the endpoint e of an object at time step t”)

for

t = 0

The goal is described as a set of constraints $\begin{array}{l} \leftarrow not tidy (maxstep), \\ \leftarrow not free (maxstep), \\ \leftarrow not elapsed_time (maxtime, maxstep) \end{array}$ using auxiliary fluents of the forms

$tidy (t)$ (“the house is tidy at time step t”),

$free (t)$ (“no robot is attached to any object, so they are all free, at time step t”) and

$elapsed_time (g, t)$ (“estimated elapsed time from time step 0 till time step t is g time units”)

where

maxstep

is the makespan and

maxtime

is the estimated total plan duration. The auxiliary fluents are defined in terms of the simple fluents as in [1,11]. The definition of

tidy

utilizes commonsense knowledge extracted from the commonsense knowledge base ConceptNet [48] by means of an external atom.

A plan is a sequence of actions of the forms

Once a maximum makespan $maxmakespan$ for a plan is specified, an optimal plan of length $maxstep$ is computed by trying to find a plan using the solver dlvhex with $maxstep = 1, 2, 3, \dots, maxmakespan$ .

Preconditions and direct effects of actions. We describe direct effects and preconditions of the action $goto (r, x, y, t_{a})$ by the following rules: $\begin{array}{l} at (r, x, y, t_{a} + 1) \leftarrow goto (r, x, y, t_{a}), \\ \leftarrow goto (r, x, y, t_{a}), occupied (x, y), \\ \leftarrow goto (r, x, y, t_{a}), at (r, x, y, t_{a}) . \end{array}$ The first rule above describes the change in the robot’s location as a direct effect of this action, whereas the other rules describe the preconditions of this action (i.e., a robot can neither move to an occupied location nor to its current location).

The direct effects and preconditions of the action $attach$ are defined by the following rules: $\begin{array}{l} connected (r, e, t_{a} + 1) \leftarrow attach (r, t_{a}), \\ attach_point (r, e, t_{a}), \\ \leftarrow attach (r, t_{a}), connected (r, e, t_{a}), \\ \leftarrow attach (r, t_{a}), attach_point (r, e, t_{a}), \\ different_loc (r, e, t_{a}) . \end{array}$ The first rule above described that the robot is connected to the endpoint of the object after the execution of this action. The other rules describe the preconditions of executing this action (i.e., a robot cannot attach to an object if it is already connected to some object, or if the object is at a remote location different from the location of the robot).

Similarly the action $detach$ is described by the following rules: $\begin{array}{l} \neg connected (r, e, t_{a} + 1) \leftarrow detach (r, t_{a}), \\ connected (r, e, t_{a}), \\ \leftarrow detach (r, t_{a}), free_robot (r, t_{a}) . \end{array}$

Ramifications. Indirect effects of actions can be defined by rules as well. For instance, an indirect effect of the action $attach (r, t_{a})$ with $attach_point (r, e, t_{a})$ is that the location of the endpoint e is equal to the location of the robot r. This ramification can be expressed by the rules: $\begin{array}{l} at (e, x, y, t) \leftarrow connected (r, e, t), at (r, x, y, t) . \end{array}$ Note that these rules also describe a ramification of the $goto (r, x, y, t_{a})$ action.

Another ramification of the $goto (r, x, y, t_{a})$ action is that if a robot/object is at a location that it is not anywhere else: $\begin{array}{l} \neg at (t h, x, y, t) \leftarrow at (t h, x_{1}, y_{1}, t) (x \neq x_{1}), \\ \neg at (t h, x, y, t) \leftarrow at (t h, x_{1}, y_{1}, t) (y \neq y_{1}) . \end{array}$

Commonsense law of inertia. We describe the commonsense law of inertia by the following rules: $\begin{array}{l} at (t h, x, y, t_{a} + 1) \leftarrow not \neg at (t h, x, y, t_{a} + 1), \\ at (t h, x, y, t_{a}), \\ \neg at (t h, x, y, t_{a} + 1) \leftarrow not at (t h, x, y, t_{a} + 1), \\ \neg at (t h, x, y, t_{a}), \\ connected (r, e, t_{a} + 1) \leftarrow \\ not \neg connected (r, e, t_{a} + 1), \\ connected (r, e, t_{a}), \\ \neg connected (r, e, t_{a} + 1) \leftarrow \\ not connected (r, e, t_{a} + 1), \\ \neg connected (r, e, t_{a}) . \end{array}$

State constraints. The state constraint that no two robots/objects occupy the same location at any time step can be expressed by the following rules: $\begin{matrix} \leftarrow at (e_{1}, x, y, t), at (e_{2}, x, y, t) (e_{1} < e_{2}) . \end{matrix}$

We can describe the constraint that a robot cannot be attached to multiple objects at the same time as follows: $\begin{array}{l} \leftarrow connected (r, e_{1}, t), \\ connected (r, e_{2}, t) (e_{1} < e_{2}) . \end{array}$

We can describe the state constraint that the endpoints of the objects should be aligned horizontally or vertically as follows: $\begin{array}{l} \leftarrow at (e_{1}, x_{1}, y_{1}, t), at (e_{2}, x_{2}, y_{2}, t), \\ belongs (e_{1}, o), belongs (e_{2}, o) \\ (e_{1} < e_{2}, {(x_{1} - x_{2})}^{2} + {(y_{1} - y_{2})}^{2} \neq 1) . \end{array}$

Concurrency constraints. A robot cannot simultaneously move, and attach or detach: $\begin{array}{l} \leftarrow goto (r, x, y, t_{a}), attach (r, t_{a}), \\ \leftarrow goto (r, x, y, t_{a}), detach (r, t_{a}) . \end{array}$

Temporal constraints. To be able to ensure that the elapsed time is less than a given specific time unit, we introduce further auxiliary fluents of the form $robot_time (r, d_{e}, t_{a} + 1)$ (“estimated time for a robot r to complete its action started at time step $t_{a}$ id $d_{e}$ time units”).

For $goto (r, x, y, t_{a})$ action, among all possible values for its duration, $\begin{array}{l} robot_time (r, d_{e}, t_{a} + 1) \\ \lor \neg robot_time (r, d_{e}, t_{a} + 1) \leftarrow \\ goto (r, x, y, t_{a}), \\ \neg robot_time (r, d_{1}, t) \leftarrow \\ robot_time (r, d_{2}, t) (d_{1} \neq d_{2}) . \end{array}$ The duration of the action is estimated over the length of a continuous trajectory from the robot’s current location to $(x, y)$ . The estimated duration is computed externally using a motion planner and the result of this external computation is embedded into the following constraint via the external atom $& time_estimate [goto, a t, robot_time] ()$ to define the duration of the $goto (r, x, y, t_{a})$ action: $\begin{matrix} \leftarrow not & time_estimate [goto, at, robot_time] () . \end{matrix}$ Note that this constraint realizes the low-level check $Ti$ .

For other actions, we define their durations as constants: $\begin{array}{l} robot_time (r, 1, t_{a} + 1) \leftarrow detach (r, t_{a}), \\ robot_time (r, 1, t_{a} + 1) \leftarrow attach (r, t_{a}) . \end{array}$

Once durations of each action is defined, we accumulate the maximum of the durations of actions executed at time step $t_{a}$ to find the elapsed time so far at $t_{a} + 1$ . As noted above, the elapsed time is denoted by an auxiliary fluent of the form $elapsed_time (g, t_{a})$ . This fluent is defined recursively as follows: $\begin{array}{l} nmax_robot_time (d_{1}, t) \leftarrow robot_time (r_{1}, d_{1}, t), \\ robot_time (r_{2}, d_{2}, t) (d_{1} < d_{2}), \\ elapsed_time (g_{1} + d, t_{a} + 1) \leftarrow \\ elapsed_time (g_{1}, t_{a}), \\ robot_time (r, d, t_{a} + 1), \\ not nmax_robot_time (d, t_{a}) . \end{array}$

Geometric constraints. As described in Section 2, the following constraint ensures that, for each time step and each robot, there is a collision-free motion plan from the location given by $at$ at step t to the location given by $goto$ at step t. $\begin{matrix} \leftarrow not & path_exists [goto, at] () . \end{matrix}$ Note that this geometric constraint utilizes the low-level feasibility check $Pe$ .

The following geometric constraint utilizes the low-level feasibility check $Po$ . $\begin{matrix} \leftarrow not & path_exists_obstacles [goto, at] () . \end{matrix}$ In addition to the functionality provided by path_ exists, the function $path_exists_obstacles$ consider obstacles specified in predicate $at$ in motion planning. This makes the check more complex and dependent on a larger set of fluents in the plan candidate, therefore caching is not as effective and precomputation is not feasible.

Robotic manipulation domain description

The Manipulation domain used in our experiments is essentially the one described in [12]. Let us briefly review the formulation of this domain in ASP.

Planning problem: Input and output. An initial state of a planning problem instance is described by a set of facts using the simple fluents of the form

We specify the goal by constraints using auxiliary fluents. For example, consider the goal that payload 2 is located at $(3, 2)$ with endpoint 3 and at $(8, 2)$ with endpoint 4 and that no robot is holding any object. This goal is described as follows: $\begin{array}{l} \leftarrow not goal, \\ goal \leftarrow xpay (1, 3, t), ypay (1, 2, t), xpay (2, 8, t), \\ ypay (2, 2, t), not holdingsth (t), \\ holdingsth (t) \leftarrow holding (r, p, t) . \end{array}$

A plan is a sequence of actions of the forms

Preconditions and direct effects of actions. The direct effects of moving can be defined by the following rules: $\begin{array}{l} xpos (r, x_{1} + n, t_{a} + 1) \leftarrow move (r, right, n, t_{a}), \\ xpos (r, x_{1}, t_{a}), \\ xpos (r, x_{1} - n, t_{a} + 1) \leftarrow move (r, left, n, t_{a}), \\ xpos (r, x_{1}, t_{a}), \\ ypos (r, y_{1} + n, t_{a} + 1) \leftarrow move (r, up, n, t_{a}), \\ ypos (r, y_{1}, t_{a}), \\ ypos (r, y_{1} - n, t_{a} + 1) \leftarrow move (r, down, n, t_{a}), \\ ypos (r, y_{1}, t_{a}) . \end{array}$

A robot cannot move if it is the only one holding a payload. This precondition is described by the following constraint $\begin{array}{l} \leftarrow mover (r, t_{a}), holding (r, p, t_{a}), \\ samePayload (p, p_{1}), \\ # count {r_{1} : holding (r_{1}, p_{1}, t_{a})} ⩽ 0 \end{array}$ that utilizes the auxiliary fluents $mover (r, t)$ (“robot r moves at time step t”) and $samePayload (p, p_{1})$ (“p and $p_{1}$ are the endpoints of the same payload”) defined as follows: $\begin{array}{l} mover (r, t_{a}) \leftarrow move (r, d, n, t_{a}), \\ samepayload (2 k, 2 k + 1), \\ samepayload (2 k + 1, 2 k) . \end{array}$

We define the direct effects and preconditions of a robot’s action of picking up an endpoint of a payload as follows: $\begin{array}{l} holding (r, p, t_{a} + 1) \leftarrow pick (r, p, t_{a}), \\ \leftarrow holding (r, p, t_{a}), pick (r, p, t_{a}), \\ \leftarrow pick (r, p, t_{a}), xpos (r, x, t_{a}), \\ xpay (p, x_{1}, t_{a}) (x \neq x_{1}), \\ \leftarrow pick (r, p, t_{a}), ypos (r, y, t_{a}), \\ ypay (p, y_{1}, t_{a}) (y \neq y_{1}) . \end{array}$

We define the direct effects and preconditions of a robot’s action of dropping the endpoint of a payload that it is holding, as follows: $\begin{array}{l} \neg holding (r, p, t_{a} + 1) \leftarrow drop (r, t_{a}), \\ holding (r, p, t_{a}), \\ \leftarrow drop (r, t_{a}), # count {p : holding (r, p, t_{a})} ⩽ 0 . \end{array}$

Ramifications. The position of a payload’s endpoint p is the same as the position of the robot r who is holding p. Representing this statement formally also helps describe the ramifications of actions (e.g., whenever a robot moves to a new location then the position of the payload it is holding also changes accordingly). Here are the rules representing these ramifications: $\begin{array}{l} xpay (p, x, t) \leftarrow holding (r, p, t), xpos (r, x, t), \\ ypay (p, y, t) \leftarrow holding (r, p, t), ypos (r, y, t) . \end{array}$ Furthermore, holding an endpoint of a payload entails that the robot does not hold any other endpoint: $\begin{array}{l} \neg holding (r, p_{2}, t) \leftarrow \\ holding (r, p_{1}, t) (p_{1} \neq p_{2}) . \end{array}$

Commonsense law of inertia. We define inertia for fluents $holding$ , $xpos$ , $ypos$ , $xpay$ , and $ypay$ by rules similar to the ones. For efficiency reasons we use true negation only for the fluent $holding$ : $\begin{array}{l} holding (r, p, t_{a} + 1) \leftarrow holding (r, p, t_{a}), \\ not \neg holding (r, p, t_{a} + 1), \\ \neg holding (r, p, t_{a} + 1) \leftarrow \neg holding (r, p, t_{a}), \\ not holding (r, p, t_{a} + 1) . \end{array}$

Concurrency constraints. We disallow concurrency of picking, dropping, and moving. $\begin{array}{l} picker (r, t_{a}) \leftarrow pick (r, p, t_{a}), \\ \leftarrow mover (r, t_{a}), picker (r, t_{a}), \\ \leftarrow mover (r, t_{a}), drop (r, t_{a}) . \end{array}$

State constraints. We require that payloads are located horizontally or vertically on the grid. $\begin{array}{l} \leftarrow not beingCarried (k, t), \\ # count {o : orientation (k, o, t)} ⩽ 0, \end{array}$ where the auxiliary fluent $beingCarried (k, t)$ is defined as follows: $\begin{array}{l} beingCarried (k, t) \leftarrow holding (r, p, t), \\ endpointOf (k, p), holding (r, p_{1}, t), \\ endpointOf (k, p_{1}) (p < p_{1}) . \end{array}$

Furthermore we ensure that robots do not hold different payloads at the same time, and that a payload is held by two robots or by none. $\begin{array}{l} \leftarrow holding (r, p_{1}, t), samePayload (p_{1}, p_{2}), \\ # count {r_{2} : holding (r_{2}, p_{2}, t)} ⩽ 0 \\ (p_{1} \neq p_{2}), \\ \leftarrow holding (r, p_{1}, t), \\ holding (r, p_{2}, t) (p_{1} < p_{2}) . \end{array}$

Geometric constraints. We require that payloads do not overlap with each other. Note that this constraint excludes many cases where low-level feasibility checks (i.e., collision checks) would fail. $\begin{array}{l} \leftarrow orientation (k_{1}, v, t), not beingCarried (k_{1}, t), \\ \min_{X} (k_{1}, x, t), \min_{Y} (k_{1}, y_{1}, t), \\ orientation (k_{2}, v, t), \\ not beingCarried (k_{2}, t), \\ \min_{X} (k_{2}, x, t), \min_{Y} (k_{2}, y_{2}, t) \\ (1 ⩽ k_{1} < k_{2} ⩽ maxP, \\ abs (y_{2} - y_{1}) < lengthP), \\ \leftarrow orientation (k_{1}, h, t), not beingCarried (k_{1}, t), \\ \min_{X} (k_{1}, x_{1}, t), \min_{Y} (k_{1}, y, t), \\ orientation (k_{2}, h, t), \\ not beingCarried (k_{2}, t), \\ \min_{X} (k_{2}, x_{2}, t), \min_{Y} (k_{2}, y, t) \\ (1 ⩽ k_{1} < k_{2} ⩽ maxP, \\ abs (x_{2} - x_{1}) < lengthP), \\ \leftarrow orientation (k_{1}, v, t), not beingCarried (k_{1}, t), \\ \min_{X} (k_{1}, x_{1}, t), \min_{Y} (k_{1}, y_{1}, t), \\ orientation (k_{2}, h, t), not beingCarried (k_{2}, t), \\ \min_{X} (k_{2}, x_{2}, t), \min_{Y} (k_{2}, y_{2}, t) \\ (k_{1} \neq k_{2}, x_{2} ⩽ x_{1} ⩽ x_{2} + lengthP, \\ y_{1} ⩽ y_{2} ⩽ y_{1} + lengthP) . \end{array}$ Here the auxiliary fluents are defined as follows: $\begin{array}{l} \min_{X} (k, x_{1}, t) \leftarrow endpointOf (k, p), \\ endpointOf (k, p_{1}), \\ xpay (p, x_{1}, t), xpay (p_{1}, x_{2}, t) \\ (p \neq p_{1}, x_{1} ⩽ x_{2}), \\ \min_{Y} (k_{1}, y_{1}, t) \leftarrow endpointOf (k, p), \\ endpointOf (k, p_{1}), \\ ypay (p, y_{1}, t), ypay (p_{1}, y_{2}, t) \\ (p \neq p_{1}, y_{1} ⩽ y_{2}), \\ orientation (k, h, t) \leftarrow ypay (p, y_{1}, t), \\ ypay (p_{1}, y_{1}, t), endpointOf (k, p), \\ endpointOf (k, p_{1}) (p < p_{1}), \\ orientation (k, v, t) \leftarrow xpay (p, x_{1}, t), \\ xpay (p_{1}, x_{1}, t), endpointOf (k, p), \\ endpointOf (k, p_{1}) (p < p_{1}) . \end{array}$

To make physical feasibility more likely, we restrict movements of robots when holding the payload in a non-axis-aligned way: the robots do not have to hold the payloads from their endpoints exactly but “sufficiently close to” the endpoints within some “tolerance” value. $\begin{array}{l} \leftarrow xpay (p_{1}, x_{1}, t), xpay (p_{2}, x_{2}, t), \\ ypay (p_{1}, y_{1}, t), ypay (p_{2}, y_{2}, t), \\ samePayload (p_{1}, p_{2}), \\ \leftarrow xpay (p_{1}, x_{1}, t), xpay (p_{2}, x_{2}, t), \\ ypay (p_{1}, y_{1}, t), ypay (p_{2}, y_{2}, t), \\ samePayload (p_{1}, p_{2}), \end{array}$ where ${(x_{1} \cdot x_{2})}^{2} + {(y_{1} \cdot y_{2})}^{2} > {lengthP}^{2} + tolerance$ and $p_{1} < p_{2}$ .

The low-level feasibility check $Ro$ is ensured by the following constraint: $\begin{matrix} \leftarrow not & robot_collision_free [xpos, ypos, dir] () . \end{matrix}$ Here the external function $robot_collision_free$ gets as input the set of atoms $xpos (r, x, t)$ , $ypos (r, y, t)$ , and $dir (r, d, t)$ that are true in the current plan candidate, extracts for each time step t all coordinate/direction triples $(x, y, d)$ of a robot r; and returns true if and only if for each time step the specified robot poses are collision-free with other robot poses and with the environment.

Similarly, the following constraint realizes $Pa$ : $\begin{matrix} \leftarrow not & payload_collision_free [xpay, ypay] () . \end{matrix}$

Finally the $Mo$ low-level check is realized in the following constraint $\begin{array}{l} \leftarrow not motion_feasible [xpos, ypos, dir, \\ xpay, ypay, holding, move] () . \end{array}$ From the atoms in the extensions of predicates $xpos$ , $ypos$ , $dir$ , $xpay$ , $ypay$ , $holding$ , $move$ , the low-level feasibility check function $motion_feasible$ extracts at every time step $t_{a}$ the positions and orientations of the robots, the positions of the payloads, which robot is holding which payload, and which robot is moving to where. This information provides the initial configuration and the goal configuration for a motion planner; note that the information extracted from $holding$ fluent determines whether motion planning should be done with two robots carrying a payload, with one robot, or with two robots that are not connected to payloads. Then, using a motion planner, $motion_feasible$ returns true if the robots’ move actions are feasible with respect to the motion planner’s output.

Experimental results with the ASP solver Clasp

We have performed some experiments using the ASP solver Clasp with Gringo, over the housekeeping domain (with the feasibility checks $Pe$ and $Ti$ ) and the robotic manipulation domain (with the feasibility checks $Ro$ and $Pa$ ), to compare Pre with Grepl. Experiments were performed one run on a Linux server with 32 2.4 GHz Intel^® E5-2665 CPU cores and 64 GB memory.

The experimental results are summarized in Table 10. Due to the more coarse interface of Clasp compared to dlvhex, only some parts of the domains could be modeled; thus, some integration methods could not be tested. However, the results confirm the conclusions given in Section 11 suggested by the experimental results presented in Section 9.

References

[1]

Aker,

Patoglu and

Erdem, Answer set programming for reasoning with semantic knowledge in collaborative housekeeping robotics, in: Proc. of SYROCO, 2012.

[2]

Brewka,

Eiter and

Truszczynski, Answer set programming at a glance, Commun. ACM54(12) (2011), 92–103.

[3]

Bylander, The computational complexity of propositional STRIPS planning, Artificial Intelligence69(1–2) (1994), 165–204.

[4]

Caldiran,

Haspalamutgil,

Ok,

Palaz,

Erdem and

Patoglu, Bridging the gap between high-level reasoning and low-level control, in: Proc. of LPNMR, 2009.

[5]

Choset,

K.M.

Lynch,

Hutchinson,

G.A.

Kantor,

Burgard,

L.E.

Kavraki and

Thrun, Principles of Robot Motion: Theory, Algorithms, and Implementations, MIT Press, 2005.

[6]

Dimopoulos,

Nebel and

Koehler, Encoding planning problems in nonmonotonic logic programs, in: Proc. of ECP, 1997.

[7]

Dornhege,

Eyerich,

Keller,

Trüg,

Brenner and

Nebel, Semantic attachments for domain-independent planning systems, in: Proc. of ICAPS, 2009.

[8]

Eiter,

Fink,

Ianni,

Krennwallner,

Redl and

Schüller, A model building framework for answer set programming with external computations, Theory and Practice of Logic Programming (2015), to appear.

[9]

Eiter,

Ianni,

Schindlauer and

Tompits, A uniform integration of higher-order reasoning and external evaluations in answer-set programming, in: Proc. of IJCAI, 2005.

10.

[10]

Eiter,

Ianni,

Schindlauer and

Tompits, Effective integration of declarative rules with external evaluations for semantic-web reasoning, in: Proc. of ESWC, 2006.

11.

[11]

Erdem,

Aker and

Patoglu, Answer set programming for collaborative housekeeping robotics: Representation, reasoning, and execution, Intelligent Service Robotics5 (2012), 275–291.

12.

[12]

Erdem,

Haspalamutgil,

Palaz,

Patoglu and

Uras, Combining high-level causal reasoning with low-level geometric reasoning and motion planning for robotic manipulation, in: Proc. of ICRA, 2011.

13.

[13]

Erdem,

Haspalamutgil,

Patoglu and

Uras, Causality-based planning and diagnostic reasoning for cognitive factories, in: Proc. 17th IEEE Int. Conf. Emerging Technologies and Factory Automation (ETFA), 2012.

14.

[14]

Erdem,

D.G.

Kisa,

Oztok and

Schüller, A general formal framework for pathfinding problems with multiple agents, in: Proc. of AAAI, 2013.

15.

[15]

Erdem,

Patoglu and

Z.G.

Saribatur, Integrating hybrid diagnostic reasoning in plan execution monitoring for cognitive factories with multiple robots, in: Proc. of ICRA, 2015. Finalist for Best Conference Paper Award, Finalist for Best Cognitive Robotics Paper Award.

16.

[16]

Erdem,

Patoglu,

Z.G.

Saribatur,

Schüller and

Uras, Finding optimal plans for multiple teams of robots through a mediator: A logic-based approach, Theory and Practice of Logic Programming13(4–5) (2013), 831–846.

17.

[17]

Erdem,

Patoglu and

Schüller, Levels of integration between low-level reasoning and task planning, in: Proc. AAAI 2013 Workshop on Intelligent Robotic Systems, 2013.

18.

[18]

Erdem,

Patoglu and

Schüller, A systematic analysis of levels of integration between low-level reasoning and task planning, in: Proc. ICRA 2013 Workshop on Combining Task and Motion Planning, 2013.

19.

[19]

Erdem,

Patoglu and

Schüller, A systematic analysis of levels of integration between high-level task planning and low-level feasibility checks, in: Proc. of RCRA, 2014.

20.

[20]

Erol,

D.S.

Nau and

V.S.

Subrahmanian, Complexity, decidability and undecidability results for domain-independent planning, Artificial Intelligence76(1–2) (1995), 75–88.

21.

[21]

Eyerich,

Mattmüller and

Röger, Using the context-enhanced additive heuristic for temporal and numeric planning, in: Proc. of ICAPS, 2009.

22.

[22]

R.E.

Fikes and

N.J.

Nilsson, STRIPS: A new approach to the application of theorem proving to problem solving, in: Proc. of IJCAI, 1971.

23.

[23]

Fox and

Long, PDDL2.1: An extension to PDDL for expressing temporal planning domains, J. Artif. Intell. Res. (JAIR)20 (2003), 61–124.

24.

[24]

Gaschler,

R.P.A.

Petrick,

Giuliani,

Rickert and

Knoll, KVP: A knowledge of volumes approach to robot task planning, in: Proc. of IROS, 2013.

25.

[25]

Gebser,

Kaminski,

Kaufmann,

Ostrowski,

Schaub and

Thiele, Engineering an incremental ASP solver, in: Proc. of ICLP, 2008.

26.

[26]

Gebser,

Kaufmann,

Neumann and

Schaub, Clasp: A conflict-driven answer set solver, in: Proc. of LPNMR, 2007.

27.

[27]

Gebser,

Schaub and

Thiele, Gringo: A new grounder for answer set programming, in: Proc. of LPNMR, 2007.

28.

[28]

Gelfond and

Lifschitz, The stable model semantics for logic programming, in: Proc. of ICLP, 1988.

29.

[29]

Gelfond and

Lifschitz, Classical negation in logic programs and disjunctive databases, New Generation Computing9 (1991), 365–385.

30.

[30]

Gelfond and

Lifschitz, Action languages, Electronic Transactions on Artificial Intelligence2 (1998), 193–210.

31.

[31]

Giunchiglia,

Lee,

Lifschitz,

McCain and

Turner, Nonmonotonic causal theories, Artificial Intelligence (AIJ)153(1–2) (2004), 49–104.

32.

[32]

Gravot,

Cambon and

Alami, aSyMov: A planner that deals with intricate symbolic and geometric problems, in: Robotics Research the Eleventh International Symposium, Springer Tracts in Advanced Robotics, Vol. 15, 2005.

33.

[33]

Hauser and

J.-C.

Latombe, Integrating task and PRM motion planning: Dealing with many infeasible motion planning queries, in: Workshop on Bridging the Gap Between Task and Motion Planning at ICAPS, 2009.

34.

[34]

Havur,

Haspalamutgil,

Palaz,

Erdem and

Patoglu, A case study on the tower of hanoi challenge: Representation, reasoning and execution, in: Proc. of ICRA, 2013.

35.

[35]

Havur,

Ozbilgin,

Erdem and

Patoglu, Geometric rearrangement of multiple movable objects on cluttered surfaces: A hybrid reasoning approach, in: Proc. of ICRA, 2014.

36.

[36]

Hertle,

Dornhege,

Keller and

Nebel, Planning with semantic attachments: An object-oriented view, in: Proc. of ECAI, 2012.

37.

[37]

Hoffmann and

Nebel, The FF planning system: Fast plan generation through heuristic search, J. Artif. Intell. Res.14 (2001), 253–302.

38.

[38]

L.P.

Kaelbling and

Lozano-Pérez, Hierarchical task and motion planning in the now, in: Proc. of ICRA, 2011.

39.

[39]

L.P.

Kaelbling and

Lozano-Pérez, Integrated task and motion planning in belief space, International Journal of Robotics Research32(9–10) (2013), 1194–1227.

40.

[40]

H.A.

Kautz and

Selman, Planning as satisfiability, in: Proc. of ECAI, 1992.

41.

[41]

KuffnerJr. and

LaValle, RRT-connect: An efficient approach to single-query path planning, in: Proc. of ICRA, Vol. 2, 2000.

42.

[42]

Lagriffoul,

Dimitrov,

Bidot,

Saffiotti and

Karlsson, Efficiently combining task and motion planning using geometric constraints, International Journal of Robotics Research33(14) (2014), 1726–1747.

43.

[43]

Lagriffoul,

Karlsson,

Bidot and

Saffiotti, Combining task and motion planning is not always a good idea, in: Proc. RSS 2013 on Combined Robot Motion Planning and AI Planning for Practical Applications, 2013.

44.

[44]

S.M.

LaValle, Planning Algorithms, Cambridge University Press, Cambridge, UK, 2006, available at: http://planning.cs.uiuc.edu/.

45.

[45]

Lifschitz, Action languages, answer sets and planning, in: The Logic Programming Paradigm: A 25-Year Perspective, Springer Verlag, 1999, pp. 357–373.

46.

[46]

Lifschitz, Answer set programming and plan generation, Artificial Intelligence138 (2002), 39–54.

47.

[47]

Lifschitz, What is answer set programming?, in: Proc. of AAAI, 2008.

48.

[48]

Liu and

Singh, ConceptNet: A practical commonsense reasoning toolkit, BT Technology Journal22(4) (2004), 211–226.

49.

[49]

Marek and

Truszczyński, Stable models and an alternative logic programming paradigm, in: The Logic Programming Paradigm: A 25-Year Perspective, Springer Verlag, 1999, pp. 375–398.

50.

[50]

McCain and

Turner, Causal theories of action and change, in: Proc. of AAAI/IAAI, 1997.

51.

[51]

Mccarthy and

P.J.

Hayes, Some philosophical problems from the standpoint of artificial intelligence, in: Machine Intelligence, Edinburgh University Press, 1969, pp. 463–502.

52.

[52]

Mcdermott,

Ghallab,

Howe,

Knoblock,

Ram,

Veloso,

Weld and

Wilkins, Pddl – the planning domain definition language, Technical Report TR-98-003, Yale Center for Computational Vision and Control, 1998.

53.

[53]

D.S.

Nau,

Muñoz-Avila,

Cao,

Lotem and

Mitchell, Total-order planning with partially ordered subtasks, in: Proc. of IJCAI, 2001.

54.

[54]

Niemelä, Logic programs with stable model semantics as a constraint programming paradigm, Annals of Mathematics and Artificial Intelligence25 (1999), 241–273.

55.

[55]

Nogueira,

Balduccini,

Gelfond,

Watson and

Barry, An A-Prolog decision support system for the space shuttle, in: Proc. of PADL, 2001.

56.

[56]

Pan,

Chitta and

Manocha, FCL: A general purpose library for collision and proximity queries, in: Proc. of ICRA, 2012.

57.

[57]

R.P.A.

Petrick and

Bacchus, A knowledge-based approach to planning with incomplete information and sensing, in: Proc. of AIPS, 2002.

58.

[58]

R.P.A.

Petrick and

Bacchus, Extending the knowledge-based approach to planning with incomplete information and sensing, in: Proc. of ICAPS, 2004.

59.

[59]

Plaku, From high-level tasks to low-level motions: Motion planning for high-dimensional nonlinear hybrid robotic systems, PhD dissertation, Rice University, TX, USA, 2008.

60.

[60]

Plaku, Planning in discrete and continuous spaces: From LTL tasks to robot motions, in: Proc. of TAROS, 2012.

61.

[61]

Plaku and

G.D.

Hager, Sampling-based motion and symbolic action planning with geometric and differential constraints, in: Proc. of ICRA, 2010.

62.

[62]

Reif, Complexity of the mover’s problem and generalizations, in: Proc. of SOCS, 1979.

63.

[63]

Ricca,

Grasso,

Alviano,

Manna,

Lio,

Iiritano and

Leone, Team-building with answer set programming in the Gioia-Tauro seaport, Theory and Practice of Logic Programming12(3) (2012), 361–381.

64.

[64]

Srivastava,

Fang,

Riano,

Chitnis,

Russell and

Abbeel, Combined task and motion planning through an extensible planner-independent interface layer, in: Proc. of ICRA, 2014.

65.

[65]

V.S.

Subrahmanian and

Zaniolo, Relating stable models and AI planning domains, in: Proc. of ICLP, 1995.

66.

[66]

I.A.

Sucan and

Chitta, MoveIt! Available at: http://moveit.ros.org.

67.

[67]

I.A.

Sucan,

Moll and

L.E.

Kavraki, The open motion planning library, Robotics & Automation Magazine, IEEE19(4) (2012), 72–82.

68.

[68]

Tiihonen,

Soininen and

Sulonen, A practical tool for mass-customising configurable products, in: Proc. of ICED, 2003.

69.

[69]

R.W.

Weyhrauch, Prolegomena to a theory of formal reasoning, Technical report, Stanford University, 1978.

70.

[70]

Wolfe,

Marthi and

Russell, Combined task and motion planning for mobile manipulation, in: Proc. of ICAPS, 2010.

Check	Description
	Relevant input
	Realization
$Pe$	Check whether a robot can move from one coordinate to another one.
	Start and goal coordinate (precomputation possible).
	RRTconnect motion planning via MoveIt! using FCL/OMPL, 3 attempts, 0.5 s time limit.
$Po$	Check whether a robot can move from one coordinate to another one, considering movable objects (obstacles) in the world.
	Start and goal coordinate for the robot, coordinate and type for k objects distinct inputs: (precomputation infeasible for $k \neq 0$ ).
	RRTconnect motion planning via MoveIt! using FCL/OMPL, 3 attempts, 1 s time limit.
$Ti$	Estimate the time a robot needs to move from one coordinate to another one by performing multiple motion plans and measuring the length of the shortest one (disregarding obstacles).
	Start and goal coordinate (precomputation possible).
	RRTconnect motion planning via MoveIt! using FCL/OMPL, 9 attempts, 1.5 s time limit.

A systematic analysis of levels of integration between high-level task planning and low-level feasibility checks

Abstract

Keywords

1. Introduction

2. Answer set programming

3.1. Representing a planning problem in ASP

3.2. Solving a planning problem in ASP

3.3. Discussion

4. Feasibility checks

5. Levels of integration

5.1. Direct integration of feasibility checks

5.2. Post-checking plan feasibility

5.3. Comparison of integration methods

Table 1 A comparison of methods of integration: Benefits (+) and drawbacks (−) Pre Int Repl Grepl Applicability with existing tools + − + +/− Low-level guides task planning + + − + Task planning triggers low-level − + + +

5.5. Combinations of integration methods

6. Evaluation criteria

7.1. Housekeeping domain

8. Experimental setup

Table 4 Computational effort of precomputation Domain Check # of checks Time (s) Housekeeping Pe 4,096 268.3 Ti 4,096 271.8 Robotic manipulation Ro 125,840 35.4 Pa 9,669 2.1

9.1. A comparison of integration methods

9.1.1. Computational effort

9.1.3. Additional observations

9.2. A comparison of levels of integration

9.2.2. Solution quality

10.2. A systematic analysis of integration at the search level

11. Discussion and conclusion

Footnotes

Acknowledgement

Housekeeping domain description

Robotic manipulation domain description

Experimental results with the ASP solver Clasp

References

Table 1
A comparison of methods of integration: Benefits (+) and drawbacks (−)

Pre Int Repl Grepl

Applicability with existing tools + − + +/−

Low-level guides task planning + + − +

Task planning triggers low-level − + + +

Table 4
Computational effort of precomputation

Domain Check # of checks Time (s)

Housekeeping $Pe$ 4,096 268.3

$Ti$ 4,096 271.8

Robotic manipulation $Ro$ 125,840 35.4

$Pa$ 9,669 2.1