Branching-Bounded Contingent Planning via Belief Space Search

Kevin McAreavey, Kim Bauters, Weiru Liu, Jun Hong

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

48 Downloads (Pure)


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.
Original languageEnglish
Title of host publication2nd ICAPS Workshop on Explainable AI Planning (XAIP'19)
PublisherKings College London Planning (KCL Planning)
Publication statusPublished - 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
Country/TerritoryUnited States
Internet address


Dive into the research topics of 'Branching-Bounded Contingent Planning via Belief Space Search'. Together they form a unique fingerprint.

Cite this