Chance-Constrained Multilayered Sampling-Based Path Planning for Temporal Logic-Based Missions

• 成果类型: Article
• 署名作者: Oh, Yoonseon; Cho, Kyunghoon; Choi, Yunho; Oh, Songhwai
• 署名单位: Korea Institute of Science & Technology (KIST); Incheon National University; Seoul National University (SNU)
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2020.3044273
• 发表日期: 2021
• 页码: 5816-5829
• 关键词: robots; PLANNING; safety; trajectory; Probabilistic logic; Heuristic algorithms; Collision avoidance; linear temporal logic (LTL); path planning; probabilistic guarantee

摘要

This article introduces a robust and safe path planning algorithm in order to satisfy mission requirements specified in linear temporal logic (LTL). When a path is planned to accomplish a mission, it is possible for a robot to fail to complete the mission or collide with obstacles due to noises and disturbances in the system. Hence, we need to find a robust path against possible disturbances. We introduce a robust path planning algorithm, which maximizes the probability of success in accomplishing a given mission by considering disturbances, while minimizing the moving distance of a robot. The proposed method can guarantee the safety of the planned trajectory by incorporating an LTL formula and chance constraints in a hierarchical manner. A high-level planner generates a discrete plan satisfying the mission requirements specified in LTL. A low-level planner builds a sampling-based rapidly exploring random tree search tree to minimize both the mission failure probability and the moving distance while guaranteeing the probability of collision with obstacles to be below a specified threshold. We have analyzed properties of the proposed algorithm theoretically and validated the robustness and safety of paths generated by the algorithm in simulation and experiments using a quadrotor.