Show simple item record

Knowledge-Based Programs as Plans: Succinctness and the Complexity of Plan Existence

hal.structure.identifier
dc.contributor.authorLang, Jérôme*
hal.structure.identifier
dc.contributor.authorZanuttini, Bruno*
dc.date.accessioned2014-01-16T09:38:04Z
dc.date.available2014-01-16T09:38:04Z
dc.date.issued2013
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/12458
dc.language.isoenen
dc.subjectSystème multi-agents
dc.subject.ddc006.3en
dc.titleKnowledge-Based Programs as Plans: Succinctness and the Complexity of Plan Existence
dc.typeCommunication / Conférence
dc.contributor.editoruniversityotherGroupe de Recherche en Informatique, Image, Automatique et Instrumentation de Caen (GREYC), Université de Caen Basse-Normandie.;France
dc.description.abstractenKnowledge-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 over-looked. 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.
dc.subject.ddclabelIntelligence artificielleen
dc.relation.conftitleTARK 2013 Theoretical Aspects of Rationality and Knowledge, 14 th Conference – Chennai, India
dc.relation.confdate2013-01
dc.relation.confcityChennai
dc.relation.confcountryIndia
dc.relation.forthcomingnonen
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.date.updated2017-01-06T18:51:42Z
hal.author.functionaut
hal.author.functionaut


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record