Sampling-Based Reactive Synthesis for Nondeterministic Hybrid Systems

被引:1
作者
Ho, Qi Heng [1 ]
Sunberg, Zachary N. [1 ]
Lahijanian, Morteza [1 ]
机构
[1] Univ Colorado, Dept Aerosp Engn Sci, Boulder, CO 80309 USA
关键词
Formal methods in robotics and automation; hybrid logical/dynamical planning and verification; motion andpath planning; planning under uncertainty; FEEDBACK;
D O I
10.1109/LRA.2023.3340029
中图分类号
TP24 [机器人技术];
学科分类号
080202 ; 1405 ;
摘要
This letter introduces a sampling-based strategy synthesis algorithm for nondeterministic hybrid systems with complex continuous dynamics under temporal and reachability constraints. We model the evolution of the hybrid system as a two-player game, where the nondeterminism is an adversarial player whose objective is to prevent achieving temporal and reachability goals. The aim is to synthesize a winning strategy - a reactive (robust) strategy that guarantees the satisfaction of the goals under all possible moves of the adversarial player. Our proposed approach involves growing a (search) game-tree in the hybrid space by combining sampling-based motion planning with a novel bandit-based technique to select and improve on partial strategies. We show that the algorithm is probabilistically complete, i.e., the algorithm will asymptotically almost surely find a winning strategy, if one exists. The case studies and benchmark results show that our algorithm is general and effective, and consistently outperforms state of the art algorithms.
引用
收藏
页码:931 / 938
页数:8
相关论文
共 30 条
  • [1] FIRM: Sampling-based feedback motion-planning under motion uncertainty and imperfect measurements
    Agha-mohammadi, Ali-akbar
    Chakravorty, Suman
    Amato, Nancy M.
    [J]. INTERNATIONAL JOURNAL OF ROBOTICS RESEARCH, 2014, 33 (02) : 268 - 304
  • [2] Finite-time analysis of the multiarmed bandit problem
    Auer, P
    Cesa-Bianchi, N
    Fischer, P
    [J]. MACHINE LEARNING, 2002, 47 (2-3) : 235 - 256
  • [3] Baier C, 2008, PRINCIPLES OF MODEL CHECKING, P1
  • [4] Sampling-based Motion Planning with Temporal Goals
    Bhatia, Amit
    Kavraki, Lydia E.
    Vardi, Moshe Y.
    [J]. 2010 IEEE INTERNATIONAL CONFERENCE ON ROBOTICS AND AUTOMATION (ICRA), 2010, : 2689 - 2696
  • [5] De Giacomo G., 2013, ence, P854
  • [6] He KL, 2017, IEEE INT C INT ROBOT, P5326, DOI 10.1109/IROS.2017.8206426
  • [7] Herbert SL, 2017, IEEE DECIS CONTR P
  • [8] Planning with SiMBA: Motion Planning under Uncertainty for Temporal Goals using Simplified Belief Guides
    Ho, Qi Heng
    Sunberg, Zachary N.
    Lahijanian, Morteza
    [J]. 2023 IEEE INTERNATIONAL CONFERENCE ON ROBOTICS AND AUTOMATION, ICRA, 2023, : 5723 - 5729
  • [9] Gaussian Belief Trees for Chance Constrained Asymptotically Optimal Motion Planning
    Ho, Qi Heng
    Sunberg, Zachary N.
    Lahijanian, Morteza
    [J]. 2022 IEEE INTERNATIONAL CONFERENCE ON ROBOTICS AND AUTOMATION, ICRA 2022, 2022, : 11029 - 11035
  • [10] Sampling-Based Methods for Motion Planning with Constraints
    Kingston, Zachary
    Moll, Mark
    Kavraki, Lydia E.
    [J]. ANNUAL REVIEW OF CONTROL, ROBOTICS, AND AUTONOMOUS SYSTEMS, VOL 1, 2018, 1 : 159 - 185