Autonomous Navigation in Cluttered Environments

Autonomous navigation in cluttered environments is a necessary capability for emerging robotics applications, from home assistance to disaster rescue and logistics. It remains challenging because of ubiquitous uncertainty, a lack of theoretical guarantees, and high precision control requirements. This thesis studies the navigation problem in cluttered environments for mobile robots using only onboard sensors and without pre-built maps. This process is formulated as an optimization problem with a large number of collision avoidance constraints derived from surrounding obstacles, which is intractable to solve directly. The majority of the research community has converged on the idea of solving this NP-hard problem using model-based or data-driven approaches. Thus, this thesis first presents a data-driven collision avoidance approach for multi-robot systems. By incorporating the concept of reciprocal velocity obstacle (RVO) in the design of observation and reward functions, the training process becomes more stable and encourages the robot to adopt efficient reciprocal local collision avoidance behaviors. Furthermore, considering theoretical guarantees and full-dimensional collision avoidance challenges in previous learning based approaches, we present an accelerated model-based motion planner for cluttered environments. This planner can decompose the complex NP-hard problem into a series of simple convex subproblems and solve them in parallel to generate safe motion commands in real time. Finally, to solve this NP-hard optimization problem in an end-to-end manner, where the raw sensor data is mapped directly to actions, we combine the advantages of data-driven and model-based techniques to construct a model-based learning framework. The model-based module ensures the safety, generalization, and feasibility of the generated trajectory, while the data-driven module can handle hundreds of collision avoidance constraints in real time and improve performance by training with more data. All proposed methods are validated through both simulation and real-world experiments, demonstrating their effectiveness and efficiency.

[1] Daniel Coelho and Miguel Oliveira. “A review of end-to-end autonomous drivingin urban environments”. In: IEEE Access 10 (2022), pp. 75296–75311.
[2] Ruihua Han and Development Team. IR-SIM: A python based Lightweight intelligentrobot simulator. 2024. URL: https://github.com/hanruihua/ir-sim.
[3] Javier Alonso-Mora et al. “Optimal reciprocal collision avoidance for multiplenon-holonomic robots”. In: Distributed autonomous robotic systems. Springer,2013, pp. 203–216.
[4] Zhichao Han et al. “An efficient spatial-temporal trajectory planner for autonomousvehicles in unstructured environments”. In: IEEE Transactions on Intelligent TransportationSystems (2023).
[5] Christoph Rösmann, Frank Hoffmann, and Torsten Bertram. “Kinodynamic trajectoryoptimization and control for car-like robots”. In: 2017 IEEE/RSJ InternationalConference on Intelligent Robots and Systems (IROS). IEEE. 2017, pp. 5681–5686.
[6] Xiaojing Zhang, Alexander Liniger, and Francesco Borrelli. “Optimization-basedcollision avoidance”. In: IEEE Transactions on Control Systems Technology 29.3(2020), pp. 972–983.
[7] Changan Chen et al. “Crowd-robot interaction: Crowd-aware robot navigationwith attention-based deep reinforcement learning”. In: 2019 International Conferenceon Robotics and Automation (ICRA). IEEE. 2019, pp. 6015–6022.
[8] Shuaijun Wang et al. “Adaptive environment modeling based reinforcementlearning for collision avoidance in complex scenes”. In: 2022 IEEE/RSJ InternationalConference on Intelligent Robots and Systems (IROS). IEEE. 2022, pp. 9011–9018.
[9] Tingxiang Fan et al. “Distributed multi-robot collision avoidance via deep reinforcementlearning for navigation in complex scenarios”. In: The InternationalJournal of Robotics Research 39.7 (2020), pp. 856–892.
[10] Chonghao Sima et al. “DriveLM: Driving with Graph Visual Question Answering”.In: arXiv preprint arXiv:2312.14150 (2023).
[11] Ahmed Hussain Qureshi et al. “Motion planning networks: Bridging the gapbetween learning-based and classical motion planners”. In: IEEE Transactions onRobotics 37.1 (2020), pp. 48–66.
[12] Linjun Li et al. “Mpc-mpnet: Model-predictive motion planning networks forfast, near-optimal planning under kinodynamic constraints”. In: IEEE Roboticsand Automation Letters 6.3 (2021), pp. 4496–4503.
[13] Jur Van den Berg, Ming Lin, and Dinesh Manocha. “Reciprocal velocity obstaclesfor real-time multi-agent navigation”. In: 2008 IEEE international conferenceon robotics and automation. Ieee. 2008, pp. 1928–1935.
[14] Jamie Snape et al. “The hybrid reciprocal velocity obstacle”. In: IEEE Transactionson Robotics 27.4 (2011), pp. 696–706.
[15] Jur Van Den Berg et al. “Reciprocal n-body collision avoidance”. In: RoboticsResearch: The 14th International Symposium ISRR. Springer. 2011, pp. 3–19.
[16] Bharath Gopalakrishnan et al. “Prvo: Probabilistic reciprocal velocity obstaclefor multi robot navigation under uncertainty”. In: 2017 IEEE/RSJ InternationalConference on Intelligent Robots and Systems (IROS). IEEE. 2017, pp. 1089–1096.
[17] Ruihua, Han et al. “Reinforcement learned distributed multi-robot navigationwith reciprocal velocity obstacle shaped rewards”. In: IEEE Robotics and AutomationLetters (RAL) 7.3 (2022), pp. 5896–5903.
[18] Ruihua, Han et al. “RDA: An accelerated collision free motion planner for autonomousnavigation in cluttered environments”. In: IEEE Robotics and AutomationLetters (RAL) 8.3 (2023), pp. 1715–1722.
[19] Ruihua Han et al. “NeuPAN: Direct Point Robot Navigation with End-to-EndModel-based Learning”. In: arXiv preprint arXiv:2403.06828 (2024).
[20] Zeqing Zhang, Ruihua, Han, and Jia Pan. “An efficient centralized planner formultiple automated guided vehicles at the crossroad of polynomial curves”. In:IEEE Robotics and Automation Letters (RAL) 7.1 (2021), pp. 398–405.
[21] Shreyas Kousik et al. “Bridging the gap between safety and real-time performancein receding-horizon trajectory design for mobile robots”. In: The InternationalJournal of Robotics Research 39.12 (2020), pp. 1419–1469. ISSN: 0278-3649.
[22] Matteo Guerra et al. “Avoiding local minima in the potential field method usinginput-to-state stability”. In: Control Engineering Practice 55 (2016), pp. 174–184.
[23] Daniel Hennes et al. “Multi-robot collision avoidance with localization uncertainty.”In: AAMAS. 2012, pp. 147–154.
[24] Ruihua Han, Shengduo Chen, and Qi Hao. “A Distributed Range-Only CollisionAvoidance Approach for Low-cost Large-scale Multi-Robot Systems”. In: 2020IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE.2020, pp. 8020–8026.
[25] Ryan Lowe et al. “Multi-agent actor-critic for mixed cooperative-competitiveenvironments”. In: arXiv preprint arXiv:1706.02275 (2017).
[26] Pinxin Long et al. “Towards optimally decentralized multi-robot collision avoidancevia deep reinforcement learning”. In: 2018 IEEE International Conference onRobotics and Automation (ICRA). IEEE. 2018, pp. 6252–6259.
[27] Jing Liang et al. “Crowd-Steer: Realtime Smooth and Collision-Free Robot Navigationin Densely Crowded Scenarios Trained using High-Fidelity Simulation.”In: IJCAI. 2020, pp. 4221–4228.
[28] Michael Everett, Yu Fan Chen, and Jonathan P How. “Motion planning amongdynamic, decision-making agents with deep reinforcement learning”. In: 2018IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE.2018, pp. 3052–3059.
[29] Yu Fan Chen et al. “Socially aware motion planning with deep reinforcementlearning”. In: 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems(IROS). IEEE. 2017, pp. 1343–1350.
[30] Ruihua Han, Shengduo Chen, and Qi Hao. “Cooperative Multi-Robot Navigationin Dynamic Environment with Deep Reinforcement Learning”. In: 2020IEEE International Conference on Robotics and Automation (ICRA). IEEE. 2020, pp. 448–454.
[31] Michael Everett, Yu Fan Chen, and Jonathan P How. “Collision avoidance inpedestrian-rich environments with deep reinforcement learning”. In: IEEE Access9 (2021), pp. 10357–10377.
[32] Adarsh Jagan Sathyamoorthy Utsav Patel Nithish K Sanjeev Kumar and DineshManocha. “DWA-RL: Dynamically Feasible Deep Reinforcement Learning Policyfor Robot Navigation among Mobile Obstacles”. In: 2021 IEEE InternationalConference on Robotics and Automation (ICRA). IEEE. 2021.
[33] Daniel Claes and Karl Tuyls. “Multi robot collision avoidance in a shared workspace”.In: Autonomous Robots 42.8 (2018), pp. 1749–1770.
[34] Bharath Gopalakrishnan et al. “Prvo: Probabilistic reciprocal velocity obstaclefor multi robot navigation under uncertainty”. In: 2017 IEEE/RSJ InternationalConference on Intelligent Robots and Systems (IROS). IEEE. 2017, pp. 1089–1096.
[35] Yu Fan Chen et al. “Decentralized non-communicating multiagent collision avoidancewith deep reinforcement learning”. In: 2017 IEEE international conference onrobotics and automation (ICRA). IEEE. 2017, pp. 285–292.
[36] P. Wenzel et al. “Vision-Based Mobile Robotics Obstacle Avoidance With DeepReinforcement Learning”. In: ArXiv abs/2103.04727 (2021).
[37] ChengboWang et al. “Research on intelligent collision avoidance decision-makingof unmanned ship in unknown environments”. In: Evolving Systems (2019), pp. 1–10.
[38] Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton. “Layer normalization”.In: arXiv preprint arXiv:1607.06450 (2016).
[39] John Schulman et al. “Proximal policy optimization algorithms”. In: arXiv preprintarXiv:1707.06347 (2017).
[40] Greg Brockman et al. “Openai gym”. In: arXiv preprint arXiv:1606.01540 (2016).
[41] Marc-Oliver Sonneberg et al. “Autonomous unmanned ground vehicles for urbanlogistics: Optimization of last mile delivery operations”. In: Proceedings ofthe 52nd Hawaii International Conference on System Sciences. 2019.
[42] David González et al. “A review of motion planning techniques for automatedvehicles”. In: IEEE Transactions on Intelligent Transportation Systems 17.4 (2015),pp. 1135–1145.
[43] Mihail Pivtoraiko, RossAKnepper, and Alonzo Kelly. “Differentially constrainedmobile robot motion planning in state lattices”. In: Journal of Field Robotics 26.3(2009), pp. 308–333.
[44] Michael Montemerlo et al. “Junior: The stanford entry in the urban challenge”.In: Journal of Field Robotics 25.9 (2008), pp. 569–597.
[45] Rômulo Ramos Radaelli et al. “A motion planner for car-like robots based onrapidly-exploring random trees”. In: Advances in Artificial Intelligence–IBERAMIA2014: 14th Ibero-American Conference on AI, Santiago de Chile, Chile, November 24-27, 2014, Proceedings 14. Springer. 2014, pp. 469–480.
[46] Joseph Funke et al. “Up to the limits: Autonomous Audi TTS”. In: 2012 IEEEIntelligent Vehicles Symposium. IEEE. 2012, pp. 541–547.
[47] Manel Ammour, Rodolfo Orjuela, and Michel Basset. “Collision avoidance forautonomous vehicle using MPC and time varying Sigmoid safety constraints”.In: IFAC-PapersOnLine 54.10 (2021), pp. 39–44.
[48] Felix Rey et al. “Fully decentralized admm for coordination and collision avoidance”.In: 2018 European Control Conference (ECC). IEEE. 2018, pp. 825–830.
[49] ZhitaoWang et al. “Parallel optimal control for cooperative automation of largescaleconnected vehicles via admm”. In: 2018 21st International Conference on IntelligentTransportation Systems (ITSC). IEEE. 2018, pp. 1633–1639.
[50] Zhepei Wang et al. “Geometrically constrained trajectory optimization for multicopters”.In: arXiv preprint arXiv:2103.00190 (2021).
[51] Weibo Xia, Weihong Wang, and Chuan Gao. “Trajectory optimization with obstaclesavoidance via strong duality equivalent and hp-pseudospectral sequentialconvex programming”. In: Optimal Control Applications and Methods 43.2 (2022),pp. 566–587.
[52] Zilong Cheng et al. “ADMM-based parallel optimization for multi-agent collisionfreemodel predictive control”. In: arXiv preprint arXiv:2101.09894 (2021).
[53] Roya Firoozi et al. “A distributed multi-robot coordination algorithm for navigationin tight environments”. In: arXiv preprint arXiv:2006.11492 (2020).
[54] Joseph Funke et al. “Collision avoidance and stabilization for autonomous vehiclesin emergency scenarios”. In: IEEE Transactions on Control Systems Technology25.4 (2016), pp. 1204–1216.
[55] Stephen M Erlien, Susumu Fujita, and J Christian Gerdes. “Safe driving envelopesfor shared control of ground vehicles”. In: IFAC Proceedings Volumes46.21 (2013), pp. 831–836.
[56] Erick J Rodrıéguez-Seda et al. “Trajectory tracking with collision avoidance fornonholonomic vehicles with acceleration constraints and limited sensing”. In:The International Journal of Robotics Research 33.12 (2014), pp. 1569–1592.
[57] Zeqing Zhang et al. “A generalized continuous collision detection frameworkof polynomial trajectory for mobile robots in cluttered environments”. In: IEEERobotics and Automation Letters (RAL) 7.4 (2022), pp. 9810–9817.
[58] Stephen Boyd et al. “Distributed optimization and statistical learning via thealternating direction method of multipliers”. In: Foundations and Trends® in Machinelearning 3.1 (2011), pp. 1–122.
[59] Stephen P Boyd and Lieven Vandenberghe. Convex optimization. Cambridge universitypress, 2004.
[60] Timothy Barfoot, James R Forbes, and Paul T Furgale. “Pose estimation usinglinearized rotations and quaternion algebra”. In: Acta Astronautica 68.1-2 (2011),pp. 101–112.
[61] KevinMLynch and Frank C Park. Modern Robotics. Cambridge University Press,2017.
[62] Steven Diamond and Stephen Boyd. “CVXPY: A Python-embedded modelinglanguage for convex optimization”. In: Journal of Machine Learning Research 17.83(2016), pp. 1–5.
[63] Andrei M Shkel and Vladimir Lumelsky. “Classification of the Dubins set”. In:Robotics and Autonomous Systems 34.4 (2001), pp. 179–202.
[64] Nathan Koenig and Andrew Howard. “Design and use paradigms for gazebo,an open-source multi-robot simulator”. In: 2004 IEEE/RSJ International Conferenceon Intelligent Robots and Systems (IROS)(IEEE Cat. No. 04CH37566). Vol. 3.IEEE. 2004, pp. 2149–2154.
[65] Martin Ester et al. “A density-based algorithm for discovering clusters in largespatial databases with noise.” In: kdd. Vol. 96. 34. 1996, pp. 226–231.
[66] Zipeng Fu, Tony Z. Zhao, and Chelsea Finn. “Mobile ALOHA: Learning BimanualMobile Manipulation with Low-Cost Whole-Body Teleoperation”. In: arXiv.2024.
[67] Tesla. AI & Robotics. https://www.tesla.com/AI. 2023.
[68] Shreyas Kousik et al. “Safe, optimal, real-time trajectory planning with a parallelconstrained bernstein algorithm”. In: IEEE Transactions on Robotics 37.3 (2020),pp. 815–830.
[69] Boyu Zhou et al. “Raptor: Robust and perception-aware trajectory replanningfor quadrotor fast flight”. In: IEEE Transactions on Robotics 37.6 (2021), pp. 1992–2009.
[70] Jesus Tordesillas et al. “Faster: Fast and safe trajectory planner for navigation inunknown environments”. In: IEEE Transactions on Robotics 38.2 (2021), pp. 922–938.
[71] Alessandro Devo et al. “Towards generalization in target-driven visual navigationby using deep reinforcement learning”. In: IEEE Transactions on Robotics 36.5(2020), pp. 1546–1561.
[72] Wei Xiao et al. “Barriernet: Differentiable control barrier functions for learningof safe robot control”. In: IEEE Transactions on Robotics (2023).
[73] Yihan Hu et al. “Planning-oriented autonomous driving”. In: Proceedings of theIEEE/CVF Conference on Computer Vision and Pattern Recognition. 2023, pp. 17853–17862.
[74] Zhiqi Li et al. “Bevformer: Learning bird’s-eye-view representation from multicameraimages via spatiotemporal transformers”. In: European Conference on ComputerVision. Springer. 2022, pp. 1–18.
[75] Lars Mescheder et al. “Occupancy networks: Learning 3d reconstruction in functionspace”. In: Proceedings of the IEEE/CVF Conference on Computer Vision andPattern Recognition. 2019, pp. 4460–4470.
[76] Oren Salzman and Dan Halperin. “Asymptotically near-optimal RRT for fast,high-quality motion planning”. In: IEEE Transactions on Robotics 32.3 (2016), pp. 473–483.
[77] Wenchao Ding et al. “Epsilon: An efficient planning system for automated vehiclesin highly interactive environments”. In: IEEE Transactions on Robotics 38.2(2021), pp. 1118–1138.
[78] Xin Zhou et al. “Ego-planner: An esdf-free gradient-based local planner forquadrotors”. In: IEEE Robotics and Automation Letters 6.2 (2020), pp. 478–485.
[79] Ardi Tampuu et al. “A survey of end-to-end driving: Architectures and trainingmethods”. In: IEEE Transactions on Neural Networks and Learning Systems 33.4(2020), pp. 1364–1384.
[80] Anthony Francis et al. “Long-range indoor navigation with prm-rl”. In: IEEETransactions on Robotics 36.4 (2020), pp. 1115–1134.
[81] Changan Chen et al. “Relational graph learning for crowd navigation”. In: 2020IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE.2020, pp. 10007–10013.
[82] Mariusz Bojarski et al. “End to end learning for self-driving cars”. In: arXivpreprint arXiv:1604.07316 (2016).
[83] Felipe Codevilla et al. “End-to-end driving via conditional imitation learning”.In: 2018 IEEE International Conference on Robotics and Automation (ICRA). IEEE.2018, pp. 4693–4700.
[84] Jiarong Lin et al. “Flying through a narrow gap using neural network: an end-toendplanning and control approach”. In: 2019 IEEE/RSJ International Conferenceon Intelligent Robots and Systems (IROS). IEEE. 2019, pp. 3526–3533.
[85] Tim Salzmann et al. “Real-time neural MPC: Deep learning model predictivecontrol for quadrotors and agile robotic platforms”. In: IEEE Robotics and AutomationLetters 8.4 (2023), pp. 2397–2404.
[86] Jacob Sacks and Byron Boots. “Learning Sampling Distributions for Model PredictiveControl”. In: Conference on Robot Learning. PMLR. 2023, pp. 1733–1742.
[87] Grady Williams et al. “Information-theoretic model predictive control: Theoryand applications to autonomous driving”. In: IEEE Transactions on Robotics 34.6(2018), pp. 1603–1622.
[88] Brandon Amos et al. “Differentiable mpc for end-to-end planning and control”.In: Advances in Neural Information Processing Systems 31 (2018).
[89] Akshay Agrawal, Shane Barratt, and Stephen Boyd. “Learning convex optimizationmodels”. In: IEEE/CAA Journal of Automatica Sinica 8.8 (2021), pp. 1355–1364.
[90] Yang Yang et al. “Inexact block coordinate descent algorithms for nonsmoothnonconvex optimization”. In: IEEE Transactions on Signal Processing 68 (2019),pp. 947–961.
[91] Karol Gregor and Yann LeCun. “Learning fast approximations of sparse coding”.In: Proceedings of the 27th international conference on international conferenceon machine learning. 2010, pp. 399–406.
[92] Nir Shlezinger et al. “Model-based deep learning”. In: Proceedings of the IEEE(2023).
[93] Alexey Dosovitskiy et al. “CARLA: An open urban driving simulator”. In: Conferenceon Robot Learning. PMLR. 2017, pp. 1–16.
[94] Adam Paszke et al. “Pytorch: An imperative style, high-performance deep learninglibrary”. In: arXiv preprint arXiv:1912.01703 (2019).
[95] Akshay Agrawal et al. “Differentiable convex optimization layers”. In: Advancesin Neural Information Processing systems 32 (2019).
[96] Wei Xu et al. “Fast-lio2: Fast direct lidar-inertial odometry”. In: IEEE Transactionson Robotics 38.4 (2022), pp. 2053–2073.
[97] Tixiao Shan and Brendan Englot. “Lego-loam: Lightweight and ground-optimizedlidar odometry and mapping on variable terrain”. In: 2018 IEEE/RSJ InternationalConference on Intelligent Robots and Systems (IROS). IEEE. 2018, pp. 4758–4765.
[98] Andreas Geiger, Philip Lenz, and Raquel Urtasun. “Are we ready for AutonomousDriving? The KITTI Vision Benchmark Suite”. In: Conference on Computer Visionand Pattern Recognition (CVPR). 2012.
[99] Alex H Lang et al. “Pointpillars: Fast encoders for object detection from pointclouds”. In: Proceedings of the IEEE/CVF Conference on Computer Vision and PatternRecognition. 2019, pp. 12697–12705.
[100] Wolfgang Hess et al. “Real-time loop closure in 2D LIDAR SLAM”. In: 2016 IEEEInternational Conference on Robotics and Automation (ICRA). IEEE. 2016, pp. 1271–1278.
[101] Giseop Kim and Ayoung Kim. “Scan Context: Egocentric Spatial Descriptor forPlace Recognition within 3D Point Cloud Map”. In: Proceedings of the IEEE/RSJInternational Conference on Intelligent Robots and Systems. Madrid, Oct. 2018.
[102] Karl Kurzer. Path planning in unstructured environments: A real-time hybrid a* implementationfor fast and deterministic path generation for the kth research conceptvehicle. 2016.
[103] Shinpei Kato et al. “Autoware on board: Enabling autonomous vehicles withembedded systems”. In: 2018 ACM/IEEE 9th International Conference on Cyber-Physical Systems (ICCPS). IEEE. 2018, pp. 287–296.
[104] Bernhard Kerbl et al. “3d gaussian splatting for real-time radiance field rendering”.In: ACM Transactions on Graphics 42.4 (2023), pp. 1–14.
[105] J. Bolte, Shoham Sabach, and Marc Teboulle. “Proximal Alternating LinearizedMinimization for Nonconvex and Nonsmooth Problems”. In: Mathematical Programming146 (2014), pp. 459–494.