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.
Offline conditional planners can be further classified into two groups: search-based approaches and compilation-based approaches. The former group views conditional planning as a nondeterministic search problem in belief space (e.g., Contingent-FF, PKS, POND), whereas most of the planners in the latter group compiles a conditional planning problem into many conformant planning problems by deciding for the order of sensing actions and then computing the branches of the conditional plan by means of conformant planning (e.g., CLG, DNFct, PO-PRP). Recall that conformant planning considers incomplete initial state and no observability, and its aim is to find an action sequence that reaches the goal for every possible initial state @cite_1 . Our planner can be characterized as a compilation-based planner since we compile a conditional planning problem into many sequential planning problems.
@cite_1
221046306 2572515681 2549574390 2574020264
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. 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. 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. We address the class of probabilistic planning problems where the objective is to maximize the probability of reaching a prescribed goal. The complexity of probabilistic planning problems makes it difficult to compute high quality solutions for large instances, and existing algorithms either do not scale, or do so at the expense of the solution quality. We leverage core similarities between probabilistic and fully observable non-deterministic (FOND) planning to construct a sound, offline probabilistic planner, ProbPRP, that exploits algorithmic advances from state-of-the-art FOND planner, PRP, to compute compact policies that are guaranteed to bypass avoidable deadends. We evaluate ProbPRP on a selection of benchmarks used in past probabilistic planning competitions. The results show that ProbPRP, in many cases, outperforms the state of the art, computing substantially more robust policies and at times doing so orders of magnitude faster.