{"id":{"repo_id":"birmingham","oai_identifier":"oai:etheses.bham.ac.uk:15109"},"canonical_url":"https://search.ndltd.org/etd/birmingham/oai:etheses.bham.ac.uk:15109","repository":{"repo_id":"birmingham","name":"University of Birmingham","base_url":"https://etheses.bham.ac.uk/cgi/oai2"},"display":{"title":"Autonomous online hierarchical conformance refinement planning using answer set programming for general-purpose robots","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.","abstract_html":"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.","abstract_has_math":false,"creators":["Kamperis, Oliver Michael"],"institution":"University of Birmingham","degree_name":"d_ph","degree_level":"d_ph","degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2024,"date_issued":"2024-07","date_published":"2024-07","updated_at":"2026-11-19T09:32:49Z","subjects":["QA75 Electronic computers. Computer science","QA76 Computer software"],"languages":["eng"],"rights":[],"rights_urls":[],"identifier_entries":[],"person_identifier_entries":[]},"links":{"outbound_url":null,"outbound_label":null,"outbound_source":null,"record_url":null,"record_label":null,"record_kind":null,"record_source":null,"download_url":"http://etheses.bham.ac.uk//id/eprint/15109/7/Kamperis2024PhD.pdf","download_label":"Download PDF","download_source":"dc:identifier.uri","access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://etheses.bham.ac.uk/cgi/oai2?verb=GetRecord&metadataPrefix=uketd_dc&identifier=oai%3Aetheses.bham.ac.uk%3A15109","prefix":"uketd_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.sponsor","label":"Sponsor","values":["other"]},{"key":"dc:creator","label":"Author","values":["Kamperis, Oliver Michael"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2024-07-11"]},{"key":"dc:date.issued","label":"Date","values":["2024-07"]},{"key":"dc:publisher.department","label":"Dc Publisher Department","values":["College of Engineering & Physical Sciences","School of Computer Science"]},{"key":"dc:publisher.institution","label":"Dc Publisher Institution","values":["University of Birmingham"]},{"key":"dc:relation.isreferencedby","label":"Dc Relation Isreferencedby","values":["http://etheses.bham.ac.uk//id/eprint/15109/"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"dc:type.qualificationlevel","label":"Dc Type Qualificationlevel","values":["d_ph"]},{"key":"dc:type.qualificationname","label":"Dc Type Qualificationname","values":["d_ph"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["QA75 Electronic computers. Computer science","QA76 Computer software"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.dcterms_iso639_2","label":"Language (ISO 639-2)","values":["eng"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://etheses.bham.ac.uk//id/eprint/15109/7/Kamperis2024PhD.pdf"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:format","label":"Dc Format","values":["text"]},{"key":"dcterms:accessrights","label":"Dcterms Accessrights","values":["public"]},{"key":"dc:title","label":"Title","values":["Autonomous online hierarchical conformance refinement planning using answer set programming for general-purpose robots"]}]}],"canonical_facts":{"dc:contributor.sponsor":["other"],"dc:creator":["Kamperis, Oliver Michael"],"dc:date":["2024-07-11"],"dc:date.issued":["2024-07"],"dc:description.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."],"dc:format":["text"],"dc:identifier.uri":["http://etheses.bham.ac.uk//id/eprint/15109/7/Kamperis2024PhD.pdf"],"dc:language.dcterms_iso639_2":["eng"],"dc:publisher.department":["College of Engineering & Physical Sciences","School of Computer Science"],"dc:publisher.institution":["University of Birmingham"],"dc:relation.isreferencedby":["http://etheses.bham.ac.uk//id/eprint/15109/"],"dc:subject":["QA75 Electronic computers. Computer science","QA76 Computer software"],"dcterms:accessrights":["public"],"dc:title":["Autonomous online hierarchical conformance refinement planning using answer set programming for general-purpose robots"],"dc:type":["Thesis"],"dc:type.qualificationlevel":["d_ph"],"dc:type.qualificationname":["d_ph"]},"updated_at":"2026-11-19T09:32:49Z"}