University of Birmingham
Autonomous online hierarchical conformance refinement planning using answer set programming for general-purpose robots
Abstract
dc:description.abstractThis 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.
Degree
thesis:*- Name dc:type.qualificationname
- d_ph
- Level dc:type.qualificationlevel
- d_ph
- Grantor dc:publisher.institution
- University of Birmingham
- Year dc:date.issued
- 2024
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Kamperis, Oliver Michael
Subjects
dc:subject × 2Rights
- Language dc:language.dcterms_iso639_2
- eng