short-paper

Temporal logic motion planning using POMDPs with parity objectives: case study paper

Authors:

Mária Svoreňová,

Martin Chmelík,

Hasan Ferit Eniser,

Krishnendu Chatterjee,

Calin BeltaAuthors Info & Claims

HSCC '15: Proceedings of the 18th International Conference on Hybrid Systems: Computation and Control

Pages 233 - 238

https://doi.org/10.1145/2728606.2728617

Published: 14 April 2015 Publication History

Abstract

We consider a case study of the problem of deploying an autonomous air vehicle in a partially observable, dynamic, indoor environment from a specification given as a linear temporal logic (LTL) formula over regions of interest. We model the motion and sensing capabilities of the vehicle as a partially observable Markov decision process (POMDP). We adapt recent results for solving POMDPs with parity objectives to generate a control policy. We also extend the existing framework with a policy minimization technique to obtain a better implementable policy, while preserving its correctness. The proposed techniques are illustrated in an experimental setup involving an autonomous quadrotor performing surveillance in a dynamic environment.

References

[1]

C. Baier, M. Größer, and N. Bertrand. Probabilistic omega-automata. J. ACM, 59(1), 2012.

Digital Library

[2]

C. Baier and J.-P. Katoen. Principles of Model Checking. MIT Press, 2008.

Digital Library

[3]

A. Brooks, A. Makarenko, S. Williams, and H. Durrant-Whyte. Parametric POMDPs for planning in continuous state spaces. J. RAS, 54(11), 2006.

[4]

K. Chatterjee, M. Chmelik, R. Gupta, and A. Kanodia. Qualitative Analysis of POMDPs with Temporal Logic Specifications for Robotics Applications. CoRR, abs/1409.3360, 2014.

[5]

K. Chatterjee, M. Chmelik, and M. Tracol. What is Decidable about Partially Observable Markov Decision Processes with ω-Regular Objectives. In CSL, 2013.

[6]

E. Clarke, O. Grumberg, and D. Peled. Model checking. MIT press, 1999.

Digital Library

[7]

K. Hsiao, L. Kaelbling, and T. Lozano-Perez. Grasping POMDPs. In ICRA. IEEE, 2007.

[8]

D. Hsu, W. S. Lee, and N. Rong. A point-based POMDP planner for target tracking. In ICRA, 2008.

[9]

T. Jiang and B. Ravikumar. Minimal NFA problems are hard. SIAM J. Comput., 1993.

Digital Library

[10]

H. Kurniawati, D. Hsu, and W. Lee. SARSOP: Efficient point-based POMDP planning by approximating optimally reachable belief spaces. In Robotics: Science and Systems, 2008.

[11]

C. H. Papadimitriou and J. N. Tsitsiklis. The complexity of Markov decision processes. Mathematics of Operations Research, 1987.

[12]

J. Pineau, G. Gordon, and S. Thrun. Point-based value iteration: An anytime algorithm for POMDPs. In IJCAI, 2003.

Digital Library

[13]

N. Piterman. From nondeterministic Buchi and Streett automata to deterministic parity automata. In LICS, 2006.

Digital Library

[14]

N. Roy and S. Thrun. Coastal Navigation with Mobile Robots. In NIPS, 1999.

[15]

S. Safra. On the complexity of ω-automata. In FOCS, 1988.

Digital Library

[16]

G. Shani, P. Poupart, R. I. Brafman, and S. E. Shimony. Efficient ADD Operations for Point-Based Algorithms. In ICAPS, 2008.

[17]

T. Smith and R. Simmons. Point-Based POMDP Algorithms: Improved Analysis and Implementation. In UAI, 2005.

[18]

M. Spaan and N. Vlassis. A point-based POMDP algorithm for robot planning. In ICRA. IEEE, 2004.

[19]

S. Thrun, W. Burgard, and D. Fox. Probabilistic robotics. MIT Press, 2005.

[20]

M. Y. Vardi. Automatic verification of probabilistic concurrent finite-state systems. In FOCS. IEEE, 1985.

Digital Library

Cited By

Yu PDong SSheng SFeng LKwiatkowska M(2024)Trust-Aware Motion Planning for Human-Robot Collaboration under Distribution Temporal Logic Specifications2024 IEEE International Conference on Robotics and Automation (ICRA)10.1109/ICRA57147.2024.10610874(12949-12955)Online publication date: 13-May-2024
https://doi.org/10.1109/ICRA57147.2024.10610874
Yang WXu CPan MZhou YHuang Z(2023)Ensure: Towards Reliable Control of Cyber-Physical Systems Under UncertaintyIEEE Transactions on Reliability10.1109/TR.2022.316711672:1(289-301)Online publication date: Mar-2023
https://doi.org/10.1109/TR.2022.3167116
Wang YNewaz AHernandez JChaudhuri SKavraki L(2021)Online Partial Conditional Plan Synthesis for POMDPs With Safe-Reachability Objectives: Methods and ExperimentsIEEE Transactions on Automation Science and Engineering10.1109/TASE.2021.305711118:3(932-945)Online publication date: Jul-2021
https://doi.org/10.1109/TASE.2021.3057111
Show More Cited By

Index Terms

Temporal logic motion planning using POMDPs with parity objectives: case study paper

Recommendations

Efficient planning for factored infinite-horizon DEC-POMDPs
IJCAI'11: Proceedings of the Twenty-Second international joint conference on Artificial Intelligence - Volume Volume One

Decentralized partially observable Markov decision processes (DEC-POMDPs) are used to plan policies for multiple agents that must maximize a joint reward function but do not communicate with each other. The agents act under uncertainty about each other ...
Expectation optimization with probabilistic guarantees in POMDPs with discounted-sum objectives
IJCAI'18: Proceedings of the 27th International Joint Conference on Artificial Intelligence

Partially-observable Markov decision processes (POMDPs) with discounted-sum payoff are a standard framework to model a wide range of problems related to decision making under uncertainty. Traditionally, the goal has been to obtain policies that optimize ...
Efficient planning in large POMDPs through policy graph based factorized approximations
ECMLPKDD'10: Proceedings of the 2010th European Conference on Machine Learning and Knowledge Discovery in Databases - Volume Part III

Partially observable Markov decision processes (POMDPs) are widely used for planning under uncertainty. In many applications, the huge size of the POMDP state space makes straightforward optimization of plans (policies) computationally intractable. To ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

HSCC '15: Proceedings of the 18th International Conference on Hybrid Systems: Computation and Control

April 2015

321 pages

ISBN:9781450334334

DOI:10.1145/2728606

Program Chairs:
Antoine Girard
Université Joseph Fourier, Grenoble, France
,
Sriram Sankaranarayanan
University of Colorado at Boulder

Copyright © 2015 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

IEEE-CSS: Control Systems Society
SIGBED: ACM Special Interest Group on Embedded Systems

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 April 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Short-paper

Funding Sources

Czech Ministry of Education, Youth and Sports
Austrian Science Fund
European Research Council
Office of Naval Research
National Science Foundation

Conference

HSCC '15

Sponsor:

IEEE-CSS
SIGBED

HSCC '15: 18th International Conference on Hybrid Systems: Computation and Control

April 14 - 16, 2015

Washington, Seattle

Acceptance Rates

Overall Acceptance Rate 153 of 373 submissions, 41%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
311
Total Downloads

Downloads (Last 12 months)19
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Yu PDong SSheng SFeng LKwiatkowska M(2024)Trust-Aware Motion Planning for Human-Robot Collaboration under Distribution Temporal Logic Specifications2024 IEEE International Conference on Robotics and Automation (ICRA)10.1109/ICRA57147.2024.10610874(12949-12955)Online publication date: 13-May-2024
https://doi.org/10.1109/ICRA57147.2024.10610874
Yang WXu CPan MZhou YHuang Z(2023)Ensure: Towards Reliable Control of Cyber-Physical Systems Under UncertaintyIEEE Transactions on Reliability10.1109/TR.2022.316711672:1(289-301)Online publication date: Mar-2023
https://doi.org/10.1109/TR.2022.3167116
Wang YNewaz AHernandez JChaudhuri SKavraki L(2021)Online Partial Conditional Plan Synthesis for POMDPs With Safe-Reachability Objectives: Methods and ExperimentsIEEE Transactions on Automation Science and Engineering10.1109/TASE.2021.305711118:3(932-945)Online publication date: Jul-2021
https://doi.org/10.1109/TASE.2021.3057111
Bradley CPacheck AStein GCastro SKress-Gazit HRoy N(2021)Learning and Planning for Temporally Extended Tasks in Unknown Environments2021 IEEE International Conference on Robotics and Automation (ICRA)10.1109/ICRA48506.2021.9561819(4830-4836)Online publication date: 30-May-2021
https://doi.org/10.1109/ICRA48506.2021.9561819
Shamgah LGetahun Tadewos TKarimoddini A(2021)Design of smooth hybrid controllers for a class of non‐linear systemsIET Control Theory & Applications10.1049/iet-cta.2019.111214:19(3251-3259)Online publication date: 17-Feb-2021
https://doi.org/10.1049/iet-cta.2019.1112
Junges SJansen NSeshia S(2021)Enforcing Almost-Sure Reachability in POMDPsComputer Aided Verification10.1007/978-3-030-81688-9_28(602-625)Online publication date: 15-Jul-2021
https://doi.org/10.1007/978-3-030-81688-9_28
Wang YChaudhuri SKavraki L(2020)Online Partial Conditional Plan Synthesis for POMDPs with Safe-Reachability ObjectivesAlgorithmic Foundations of Robotics XIII10.1007/978-3-030-44051-0_8(127-143)Online publication date: 8-May-2020
https://doi.org/10.1007/978-3-030-44051-0_8
Wang YChaudhuri SKavraki LAndre EKoenig SDastani MSukthankar G(2018)Bounded Policy Synthesis for POMDPs with Safe-Reachability ObjectivesProceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3237383.3237424(238-246)Online publication date: 9-Jul-2018
https://dl.acm.org/doi/10.5555/3237383.3237424
Giaquinta RHoffmann RIreland MMiller ANorman G(2018)Strategy Synthesis for Autonomous Agents Using PRISMNASA Formal Methods10.1007/978-3-319-77935-5_16(220-236)Online publication date: 11-Mar-2018
https://doi.org/10.1007/978-3-319-77935-5_16
Norman GParker DZou X(2017)Verification and control of partially observable probabilistic systemsReal-Time Systems10.1007/s11241-017-9269-453:3(354-402)Online publication date: 1-May-2017
https://dl.acm.org/doi/10.1007/s11241-017-9269-4
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents