Robots in Partially Known and Unknown Environments: A Simulated Annealing Approach for Re-Planning
Source abstract
Abstract
The path planning problem using mobile robots, also known as robot motion planning, is a key problem in robotics. The goal is to find a collision-free path from a starting point to a target point in an environment with obstacles. These obstacles can be known, partially unknown, or completely unknown to the robot. The robot’s decisions are different according to its degree of knowledge of the environment. If the environment is fully known, using an offline approach is sufficient. Otherwise, online techniques are required to find a path. They must be fast, effective, and adaptive to tackle the complexity of changing environments. In this work, we propose a framework based on a simulated annealing approach to solve the path planning problem with different degrees of knowledge of the environment for the robot. We evaluate our approach with a set of large-scale instances with different features. The results show that our framework can quickly find quality solutions and is also able to manage environmental changes.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Robotic Path Planning Algorithms · AI-based Problem Solving and Planning · Robotics and Sensor-Based Localization
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Departament of Computer Science, Universidad Técnica Federico Santa María, Valparaíso 2390123, Chile
Department of Human-centered Design and Engineering, University of Washington, Seattle, WA 98195, USA
Funding
Fondecyt Project
References (40)
Show source-provided references
1. Benchmarking motion planning algorithms: An extensible infrastructure for analysis and visualization10.1109/MRA.2015.2448276 ↗
2. Path planning for autonomous mobile robot navigation with ant colony optimization and fuzzy cost function evaluation10.1016/j.asoc.2009.02.014 ↗
3. Mobile robot path planning with surrounding point set and path improvement10.1016/j.asoc.2017.03.035 ↗
4. Solving the motion planning problem using learning experience through case-based reasoning and machine learning algorithms10.1016/j.asej.2019.10.007 ↗
5. Motion planning10.1109/MRA.2011.940276 ↗
6. Canny, J. (1988). The Complexity of Robot Motion Planning, MIT Press.10.1109/SFCS.1988.21947 ↗
7. Classic and heuristic approaches in robot motion planning-a chronological review
8. Asano, T., Asano, T., Guibas, L., Hershberger, J., and Imai, H. (1985, January 21–23). Visibility-polygon search and euclidean shortest paths. Proceedings of the Foundations of Computer Science, 26th Annual Symposium, Portland, OR, USA.10.1109/SFCS.1985.65 ↗
9. Canny, J. (1987, January 12–14). A new algebraic method for robot motion planning and real geometry. Proceedings of the Foundations of Computer Science, 28th Annual Symposium, Washington, DC, USA.10.1109/SFCS.1987.1 ↗
10. Latombe, J.C. (2012). Robot Motion Planning, Springer Science & Business Media.
11. Short, A., Pan, Z., Larkin, N., and van Duin, S. (2016, January 12–15). Recent progress on sampling based dynamic motion planning algorithms. Proceedings of the Advanced Intelligent Mechatronics (AIM), 2016 IEEE International Conference, Banff, AB, Canada.10.1109/AIM.2016.7576950 ↗
12. Measure Theoretic Analysis of Probabilistic Path Planning10.1109/TRA.2004.824649 ↗
13. Randomized Kinodynamic Planning10.1177/02783640122067453 ↗
14. Research on Robot Motion Planning Based on RRT Algorithm with Nonholonomic Constraints10.1007/s11063-021-10536-4 ↗
15. Optimal Path Planning using RRT* based Approaches: A Survey and Future Directions
16. Multi-Tree Guided Efficient Robot Motion Planning10.1016/j.procs.2022.10.096 ↗
17. An efficient motion planning based on grid map: Predicted Trajectory Approach with global path guiding10.1016/j.oceaneng.2021.109696 ↗
18. Sampling-based Motion Planning with Temporal Logic Missions and Spatial Preferences10.1016/j.ifacol.2020.12.2397 ↗
19. Sugihara, K., and Smith, J. (1997, January 10–11). Genetic algorithms for adaptive motion planning of an autonomous mobile robot. Proceedings of the Computational Intelligence in Robotics and Automation, Monterey, CA, USA.
20. Zhu, Q., Yan, Y., and Xing, Z. (2006, January 16–18). Robot path planning based on artificial potential field approach with simulated annealing. Proceedings of the Sixth International Conference on Intelligent Systems Design and Applications, Jinan, China.10.1109/ISDA.2006.253908 ↗
21. A fast two-stage ACO algorithm for robotic path planning10.1007/s00521-011-0682-7 ↗
22. Leu, J., Zhang, G., Sun, L., and Tomizuka, M. (2021, January 26–28). Efficient Robot Motion Planning via Sampling and Optimization. Proceedings of the 2021 American Control Conference (ACC), New Orleans, LA, USA.10.23919/ACC50511.2021.9483146 ↗
23. Sampling-based algorithms for optimal motion planning10.1177/0278364911406761 ↗
24. A residual convolutional neural network based approach for real-time path planning10.1016/j.knosys.2022.108400 ↗
25. Zacksenhouse, M., DeFigueiredo, R.J., and Johnson, D.H. (1988, January 7–9). A neural network architecture for cue-based motion planning. Proceedings of the Conference on Decision and Control, Austin, TX, USA.
26. Neural network dynamics for path planning and obstacle avoidance10.1016/0893-6080(94)E0045-M ↗
27. Alfaro, T., and Riff, M.C. (2005). An on-the-fly evolutionary algorithm for robot motion planning. Evolvable Systems: From Biology to Hardware, Springer.10.1007/11549703_12 ↗
28. An evolutionary navigator for autonomous agents on unknown large-scale environments10.1080/10798587.2008.10642986 ↗
29. Adaptive evolutionary planner/navigator for mobile robots10.1109/4235.585889 ↗
30. Convolutionally Evaluated Gradient First Search Path Planning Algorithm without Prior Global Maps10.1016/j.robot.2021.103985 ↗
31. Distributed real-time control architecture for electrohydraulic humanoid robots
32. Data-Driven Learning for H Control of Adaptive Cruise Control Systems
33. Path planning in uncertain environment by using firefly algorithm10.1016/j.dt.2018.06.004 ↗
34. A surrounding point set approach for path planning in unknown environments10.1016/j.cie.2019.05.013 ↗
35. Figueroa, A., Montero, E., and Riff, M.C. (2017, January 6–8). An Effective Simulated Annealing for Off-Line Robot Motion Planning. Proceedings of the 29th IEEE International Conference on Tools with Artificial Intelligence, ICTAI 2017, Boston, MA, USA.10.1109/ICTAI.2017.00148 ↗
36. Nosal, E.M. (2008, January 14–17). Flood-fill algorithms used for passive acoustic detection and tracking. Proceedings of the New Trends for Environmental Monitoring Using Passive Systems, Hyeres, France.10.1109/PASSIVE.2008.4786975 ↗
37. A beginner’s guide to tuning methods10.1016/j.asoc.2013.12.017 ↗
38. ParamILS: An Automatic Algorithm Configuration Framework10.1613/jair.2861 ↗
39. Boor, V., Overmars, M., and van der Stappen, A. (1999, January 10–15). The Gaussian sampling strategy for probabilistic roadmap planners. Proceedings of the 1999 IEEE International Conference on Robotics and Automation (Cat. No.99CH36288C), Detroit, MI, USA.
40. Montero, E. (2024, November 12). Adaptive MRP Problem Instances. Available online: https://github.com/elimail/AdaptiveMRPProblemInstances.