Show simple item record

dc.contributor.authorLang, Jérôme
dc.contributor.authorZanuttini, Bruno
dc.date.accessioned2019-06-14T16:11:19Z
dc.date.available2019-06-14T16:11:19Z
dc.date.issued2013
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/18980
dc.language.isoenen
dc.subjectKnowledge-based programsen
dc.subject.ddc006.3en
dc.titleKnowledge-Based Programs as Plans: Succinctness and the Complexity of Plan Existenceen
dc.typeCommunication / Conférence
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 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.en
dc.relation.ispartoftitleProceedings of the 14th Conference on Theoretical Aspects of Rationality and Knowledge (TARK 2013)en
dc.relation.ispartofeditorC. Schipper, Burkhard
dc.relation.ispartofpublnameElectronic Proceedings in Theoretical Computer Scienceen
dc.relation.ispartofdate2013
dc.subject.ddclabelIntelligence artificielleen
dc.relation.ispartofisbn978-0-615-74716-3en
dc.relation.conftitle14th Conference on Theoretical Aspects of Rationality and Knowledge (TARK 2013)en
dc.relation.confdate2013-01
dc.relation.confcityChennaien
dc.relation.confcountryIndiaen
dc.relation.forthcomingnonen
dc.description.ssrncandidatenonen
dc.description.halcandidatenonen
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2019-06-14T16:07:36Z
hal.person.labIds989
hal.person.labIds150


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record