From FOND to Robust Probabilistic Planning: Computing compact policies that bypass avoidable deadends.
Camacho, A.; Muise, C.; and McIlraith, S. A.
In
The 26th International Conference on Automated Planning and Scheduling (ICAPS), pages 65–69, 2016.
Paper
link
bibtex
abstract
6 downloads
@InProceedings{cam-mui-mci-icaps16,
Title = {From FOND to Robust Probabilistic Planning: Computing compact policies that bypass avoidable deadends},
Author = {Alberto Camacho and Christian Muise and Sheila A. McIlraith},
Booktitle = {The 26th International Conference on Automated Planning and Scheduling (ICAPS)},
Year = {2016},
Pages = {65--69},
Abstract = {We address the class of probabilistic planning problems where the objective is to maximize the probability of reaching a prescribed goal. The complexity of probabilistic planning problems makes it difficult to compute high quality solutions for large instances, and existing algorithms either do not scale, or do so at the expense of the solution quality. We leverage core similarities between probabilistic and fully observable non-deterministic (FOND) planning to construct a sound, offline probabilistic planner, ProbPRP, that exploits algorithmic advances from state-of-the-art FOND planner, PRP, to compute compact policies that are guaranteed to bypass avoidable deadends. We evaluate ProbPRP on a selection of benchmarks used in past probabilistic planning competitions. The results show that ProbPRP, in many cases, outperforms the state of the art, computing substantially more robust policies and at times doing so orders of magnitude faster.},
Keywords = {non-deterministic planning, probabilistic planning, plan generation},
Timestamp = {2018.09.23},
Url = {http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13188}
}
We address the class of probabilistic planning problems where the objective is to maximize the probability of reaching a prescribed goal. The complexity of probabilistic planning problems makes it difficult to compute high quality solutions for large instances, and existing algorithms either do not scale, or do so at the expense of the solution quality. We leverage core similarities between probabilistic and fully observable non-deterministic (FOND) planning to construct a sound, offline probabilistic planner, ProbPRP, that exploits algorithmic advances from state-of-the-art FOND planner, PRP, to compute compact policies that are guaranteed to bypass avoidable deadends. We evaluate ProbPRP on a selection of benchmarks used in past probabilistic planning competitions. The results show that ProbPRP, in many cases, outperforms the state of the art, computing substantially more robust policies and at times doing so orders of magnitude faster.
Non-Deterministic Planning with Temporally Extended Goals: Completing the story for finite and infinite LTL (Amended Version).
Camacho, A.; Triantafillou, E.; Muise, C.; Baier, J.; and McIlraith, S. A.
In
Workshop on knowledge-based techniques for problem solving and reasoning (KnowProS'16) at IJCAI, 2016.
A version of this paper also appeared in the Workshop on Heuristic Search and Domain Independent Planning (HSDIP'16) at ICAPS
Paper
link
bibtex
abstract
8 downloads
@InProceedings{cam-etal-ltl-knowpros16,
Title = {Non-Deterministic Planning with Temporally Extended Goals: Completing the story for finite and infinite {LTL} (Amended Version)},
Author = {Alberto Camacho and Eleni Triantafillou and Christian Muise and Jorge Baier and Sheila A. McIlraith},
Booktitle = {Workshop on knowledge-based techniques for problem solving and reasoning (KnowProS'16) at IJCAI},
Year = {2016},
Note = {A version of this paper also appeared in the Workshop on Heuristic Search and Domain Independent Planning ({HSDIP}'16) at ICAPS},
Abstract = {Temporally extended goals are critical to the specification of a diversity of real-world planning problems. Here we examine the problem of planning with temporally extended goals over both finite and infinite traces where actions can be non-deterministic, and where temporally extended goals are specified in linear temporal logic (LTL). Unlike existing LTL planners, we place no restrictionson our LTL formulae beyond those necessary to distinguish finite from infinite trace interpretations. We realize our planner by compiling temporally extended goals, represented in LTL, into Planning Domain Definition Language problem instances, and exploiting a state-of-the-art fully observable non-deterministic planner to compute solutions. The resulting planner is sound and complete. Our approach exploits the correspondence between LTL and automata. We propose several different compilations based on translations of LTL to (Buchi) alternating or non-deterministic finite state automata, and evaluate various properties of the competing approaches. We address a diverse spectrum of LTL planning problems that, to this point, had not been solvable using AI planning techniques. We do so while demonstrating competitive performance relative to the state of the art in LTL planning.},
Timestamp = {2018.09.23},
Url = {http://www.cs.toronto.edu/~sheila/publications/cam-etal-ltl-knowpros16.pdf}
}
Temporally extended goals are critical to the specification of a diversity of real-world planning problems. Here we examine the problem of planning with temporally extended goals over both finite and infinite traces where actions can be non-deterministic, and where temporally extended goals are specified in linear temporal logic (LTL). Unlike existing LTL planners, we place no restrictionson our LTL formulae beyond those necessary to distinguish finite from infinite trace interpretations. We realize our planner by compiling temporally extended goals, represented in LTL, into Planning Domain Definition Language problem instances, and exploiting a state-of-the-art fully observable non-deterministic planner to compute solutions. The resulting planner is sound and complete. Our approach exploits the correspondence between LTL and automata. We propose several different compilations based on translations of LTL to (Buchi) alternating or non-deterministic finite state automata, and evaluate various properties of the competing approaches. We address a diverse spectrum of LTL planning problems that, to this point, had not been solvable using AI planning techniques. We do so while demonstrating competitive performance relative to the state of the art in LTL planning.
Belief State Estimation for Planning via Approximate Logical Filtering and Smoothing.
Mombourquette, B.; Muise, C.; and McIlraith, S. A.
In
Workshop on Knowledge-based techniques for problem solving and reasoning (KnowProS'16), 2016.
Paper
link
bibtex
abstract
1 download
@InProceedings{mombourquette-knowpros16-bf,
Title = {Belief State Estimation for Planning via Approximate Logical Filtering and Smoothing},
Author = {Brent Mombourquette and Christian Muise and Sheila A. McIlraith},
Booktitle = {Workshop on Knowledge-based techniques for problem solving and reasoning ({KnowProS}'16)},
Year = {2016},
Abstract = {State estimation is the task of estimating the state of a partially observable dynamical system given a sequence of executed actions and observations. In logical settings, state estimation can be realized via logical filtering. Unfortunately such filtering, though exact, can be intractable. To this end, we propose logical smoothing, a form of backwards reasoning that works in concert with logical filtering to refine past beliefs in light of new observations. We characterize the notion of logical smoothing together with an algorithm for backwards-forwards state estimation. We prove properties of our algorithms, and experimentally demonstrate their behaviour. Smoothing together with backwards-forwards reasoning are important techniques for reasoning about partially observable dynamical systems, introducing the logical analogue of effective techniques from control theory and dynamic programming},
Timestamp = {2018.09.23},
Url = {http://ceur-ws.org/Vol-1648/paper8.pdf}
}
State estimation is the task of estimating the state of a partially observable dynamical system given a sequence of executed actions and observations. In logical settings, state estimation can be realized via logical filtering. Unfortunately such filtering, though exact, can be intractable. To this end, we propose logical smoothing, a form of backwards reasoning that works in concert with logical filtering to refine past beliefs in light of new observations. We characterize the notion of logical smoothing together with an algorithm for backwards-forwards state estimation. We prove properties of our algorithms, and experimentally demonstrate their behaviour. Smoothing together with backwards-forwards reasoning are important techniques for reasoning about partially observable dynamical systems, introducing the logical analogue of effective techniques from control theory and dynamic programming
Optimal Partial-Order Plan Relaxation via MaxSAT.
Muise, C.; Beck, J. C.; and McIlraith, S. A.
Journal of Artificial Intelligence Research (JAIR), 57: 113 – 149. 2016.
Paper
link
bibtex
abstract
3 downloads
@Article{jair-popgen,
Title = {Optimal Partial-Order Plan Relaxation via MaxSAT},
Author = {Christian Muise and J. Christopher Beck and Sheila A. McIlraith},
Journal = {Journal of Artificial Intelligence Research (JAIR)},
Year = {2016},
Pages = {113 -- 149},
Volume = {57},
Abstract = {Partial-order plans (POPs) are attractive because of their least-commitment nature, which provides enhanced plan flexibility at execution time relative to sequential plans. Current research on automated plan generation focuses on producing sequential plans, despite the appeal of POPs. In this paper we examine POP generation by relaxing or modifying the action orderings of a sequential plan to optimize for plan criteria that promote flexibility. Our approach relies on a novel partial weighted MaxSAT encoding of a sequential plan that supports the minimization of deordering or reordering of actions. We further demonstrate how to remove redundant actions from the plan. Our partial weighted MaxSAT encoding allows us to compute a POP from a sequential plan effectively. We compare the efficiency of our approach to previous methods for POP generation via sequential-plan relaxation. Our results show that while an existing heuristic approach consistently produces the optimal deordering of a sequential plan, our approach has greater flexibility when we consider reordering the actions in the plan while also providing a guarantee of optimality. We also investigate and confirm the accuracy of the standard $\flex$ metric typically used to predict the true flexibility of a POP as measured by the number of linearizations it represents.},
Timestamp = {2018.09.23},
Url = {http://www.jair.org/media/5128/live-5128-9534-jair.pdf}
}
Partial-order plans (POPs) are attractive because of their least-commitment nature, which provides enhanced plan flexibility at execution time relative to sequential plans. Current research on automated plan generation focuses on producing sequential plans, despite the appeal of POPs. In this paper we examine POP generation by relaxing or modifying the action orderings of a sequential plan to optimize for plan criteria that promote flexibility. Our approach relies on a novel partial weighted MaxSAT encoding of a sequential plan that supports the minimization of deordering or reordering of actions. We further demonstrate how to remove redundant actions from the plan. Our partial weighted MaxSAT encoding allows us to compute a POP from a sequential plan effectively. We compare the efficiency of our approach to previous methods for POP generation via sequential-plan relaxation. Our results show that while an existing heuristic approach consistently produces the optimal deordering of a sequential plan, our approach has greater flexibility when we consider reordering the actions in the plan while also providing a guarantee of optimality. We also investigate and confirm the accuracy of the standard $\flex$ metric typically used to predict the true flexibility of a POP as measured by the number of linearizations it represents.
DSHARP: Fast d-DNNF Compilation with sharpSAT (Amended Version).
Muise, C.; McIlraith, S. A.; Beck, J. C.; and Hsu, E.
In
AAAI-16 Workshop on Beyond NP, 2016.
Paper
link
bibtex
@InProceedings{muise-beyondnp16-dsharp,
Title = {{DSHARP}: Fast d-DNNF Compilation with sharpSAT (Amended Version)},
Author = {Muise, Christian and McIlraith, Sheila A. and Beck, J.
Christopher and Hsu, Eric},
Booktitle = {AAAI-16 Workshop on Beyond NP},
Year = {2016},
Timestamp = {2018.09.23},
Url = {http://haz.ca/dsharp-related.html}
}