We introduce a parallel offline algorithm for computing hybrid conditional plans, called HCP-ASP, oriented towards robotics applications. HCP-ASP relies on modeling actuation actions and sensing actions in an expressive nonmonotonic language of answer set programming (ASP), and computation of the branches of a conditional plan in parallel using an ASP solver. In particular, thanks to external atoms, continuous feasibility checks (like collision checks) are embedded into formal representations of actuation actions and sensing actions in ASP; and thus each branch of a hybrid conditional plan describes a feasible execution of actions to reach their goals. Utilizing nonmonotonic constructs and nondeterministic choices, partial knowledge about states and nondeterministic effects of sensing actions can be explicitly formalized in ASP; and thus each branch of a conditional plan can be computed by an ASP solver without necessitating a conformant planner and an ordering of sensing actions in advance. We apply our method in a service robotics domain and report experimental evaluations. Furthermore, we present performance comparisons with other compilation based conditional planners on standardized benchmark domains. This paper is under consideration for acceptance in TPLP.
Although not compilation-based, the offline conditional planner is also related to : It is not hybrid, not parallel, and its input language is the action language @math ; but it uses ASP to compute conditional plans. Based on 0-approximations @cite_37 , the idea is to approximate a belief state by a consistent set of fluent literals that are known to be true, and to define transitions considering what definitely holds and what may change at the next state. With such an approximation, the computational complexity of conditional planning becomes NP-complete. Given upper bounds for the height and the number of branches, generates a conditional plan with one call of an ASP solver based on an intelligent formulation of possible transitions. does not consider 0-approximations of belief states, but requires that the initial values of fluents that cannot be identified by any sensing action are known in advance, decided nondeterministically (e.g., by a disjunction over the possible values), or specified with respect to some assumptions (e.g., by defaults). Since is compilation-based, it calls an ASP solver multiple times to build a conditional plan.
@cite_37
2549574390 2572515681 2222620134 221046306
Conditional planning enables planning for the sensing actions and their possible outcomes in addition to actuation actions, and allows for addressing uncertainties due to partial observability at the time of offline planning. Therefore, the plans (called conditional plans) computed by conditional planners can be viewed as trees of (deterministic) actuation actions and (nondeterministic) sensing actions. Hybrid conditional planning extends conditional planning further by integrating low-level feasibility checks into executability conditions of actuation actions in conditional plans. We introduce a novel hybrid conditional planning method, which extends hybrid sequential planning with nondeterministic sensing actions and utilizes this extension to compute branches of a conditional plan in parallel. We evaluate this method in a service robotics domain, by means of a set of experiments over dynamic simulations, from the perspectives of computational efficiency and plan quality. In contingent planning under partial observability with sensing actions, agents actively use sensing to discover meaningful facts about the world. For this class of problems the solution can be represented as a plan tree, branching on various possible observations. Recent successful approaches translate the partially observable contingent problem into a non-deterministic fully observable problem, and then use a planner for non-deterministic planning. While this approach has been successful in many domains, the translation may become very large, encumbering the task of the non-deterministic planner. In this paper we suggest a different approach — using an online contingent solver repeatedly to construct a plan tree. We execute the plan returned by the online solver until the next observation action, and then branch on the possible observed values, and replan for every branch independently. In many cases a plan tree can be exponential in the number of state variables, but still, the tree has a structure that allows us to compactly represent it using a directed graph. We suggest a mechanism for tailoring such a graph that reduces both the computational effort and the storage space. Furthermore, unlike recent state of the art offline planners, our approach is not bounded to a specific class of contingent problems, such as limited problem width, or simple contingent problems. We present a set of experiments, showing our approach to scale better than state of the art offline planners. This paper introduces a highly competitive contingent planner, that uses the novel idea of encoding belief states as disjunctive normal form formulae ( 2009), for the search for solutions in the belief state space. In ( 2009), a complete transition function for computing successor belief states in the presence of incomplete information has been defined. This work extends the function to handle non-deterministic and sensing actions in the AND OR forward search paradigm for contingent planning solutions. The function allows one, under reasonable assumptions, to compute successor belief states efficiently, i.e., in polynomial time. The paper also presents a novel variant of an AND OR search algorithm, called PrAO (Pruning AND OR search), which allows the planner to significantly prune the search space; furthermore, by the time a solution is found, the remaining search graph is also the solution tree for the contingent planing problem. The strength of these techniques is confirmed by the empirical results obtained from a large set of benchmarks available in the literature. Planning with sensing actions under partial observability is a computationally challenging problem that is fundamental to the realization of AI tasks in areas as diverse as robotics, game playing, and diagnostic problem solving. Recent work on generating plans for partially observable domains has advocated for online planning, claiming that offline plans are often too large to generate. Here we push the envelope on this challenging problem, proposing a technique for generating conditional (aka contingent) plans offline. The key to our planner's success is the reliance on state-of-the-art techniques for fully observable non-deterministic (FOND) planning. In particular, we use an existing compilation for converting a planning problem under partial observability and sensing to a FOND planning problem. With a modified FOND planner in hand, we are able to scale beyond previous techniques for generating conditional plans with solutions that are orders of magnitude smaller than previously possible in some domains.