Skip to content

Branching-Bounded Contingent Planning via Belief Space Search

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Original languageEnglish
Title of host publication2nd ICAPS Workshop on Explainable AI Planning (XAIP'19)
Publisher or commissioning bodyKings College London Planning (KCL Planning)
DateAccepted/In press - 15 May 2019
DatePublished (current) - 2019
EventInternational Workshop on Explainable AI Planning - Berkeley, United States
Duration: 12 Jul 201912 Jul 2019
Conference number: 2


WorkshopInternational Workshop on Explainable AI Planning
Abbreviated titleXAIP 2019
CountryUnited States
Internet address


A contingent plan can be encoded as a rooted graph where branching occurs due to sensing. In many applications it is desirable to limit this branching; either to reduce the complexity of the plan (e.g. for subsequent execution by a human), or because sensing itself is deemed to be too expensive. This leads to an established planning problem that we refer to as branching-bounded contingent planning. In this paper, we formalise solutions to such problems in the context of history-, and belief-based policies: under noisy sensing, these policies exhibit differing notions of sensor actions. We also propose a new algorithm, called BAO*, that is able to find optimal solutions via belief space search. This work subsumes both conformant and contingent planning frameworks, and represents the first practical treatment of branching-bounded contingent planning that is valid under partial observability.


International Workshop on Explainable AI Planning

Abbreviated titleXAIP 2019
Conference number2
Duration12 Jul 201912 Jul 2019
CountryUnited States
Web address (URL)
Degree of recognitionInternational event

Event: Workshop



  • Full-text PDF (accepted author manuscript)

    Rights statement: This is the author accepted manuscript (AAM). The final published version (version of record) is available online via KCL Planning at Please refer to any applicable terms of use of the publisher.

    Accepted author manuscript, 261 KB, PDF document


View research connections

Related faculties, schools or groups