A novel robust solution to motion planning in the presence of moving obstacles is presented in this paper. The proposed method addresses the uncertainty in the robot state estimate, as well as in the estimate of the a-priori unknown obstacles motion. Our scheme employs the globally optimal state-feedback velocity field for static workspaces and exploits its topological properties to enable moving obstacles avoidance. In contrast to previous relevant contributions, our method tackles polygonal obstacles and accounts for both the obstacles geometry and the approximate motion profile to extract a reactive solution. Furthermore, the proposed kinematic planner is extended to a class of second-order systems. Our multi-layered approach integrates robust safety filtering and exhibits superior performance w.r.t. relevant methods. In summary, this work consists an important step towards bridging the gap between open-loop planning and state-feedback control.
AgrawalDRPanagouD (2023) Safe and robust observer-controller synthesis using control barrier functions. IEEE Control Systems Letters7: 127–132. DOI: 10.1109/LCSYS.2022.3185142.
2.
AnastopoulosNNikasKGoumasG, et al. (2009) Early experiences on accelerating dijkstra’s algorithm using transactional memory. In Proceedings of the 2009 IEEE International Parallel and Distributed Processing Symposium.
3.
BechlioulisCPKyriakopoulosKJ (2018) Collaborative multi-robot transportation in obstacle-cluttered environments via implicit communication. Frontiers in Robotics and AI5: 1. DOI: 10.3389/frobt.2018.00090. https://www.frontiersin.org/articles/10.3389/frobt.2018.00090
4.
BlackMFainekosGHoxhaB, et al. (2023) Safety under uncertainty: tight bounds with risk-aware control barrier functions. In 2023 IEEE International Conference on Robotics and Automation (ICRA), 12686–12692. DOI: 10.1109/ICRA48891.2023.10161379.
5.
BryshnikovY (2022) Topological perplexity of feedback stabilization. Journal of Applied and Computational Topology7: 75–87.
6.
DixitALindemannLWeiSX, et al. (2023) Adaptive conformal prediction for motion planning among dynamic agents. In: MatniNMorariMPappasGJ (eds) Proceedings of the 5th Annual Learning for Dynamics and Control Conference, Proceedings of Machine Learning Research. PMLR, Vol. 211, 300–314. https://proceedings.mlr.press/v211/dixit23a.html
7.
FanLLiuJ (2022) Mobile robot navigation in complex polygonal workspaces using conformal navigation transformations. https://arxiv.org/abs/2208.09635. DOI: 10.48550/ARXIV.2208.09635.
8.
FanLLiuJZhangW, et al. (2022) Conformal navigation transformations with application to robot navigation in complex workspaces. https://arxiv.org/abs/2208.06876. DOI: 10.48550/ARXIV.2208.06876.
9.
FukudaSSatohYSakataO (2020) Trajectory-tracking control considering obstacle avoidance by using control barrier function. In: 2020 International Automatic Control Conference (CACS), 1–6. DOI: 10.1109/CACS50047.2020.9289780.
10.
GargKPanagouD (2021) Robust control barrier and control lyapunov functions with fixed-time convergence guarantees. In: 2021 American Control Conference (ACC), 2292–2297. DOI: 10.23919/ACC50511.2021.9482751.
11.
GiernackiWSkwierczyńskiMWitwickiW, et al. (2017) Crazyflie 2.0 quadrotor as a platform for research and education in robotics and control engineering. In: 2017 22nd International Conference on Methods and Models in Automation and Robotics (MMAR), 37–42. DOI: 10.1109/MMAR.2017.8046794.
12.
HowardTPivtoraikoMKnepperRA, et al. (2014) Model-predictive motion planning: several key developments for autonomous mobile robots. IEEE Robotics and Automation Magazine21(1): 64–73. DOI: 10.1109/MRA.2013.2294914.
13.
HuberLBillardASlotineJJ (2019) Avoidance of convex and concave obstacles with convergence ensured through contraction. IEEE Robotics and Automation Letters4(2): 1462–1469. DOI: 10.1109/LRA.2019.2893676.
14.
HuberLSlotineJJBillardA (2023) Fast obstacle avoidance based on real-time sensing. IEEE Robotics and Automation Letters8(3): 1375–1382. DOI: 10.1109/LRA.2022.3232271.
15.
JaffarMKMOtteM (2023) Pip-x: online feedback motion planning/replanning in dynamic environments using invariant funnels. The International Journal of Robotics Research0(0): 02783649231209340, DOI: 10.1177/02783649231209340.
16.
JailletLCortesJSimeonT (2008) Transition-based rrt for path planning in continuous cost spaces. In: IEEE/RSJ International Conference on Intelligent Robots and Systems, 2145–2150. DOI: 10.1109/IROS.2008.4650993.
17.
JansonLHuTPavoneM (2018) Safe motion planning in unknown environments: optimality benchmarks and tractable policies. DOI:10.15607/RSS.2018.XIV.061.
18.
KaramanSFrazzoliE (2011) Sampling-based algorithms for optimal motion planning. The International Journal of Robotics Research30(7): 846–894. DOI: 10.1177/0278364911406761.
19.
KavrakiLSvestkaPLatombeJC, et al. (1996) Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Transactions on Robotics and Automation12(4): 566–580. DOI: 10.1109/70.508439.
20.
KimJKhoslaP (1991) Real-time obstacle avoidance using harmonic potential functions. In: IEEE International Conference on Robotics and Automation. IEEE Computer Society, 790–796. DOI: 10.1109/ROBOT.1991.131683.
21.
KoditschekDERimonE (1990) Robot navigation functions on manifolds with boundary. Advances in Applied Mathematics11(4): 412–442. DOI: 10.1016/0196-8858(90)90017-S.
22.
KoenigSLikhachevM (2002) D*lite. In: Proceedings of the National Conference on Artificial Intelligence, 476–483.
LiLMiaoYQureshiAH, et al. (2021) Mpc-mpnet: model-predictive motion planning networks for fast, near-optimal planning under kinodynamic constraints. IEEE Robotics and Automation Letters6(3): 4496–4503. DOI: 10.1109/LRA.2021.3067847.
25.
LiuXGongD (2011) A comparative study of a-star algorithms for search and rescue in perfect maze. In: International Conference on Electric Information and Control Engineering, 24–27. DOI: 10.1109/ICEICE.2011.5777723.
26.
LiuCLeeSVarnhagenS, et al. (2017) Path planning for autonomous vehicles using model predictive control. In: 2017 IEEE Intelligent Vehicles Symposium (IV), 174–179. DOI: 10.1109/IVS.2017.7995716.
27.
LoizouSG (2011) Closed form navigation functions based on harmonic potentials. In: 2011 50th IEEE Conference on Decision and Control and European Control Conference, 6361–6366. DOI: 10.1109/CDC.2011.6161438.
MiuraTAkaiNHondaK, et al. (2024) Spline-interpolated model predictive path integral control with stein variational inference for reactive navigation.
31.
MohamedISAllibertGMartinetP (2020) Model predictive path integral control framework for partially observable navigation: a quadrotor case study. In: 2020 16th International Conference on Control, Automation, Robotics and Vision (ICARCV), 196–203. DOI: 10.1109/ICARCV50220.2020.9305363.
32.
NicotraMMGaroneE (2018) The explicit reference governor: a general framework for the closed-form control of constrained nonlinear systems. IEEE Control Systems Magazine38(4): 89–107. DOI: 10.1109/MCS.2018.2830081.
33.
NilssonNJ (1969) A mobile automaton: an application of artificial intelligence techniques. In: International Joint Conference on Artificial Intelligence. https://api.semanticscholar.org/CorpusID:12735356
34.
NoreenIKhanAHabibZ (2016) Optimal path planning using rrt* based approaches: a survey and future directions. International Journal of Advanced Computer Science and Applications7(11): 1–16.
35.
PanagouDTannerHGKyriakopoulosKJ (2011) Control of nonholonomic systems using reference vector fields. In: 2011 50th IEEE Conference on Decision and Control and European Control Conference, 2831–2836. DOI: 10.1109/CDC.2011.6160922.
36.
QiJYangHSunH (2021) Mod-rrt*: a sampling-based algorithm for robot path planning in dynamic environment. IEEE Transactions on Industrial Electronics68(8): 7244–7251. DOI: 10.1109/TIE.2020.2998740.
37.
RimonEKoditschekD (1992) Exact robot navigation using artificial potential functions. IEEE Transactions on Robotics and Automation8(5): 501–518. DOI: 10.1109/70.163777.
38.
RousseasPBechlioulisCKyriakopoulosK (2021) Harmonic-based optimal motion planning in constrained workspaces using reinforcement learning. IEEE Robotics and Automation Letters6(2): 2005–2011. DOI: 10.1109/LRA.2021.3060711.
39.
RousseasPBechlioulisCKyriakopoulosK (2023a) A continuous off-policy reinforcement learning scheme for optimal motion planning in simply-connected workspaces. In: (Accepted) IEEE International Conference on Robotics and Automation. IEEE.
40.
RousseasPBechlioulisCKyriakopoulosK (2023b) State-feedback optimal motion planning in the presence of obstacles. IEEE Robotics and Automation Letters.
41.
RousseasPBechlioulisCKyriakopoulosK (2024a) An efficient solution to optimal motion planning with provable safety and convergence. IEEE Open Journal of Control Systems3: 143–157. DOI: 10.1109/OJCSYS.2024.3378055.
42.
RousseasPBechlioulisCKyriakopoulosK (2024b) Reactive optimal motion planning to anywhere in the presence of moving obstacles. (Accepted) International Journal of Robotics Research.
43.
RudinNHoellerDBjelonicM, et al. (2022) Advanced skills by learning locomotion and local navigation end-to-end. In: 2022 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2497–2503. DOI: 10.1109/IROS47612.2022.9981198.
44.
ShenZWilsonJPGuptaS, et al. (2023) Smart: self-morphing adaptive replanning tree. IEEE Robotics and Automation Letters8(11): 7312–7319. DOI: 10.1109/LRA.2023.3315210.
45.
SinghSLandryBMajumdarA, et al. (2023) Robust feedback motion planning via contraction theory. The International Journal of Robotics Research42(9): 655–688. DOI: 10.1177/02783649231186165.
46.
SundarSShillerZ (1997) Optimal obstacle avoidance based on the Hamilton-Jacobi-bellman equation. IEEE Transactions on Robotics and Automation13(2): 305–310. DOI: 10.1109/70.563653.
47.
TanXCortezWSDimarogonasDV (2022) High-order barrier functions: robustness, safety, and performance-critical control. IEEE Transactions on Automatic Control67(6): 3021–3028. DOI: 10.1109/TAC.2021.3089639.
48.
ThomasonWKingstonZKavrakiLE (2023) Motions in microseconds via vectorized sampling-based planning.
49.
TsukamotoHChungSJ (2021) Learning-based robust motion planning with guaranteed stability: a contraction theory approach. IEEE Robotics and Automation Letters6(4): 6164–6171. DOI: 10.1109/LRA.2021.3091019.
50.
VlantisPVrohidisCBechlioulisCP, et al. (2018) Robot navigation in complex workspaces using harmonic maps. In: 2018 IEEE International Conference on Robotics and Automation (ICRA), 1726–1731. DOI: 10.1109/ICRA.2018.8460695.
51.
WangYXuX (2023) Disturbance observer-based robust control barrier functions. In: 2023 American Control Conference (ACC), 3681–3687. DOI: 10.23919/ACC55779.2023.10156095.
52.
WangJMengMQHKhatibO (2020a) Eb-rrt: optimal motion planning for mobile robots. IEEE Transactions on Automation Science and Engineering17(4): 2063–2073. DOI: 10.1109/TASE.2020.2987397.
53.
WangZLiYZhangH, et al. (2020b) Sampling-based optimal motion planning with smart exploration and exploitation. IEEE25(5): 2376–2386. DOI: 10.1109/TMECH.2020.2973327.
54.
WebbDJvan den BergJ (2012) Kinodynamic rrt*: optimal motion planning for systems with linear differential constraints. CoRR abs/1205 5088. https://arxiv.org/abs/1205.5088
55.
WeiCChenCTannerHG (2023) Navigation functions with moving destinations and obstacles. Autonomous Robots47(4): 435–451, DOI: 10.1007/s10514-023-10088-7.
56.
WuALewTSoloveyK, et al. (2022) Robust-rrt: probabilistically-complete motion planning for uncertain nonlinear systems. In: International Symposium on Robotics Research.
57.
XiaoWBeltaC (2022) High-order control barrier functions. IEEE Transactions on Automatic Control67(7): 3655–3662. DOI: 10.1109/TAC.2021.3105491.
58.
YangGCaiMAhmadA, et al. (2023) Efficient lqr-cbf-rrt*: safe and optimal motion planning.
59.
YuHChenY (2023) A Gaussian variational inference approach to motion planning. IEEE Robotics and Automation Letters8(5): 2518–2525. DOI: 10.1109/LRA.2023.3256134.
60.
ZhangYWangHYinM, et al. (2024) Bi-am-rrt*: a fast and efficient sampling-based motion planning algorithm in dynamic environments. IEEE Transactions on Intelligent Vehicles9(1): 1282–1293. DOI: 10.1109/TIV.2023.3307283.
61.
ZhouCHuangBFräntiP (2022) A review of motion planning algorithms for intelligent robots. Journal of Intelligent Manufacturing33: 387–424. DOI: 10.1007/s10845-021-01867-z.
Supplementary Material
Please find the following supplemental material available below.
For Open Access articles published under a Creative Commons License, all supplemental material carries the same license as the article it is associated with.
For non-Open Access articles published, all supplemental material carries a non-exclusive license, and permission requests for re-use of supplemental material or any part of supplemental material shall be sent directly to the copyright owner as specified in the copyright notice associated with the article.
