Autonomous online hierarchical conformance refinement planning using answer set programming for general-purpose robots

Kamperis, Oliver Michael (2024). Autonomous online hierarchical conformance refinement planning using answer set programming for general-purpose robots. University of Birmingham. Ph.D.

Preview

Kamperis2024PhD.pdf
Text - Accepted Version
Available under License All rights reserved.
Download (2MB) | Preview

Abstract

This thesis proposes a novel approach to rapid online task and high-level action planning, called Hierarchical Conformance Refinement (HCR), which focuses on robotics applications. HCR planning is domain-independent, geared towards problems with many complex interacting constraints, and designed to minimise downtime and maximise productivity of robots. HCR is built in Answer Set Programming (ASP), a declarative knowledge representation and reasoning paradigm. ASP is highly effective for solving complex planning problems involving large amounts of descriptive domain knowledge. However, existing ASP planners perform poorly for problems with long minimal plan lengths. HCR tackles this weakness, by combining ASP with a novel mechanism for hierarchical refinement planning, and finds in the union of their complementary capabilities, the overcoming of their weaknesses and reinforcement of their strengths. The resulting technique enables a flexible divide-and-conquer method that exponentially reduces problem complexity and naturally supports online planning. This greatly improves speed and scalability to large problems with long plan lengths, whilst maintaining the high expressivity and generality of existing ASP planners.

Simulated experiments ran on a combined blocks world and navigation domain show that HCR planning significantly outperforms the classical approach to ASP based planning by exponentially reducing execution latency and total planning times in the minimum plan length of a problem. HCR planning reduced median execution latency by between 81 to 99% and total planning time by between 42 to 98%, over classical ASP based planning, for only between 0 to 11% reduction in plan quality, from the easiest to hardest problems tested. For the most complex problem tested, a robot equipped with the HCR algorithm can reduce total planning time from 607.0 to 14.1 seconds, and execution latency to less than 7 seconds. This makes ASP planning fast enough to be used for practical robotics applications.

Type of Work:

Thesis (Doctorates > Ph.D.)

Award Type:

Doctorates > Ph.D.

Supervisor(s):