FOND planning with explicit fairness assumptions

Mostra el registre complet Registre parcial de l'ítem

• dc.contributor.author Rodriguez, Ivan D.
• dc.contributor.author Bonet, Blai
• dc.contributor.author Sardina, Sebastian
• dc.contributor.author Geffner, Héctor
• dc.date.accessioned 2023-03-01T07:25:51Z
• dc.date.available 2023-03-01T07:25:51Z
• dc.date.issued 2022
• dc.description.abstract We consider the problem of reaching a propositional goal condition in fully-observable nondeterministic (FOND) planning under a general class of fairness assumptions that are given explicitly. The fairness assumptions are of the form A/B and say that state trajectories that contain infinite occurrences of an action a from A in a state s and finite occurrence of actions from B, must also contain infinite occurrences of action a in s followed by each one of its possible outcomes. The infinite trajectories that violate this condition are deemed as unfair, and the solutions are policies for which all the fair trajectories reach a goal state. We show that strong and strong-cyclic FOND planning, as well as QNP planning, a planning model introduced recently for generalized planning, are all special cases of FOND planning with fairness assumptions of this form which can also be combined. FOND+ planning, as this form of planning is called, combines the syntax of FOND planning with some of the versatility of LTL for expressing fairness constraints. A sound and complete FOND+ planner is implemented by reducing FOND+ planning to answer set programs, and its performance is evaluated in comparison with FOND and QNP planners, and LTL synthesis tools. Two other FOND+ planners are introduced as well which are more scalable but are not complete.
• dc.description.sponsorship The work is partially supported by an ERC Advanced Grant (No 885107), the project TAILOR, funded by an EU Horizon 2020 Grant (No 952215), and by the Knut and Alice Wallenberg (KAW) Foundation under the WASP program.
• dc.format.mimetype application/pdf
• dc.identifier.citation Rodriguez ID, Bonet B, Sardina S, Geffner H. FOND planning with explicit fairness assumptions. J Artif Intell Res. 2022;74:887–916. DOI: 10.1613/jair.1.13599
• dc.identifier.doi http://dx.doi.org/10.1613/jair.1.13599
• dc.identifier.issn 1076-9757
• dc.identifier.uri http://hdl.handle.net/10230/55978
• dc.language.iso eng
• dc.publisher AI Access Foundation
• dc.relation.ispartof Journal of Artificial Intelligence Research. 2022;74:887–916.
• dc.relation.projectID info:eu-repo/grantAgreement/EC/H2020/952215
• dc.relation.projectID info:eu-repo/grantAgreement/EC/H2020/885107
• dc.rights © AI Access Foundation. The original article was published in Journal of Artificial Intelligence Research 7 and can be found at http://dx.doi.org/10.1613/jair.1.13599
• dc.rights.accessRights info:eu-repo/semantics/openAccess
• dc.subject.keyword planning
• dc.subject.keyword knowledge representation
• dc.title FOND planning with explicit fairness assumptions
• dc.type info:eu-repo/semantics/article
• dc.type.version info:eu-repo/semantics/publishedVersion