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.
@cite_37: Abstract In presence of incomplete information about the world we need to distinguish between the state of the world and the state of the agent's knowledge about the world. In such a case the agent may need to have at its disposal sensing actions that change its state of knowledge about the world and may need to construct more general plans consisting of sensing actions and conditional statements to achieve its goal. In this paper we first develop a high-level action description language that allows specification of sensing actions and their effects in its domain description and allows queries with conditional plans. We give provably correct translations of domain description in our language to axioms in first-order logic, and relate our formulation to several earlier formulations in the literature. We then analyze the state space of our formulation and develop several sound approximations that have much smaller state spaces. Finally we define regression of knowledge formulas over conditional plans.
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.