Understanding planning with incomplete information and sensing Export

@article{oglietti05incomplete, abstract = {PKS is the framework for planning with incomplete information and sensing recently introduced by Bacchus and Petrick [Proc. KR'98, pp. 432-443]. The fact that PKS generalizes STRIPS to domains with incomplete information and sensing opens up the possibility of proposing it as a reference for comparisons with other formalisms that approach the problem from different perspectives.To this end we first provide a formal semantics for PKS, then analyze and extend it. The formal definition of the extended PKS entails the identification of a number of properties of this planning framework. In particular, we prove that for any finite instance of the PKS planning problem the reachable states are finite; on the basis of this result we propose an improved planning algorithm that is not only sound, as the one proposed by Petrick and Bacchus [Proc. AIPS'02, pp. 212-221], but also complete.We extend PKS to include conditional plans with cycles and introduce the distinction between different classes of solutions: strong, strong cyclic, weak acyclic and weak cyclic. In contrast with current belief, we prove that some weak acyclic solutions are more likely to succeed for a limited execution than some strong cyclic solutions, revealing the lack of a method for judging the quality of different solutions. Finally, we introduce a quality measure for solutions of any class, and a quantitative method for comparing them.}, author = {Oglietti, Marcelo}, citeulike-article-id = {604077}, citeulike-linkout-0 = {http://dx.doi.org/10.1016/j.artint.2004.11.006}, citeulike-linkout-1 = {http://www.sciencedirect.com/science/article/B6TYF-4F662K2-1/2/aa57ed8bcd7af9ca33efb3d8cf3136a6}, doi = {10.1016/j.artint.2004.11.006}, journal = {Artificial Intelligence}, keywords = {ai, incomplete\_knowledge, logi, planning}, month = {May}, number = {1-2}, pages = {171--208}, posted-at = {2006-04-27 01:01:58}, priority = {0}, title = {Understanding planning with incomplete information and sensing}, url = {http://dx.doi.org/10.1016/j.artint.2004.11.006}, volume = {164}, year = {2005} }

TY - JOUR ID - oglietti05incomplete L3 - citeulike-article-id:604077 N2 - PKS is the framework for planning with incomplete information and sensing recently introduced by Bacchus and Petrick [Proc. KR'98, pp. 432-443]. The fact that PKS generalizes STRIPS to domains with incomplete information and sensing opens up the possibility of proposing it as a reference for comparisons with other formalisms that approach the problem from different perspectives.To this end we first provide a formal semantics for PKS, then analyze and extend it. The formal definition of the extended PKS entails the identification of a number of properties of this planning framework. In particular, we prove that for any finite instance of the PKS planning problem the reachable states are finite; on the basis of this result we propose an improved planning algorithm that is not only sound, as the one proposed by Petrick and Bacchus [Proc. AIPS'02, pp. 212-221], but also complete.We extend PKS to include conditional plans with cycles and introduce the distinction between different classes of solutions: strong, strong cyclic, weak acyclic and weak cyclic. In contrast with current belief, we prove that some weak acyclic solutions are more likely to succeed for a limited execution than some strong cyclic solutions, revealing the lack of a method for judging the quality of different solutions. Finally, we introduce a quality measure for solutions of any class, and a quantitative method for comparing them. IS - 1-2 JF - Artificial Intelligence EP - 208 TI - Understanding planning with incomplete information and sensing VL - 164 SP - 171 KW - ai KW - incomplete_knowledge KW - logi KW - planning AU - Oglietti, Marcelo PY - 2005/05// UR - http://dx.doi.org/10.1016/j.artint.2004.11.006 ER -