Skip to Main content Skip to Navigation
Journal articles

Knowledge-Based Programs as Succinct Policies for Partially Observable Domains

Abstract : We suggest to express policies for contingent planning by knowledge-based programs (KBPs). KBPs, introduced by Fagin et al. [Reasoning about Knowledge, MIT Press, 1995], are high-level protocols describing the actions that the agent should perform as a function of their current knowledge: branching conditions are epistemic formulas that are interpretable by the agent. The main aim of our paper is to show that KBPs can be seen as a succinct language for expressing 15 policies in single-agent contingent planning. KBP are conceptually very close to languages used for expressing policies in the partially observable planning literature: like them, they have conditional and looping structures, with actions as atomic programs and Boolean formulas on beliefs for choosing the execution path. Now, the specificity of KBPs is that 20 branching conditions refer to the belief state and not to the observations. Because of their structural proximity, KBPs and standard languages for representing policies have the same power of expressivity: every standard policy can be expressed as a KBP, and every KBP can be "unfolded" into a standard policy. However, KBPs are more succinct, more readable, and more explainable than standard policies. On the other hand, they require more online computation time, but we show that this is an unavoidable tradeoff. We study knowledge-based programs along four criteria: expressivity, succinctness, complexity of online execution, and complexity of verification.
Document type :
Journal articles
Complete list of metadatas

Cited literature [80 references]  Display  Hide  Download
Contributor : Bruno Zanuttini <>
Submitted on : Friday, September 18, 2020 - 12:46:29 PM
Last modification on : Thursday, January 14, 2021 - 3:14:14 PM
Long-term archiving on: : Thursday, December 3, 2020 - 12:45:33 PM


Files produced by the author(s)


  • HAL Id : hal-02942873, version 1


Bruno Zanuttini, Jérôme Lang, Abdallah Saffidine, François Schwarzentruber. Knowledge-Based Programs as Succinct Policies for Partially Observable Domains. Artificial Intelligence, Elsevier, 2020, 288. ⟨hal-02942873⟩



Record views


Files downloads