Strong-Cyclic Planning when Fairness is Not a Valid Assumption. Camacho, A. & McIlraith, S. A. In Workshop on Knowledge-based techniques for problem solving and reasoning (KnowProS'16), 2016.
abstract   bibtex   2 downloads  
We address the class of fully-observable non-deterministic (FOND) planning problems where non-deterministic actions are not guaranteed to display fair behavior. Typical solutions to FOND planning either guarantee goal reachability with a bounded number of transitions (so-called strong acyclic solutions), or are predicated on a fairness assumption that presumes each action effect occurs infinitely often when the action is applied infinite times in the same state (so-called strong-cyclic solutions). We introduce the FOND+ planning model, that extends the FOND model with a more informed description of the action transitions. Solutions to FOND+ problems are able to guarantee goal reachability when the classical fairness assumption is not valid. We characterize different topologies, or classes, of solutions showing that typical strong acyclic, fair strong-cyclic planning are particular cases. Finally, we present algorithms to solve each class of problems, and prove empirically that FOND+ solutions are different than strong-cyclic solutions that presume fairness.
@inproceedings{cam-mci-fondplus-knowpros16,
  title = {Strong-Cyclic Planning when Fairness is Not a Valid Assumption},
  author = {Alberto Camacho and Sheila A. McIlraith},
  booktitle = {Workshop on Knowledge-based techniques for problem solving and reasoning ({KnowProS}'16)},
  year = {2016},
  abstract={We address the class of fully-observable non-deterministic (FOND) planning problems where non-deterministic actions are not guaranteed to display fair behavior. Typical solutions to FOND planning either guarantee goal reachability with a bounded number of transitions (so-called strong acyclic solutions), or are predicated on a fairness assumption that presumes each action effect occurs infinitely often when the action is applied infinite times in the same state (so-called strong-cyclic solutions). We introduce the FOND+ planning model, that extends the FOND model with a more informed description of the action transitions. Solutions to FOND+ problems are able to guarantee goal reachability when the classical fairness assumption is not valid. We characterize different topologies, or classes, of solutions showing that typical strong acyclic, fair strong-cyclic planning are particular cases. Finally, we present algorithms to solve each class of problems, and prove empirically that FOND+ solutions are different than strong-cyclic solutions that presume fairness.}
}
Downloads: 2
About
Documentation
Keywords
Search
Users
Terms and Conditions of Use
Privacy Policy
Sitemap
© BibBase.org 2021