Hybrid conditional planning for robotic applications

摘要

Robots who have partial observability of and incomplete knowledge about their environments may have to consider contingencies while planning, and thus necessitate cognitive abilities beyond classical planning. Moreover, during planning, they need to consider continuous feasibility checks for executability of the plans in the real world. Conditional planning is concerned with reaching goals from an initial state, in the presence of incomplete knowledge and partial observability, by considering all contingencies and by utilizing sensing actions to gather relevant knowledge when needed. A conditional plan is essentially a tree of actions where each branch of the tree represents a possible execution of actuation actions and sensing actions to reach a goal state. Hybrid conditional planning extends conditional planning by integrating feasibility checks into executability conditions of actions. We introduce a parallel offline algorithm, called HCPlan, for computing hybrid conditional plans. HCPlan relies on modeling deterministic effects of actuation actions and non-deterministic effects of sensing actions in the causality-based action language [Formula: see text]. Branches of a hybrid conditional plan are computed in parallel using a SAT solver, where continuous feasibility checks are performed as needed. We develop a comprehensive benchmark suite and introduce new evaluation metrics for hybrid conditional planning. We evaluate HCPlan with extensive experiments in terms of computational efficiency and plan quality. We perform experiments to compare HCPlan with other related conditional planners and approaches to deal with contingencies due to incomplete knowledge. We further demonstrate the applicability and usefulness of HCPlan in service robotics applications, through dynamic simulations and physical implementations.