A state-space acyclicity property for exponentially tighter plan length bounds

Mohammad Abdulaziz, Charles Gretton, Michael Norrish

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    9 Citations (Scopus)

    Abstract

    We investigate compositional bounding of transition system diameters, with application in bounding the lengths of plans. We establish usefully-tight bounds by exploiting acyclicity in state-spaces. We provide mechanised proofs in HOL4 of the validity of our approach. Evaluating our bounds in a range of benchmarks, we demonstrate exponentially tighter upper bounds compared to existing methods. Treating both solvable and unsolvable benchmark problems, we also demonstrate the utility of our bounds in boosting planner performance. We enhance an existing planning procedure to use our bounds, and demonstrate significant coverage improvements, both compared to the base planner, and also in comparisons with state-of-the-art systems.

    Original languageEnglish
    Title of host publicationProceedings of the 27th International Conference on Automated Planning and Scheduling, ICAPS 2017
    EditorsLaura Barbulescu, Stephen F. Smith, Mausam, Jeremy D. Frank
    PublisherAAAI Press
    Pages2-10
    Number of pages9
    ISBN (Electronic)9781577357896
    Publication statusPublished - 2017
    Event27th International Conference on Automated Planning and Scheduling, ICAPS 2017 - Pittsburgh, United States
    Duration: 18 Jun 201723 Jun 2017

    Publication series

    NameProceedings International Conference on Automated Planning and Scheduling, ICAPS
    ISSN (Print)2334-0835
    ISSN (Electronic)2334-0843

    Conference

    Conference27th International Conference on Automated Planning and Scheduling, ICAPS 2017
    Country/TerritoryUnited States
    CityPittsburgh
    Period18/06/1723/06/17

    Fingerprint

    Dive into the research topics of 'A state-space acyclicity property for exponentially tighter plan length bounds'. Together they form a unique fingerprint.

    Cite this