Logo eprints

Plan Synthesis in Explicit-Input Knowledge and Action Bases

Stawowy, Michele (2016) Plan Synthesis in Explicit-Input Knowledge and Action Bases. Advisor: Calvanese, Prof. Diego. pp. 135. [IMT PhD Thesis]

Stawowy_phdthesis.pdf - Published Version
Available under License Creative Commons Attribution No Derivatives.

Download (547kB) | Preview


In this Thesis we study plan synthesis for datacentric domains, where the interest is not only upon the actions the system performs to reach its desired goal, but also on how the knowledge defining the domain evolves with the aforementioned actions. We first introduce a rich, dynamic framework named Explicit-input Knowledge and Action Bases (eKABs), where states are Description Logic (DL) Knowledge Bases, whose extensional part is manipulated by actions that possibly introduce new objects from an infinite domain. We show that plan existence over eKABs is undecidable even under severe restrictions. We then focus on state-bounded eKABs, a class for which plan existence is decidable, and provide sound and complete plan synthesis algorithms, which combine techniques based on standard planning, DL query answering, and finite-state abstraction. All results hold for any DL with decidable query answering. We finally show that for lightweight DLs, plan synthesis can be compiled into standard planning, and we provide two translations: translation to STRIPS for a restricted version of lightweight DL eKABs, and translation to ADL for full lightweight DL eKABs. For the STRIPS setting, we provide an additional technique to optimize Knowledge Base satisfiability check inside the translation. We also provide a technique showing how it is possible to transform any full lightweight DL eKAB to an equivalent restricted lightweight DL eKAB.

Item Type: IMT PhD Thesis
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
PhD Course: Computer Science and Engineering
Identification Number: 10.6092/imtlucca/e-theses/208
NBN Number: urn:nbn:it:imtlucca-27236
Date Deposited: 22 Mar 2017 15:05
URI: http://e-theses.imtlucca.it/id/eprint/208

Actions (login required, only for staff repository)

View Item View Item