Incremental heuristic search for planning with temporally extended goals and uncontrollable events

Adi Botea*, André A. Ciré

*Corresponding author for this work

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

    4 Citations (Scopus)

    Abstract

    Planning with temporally extended goals and uncontrollable events has recently been introduced as a formal model for system reconfiguration problems. An important application is to automatically reconfigure a real-life system in such a way that its subsequent internal evolution is consistent with a temporal goal formula. In this paper we introduce an incremental search algorithm and a search-guidance heuristic, two generic planning enhancements. An initial problem is decomposed into a series of subproblems, providing two main ways of speeding up a search. Firstly, a subproblem focuses on a part of the initial goal. Secondly, a notion of action relevance allows to explore with higher priority actions that are heuristically considered to be more relevant to the subproblem at hand. Even though our techniques are more generally applicable, we restrict our attention to planning with temporally extended goals and uncontrollable events. Our ideas are implemented on top of a successful previous system that performs online learning to better guide planning and to safely avoid potentially expensive searches. In experiments, the system speed performance is further improved by a convincing margin.

    Original languageEnglish
    Title of host publicationIJCAI-09 - Proceedings of the 21st International Joint Conference on Artificial Intelligence
    PublisherInternational Joint Conferences on Artificial Intelligence
    Pages1647-1652
    Number of pages6
    ISBN (Print)9781577354260
    Publication statusPublished - 2009
    Event21st International Joint Conference on Artificial Intelligence, IJCAI 2009 - Pasadena, United States
    Duration: 11 Jul 200916 Jul 2009

    Publication series

    NameIJCAI International Joint Conference on Artificial Intelligence
    ISSN (Print)1045-0823

    Conference

    Conference21st International Joint Conference on Artificial Intelligence, IJCAI 2009
    Country/TerritoryUnited States
    CityPasadena
    Period11/07/0916/07/09

    Fingerprint

    Dive into the research topics of 'Incremental heuristic search for planning with temporally extended goals and uncontrollable events'. Together they form a unique fingerprint.

    Cite this