Knowledge-Based Programs as Plans: Succinctness and the Complexity of Plan Existence
Lang, Jérôme; Zanuttini, Bruno (2013), Knowledge-Based Programs as Plans: Succinctness and the Complexity of Plan Existence, in C. Schipper, Burkhard, Proceedings of the 14th Conference on Theoretical Aspects of Rationality and Knowledge (TARK 2013), Electronic Proceedings in Theoretical Computer Science
TypeCommunication / Conférence
Conference title14th Conference on Theoretical Aspects of Rationality and Knowledge (TARK 2013)
Book titleProceedings of the 14th Conference on Theoretical Aspects of Rationality and Knowledge (TARK 2013)
Book authorC. Schipper, Burkhard
MetadataShow full item record
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Groupe de Recherche en Informatique, Image, Automatique et Instrumentation de Caen [GREYC]
Abstract (EN)Knowledge-based programs (KBPs) are high-level protocols describing the course of action an agent should perform as a function of its knowledge. The use of KBPs for expressing action policies in AI planning has been surprisingly overlooked. Given that to each KBP corresponds an equivalent plan and vice versa, KBPs are typically more succinct than standard plans, but imply more on-line computation time. Here we make this argument formal, and prove that there exists an exponential succinctness gap between knowledge-based programs and standard plans. Then we address the complexity of plan existence. Some results trivially follow from results already known from the literature on planning under incomplete knowledge, but many were unknown so far.
Subjects / KeywordsKnowledge-based programs
Showing items related by title and author.