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
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.