Show simple item record

Knowledge-Based Programs as Succinct Policies for Partially Observable Domains

dc.contributor.authorZanuttini, Bruno
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorLang, Jérôme
dc.contributor.authorSaffidine, Abdallah
dc.contributor.authorSchwarzentruber, François
dc.date.accessioned2021-10-22T13:41:47Z
dc.date.available2021-10-22T13:41:47Z
dc.date.issued2019
dc.identifier.issn0004-3702
dc.identifier.urihttps://basepub.dauphine.psl.eu/handle/123456789/22091
dc.language.isoenen
dc.subjectPlanning under uncertaintyen
dc.subjectContingent planningen
dc.subjectEpistemic logicen
dc.subjectKnowledge-based programsen
dc.subjectBelief trackingen
dc.subject.ddc006.3en
dc.titleKnowledge-Based Programs as Succinct Policies for Partially Observable Domainsen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenWe suggest to express policies for contingent planning by knowledge-based programs (KBPs). KBPs, introduced by Fagin et al. (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 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 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.en
dc.relation.isversionofjnlnameArtificial Intelligence
dc.relation.isversionofjnlvol288en
dc.relation.isversionofjnldate2020-11
dc.relation.isversionofjnlpages103365en
dc.relation.isversionofdoi10.1016/j.artint.2020.103365en
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelIntelligence artificielleen
dc.relation.forthcomingnonen
dc.description.ssrncandidatenon
dc.description.halcandidatenonen
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewedouien
dc.date.updated2021-10-22T13:40:06Z
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

Thumbnail
Name:
AI_Knowledge-based.pdf
Size:
904.3Kb
Format:
PDF
View/Open

This item appears in the following Collection(s)

Show simple item record