Online Hierarchical Conformance Refinement Planning for Autonomous Robots

Planning is a fundamental reasoning ability required by any general-purpose autonomous robot that will be deployed into real-world domains. This paper presents our ongoing work towards a novel domain-independent planning paradigm, called Hierarchical Conformance Refinement (HCR), capable of rapid online partial-planning (that is planning partly interleaved with execution), which aims to maximize productivity and minimize down-times of robots. HCR planning achieves this by employing two core concepts involved in human decision making; abstract reasoning and problem decomposition. Our approach combines the expressive power of Answer Set Programming (ASP) with the speed of hierarchical refinement planning. Together, these allow large and complex problems with long plan lengths, to be broken down and solved as many smaller and more manageable partial-problems, in a general way. This exponentially reduces execution latency and total planning times, for the trade-off of small losses in plan quality. Simulated experiments ran on an extension of the blocks world domain show that HCR planning reduced overall planning time by between 43.8 to 97.6 %, and execution latency time by 87.1 to 98.7%, over classical ASP based planning, but could increase plans lengths by 0.0 to 9.0% over the minimum possible length, from our easiest to hardest problems tested.