Kourosh Naderi
ABSTRACT
This paper presents a novel algorithm for real-time path-planning in a dynamic environment such as a computer game. We utilize a real-time sampling approach based on the Rapidly Exploring Random Tree (RRT) algorithm that has enjoyed wide success in robotics. More specifically, our algorithm is based on the RRT* and informed RRT* variants. We contribute by introducing an online tree rewiring strategy that allows the tree root to move with the agent without discarding previously sampled paths. Our method also does not have to wait for the tree to be fully built, as tree expansion and taking actions are interleaved. To our knowledge, this is the first real-time variant of RRT*.
We demonstrate our method, dubbed Real-Time RRT* (RT-RRT*), in navigating a maze with moving enemies that the controlled agent is required to avoid within a predefined radius. Our method finds paths to new targets considerably faster when compared to CL-RRT, a previously proposed real-time RRT variant.
Supplemental Material
- Bruce, J., and Veloso, M. 2002. Real-time randomized path planning for robot navigation. In IROS, IEEE.Google Scholar
- Cannon, J., Rose, K., and Ruml, W. 2012. Real-Time Motion Planning with Dynamic Obstacles. In Symposium on Combinatorial Search.Google Scholar
- Gammell, D, J., Srinivasa, S, S., Barfoot, and D, T. 2014. Informed RRT*: Optimal Sampling-based Path Planning Focused via Direct Sampling of an Admissible Ellipsoidal Heuristic. In IROS, IEEE.Google Scholar
- Gutmann, J.-S., Fukuchi, M., and Fujita, M. 2005. Real-time path planning for humanoid robot navigation. In IJCAI. Google ScholarDigital Library
- Hämäläinen, P., Rajamäki, J., and Liu, C. K. 2015. Online Control of Simulated Humanoids Using Particle Belief Propagation. In Proc. SIGGRAPH '15, ACM.Google Scholar
- Karaman, S., and Frazzoli, E. 2011. Sampling-based Algorithms for Optimal Motion Planning. Int. J. Rob. Res.. Google ScholarDigital Library
- Kavraki, L. E., Švestka, P., Latombe, J.-C., and Overmars, M. H. 1996. Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Trans. Robot. Autom..Google ScholarCross Ref
- Khatib, O. 1986. Real-time obstacle avoidance for manipulators and mobile robots. The International Journal of Robotics Research. Google ScholarDigital Library
- LaValle, S. M. 1998. Rapidly-Exploring Random Trees: A new Tool for Path Planning.Google Scholar
- Luders, B. D., Karaman, S., Frazzoli, E., and How, J. P. 2010. Bounds on tracking error using closed-loop rapidly-exploring random trees. In American Control Conference, IEEE.Google Scholar
- Otte, M., and Frazzoli, E. 2015. RRTX: Real-time motion planning/replanning for environments with unpredictable obstacles. In Algorithmic Foundations of Robotics XI. Springer.Google Scholar
- Rastgoo, M. N., Nakisa, B., Nasrudin, M. F., Nazri, A., and Zakree, M. 2014. A critical evaluation of literature on robot path planning in dynamic environment. Journal of Theoretical & Applied Information Technology.Google Scholar
- Song, S., Liu, W., Wei, R., Xing, W., and Ren, C. 2014. Path planning directed motion control of virtual humans in complex environments. Journal of Visual Languages & Computing.Google ScholarDigital Library
- Sturtevant, N. R., Bulitko, V., and Björnsson, Y. 2010. On learning in agent-centered search. In AAMAS. Google ScholarDigital Library
- Sud, A., Andersen, E., Curtis, S., Lin, M., and Manocha, D. 2008. Real-time path planning for virtual agents in dynamic environments. In ACM SIGGRAPH 2008 Classes, ACM. Google ScholarDigital Library
Index Terms
- RT-RRT*: a real-time path planning algorithm based on RRT*
Recommendations
Deep Learning rooted Potential piloted RRT* for expeditious Path Planning
CACRE2019: Proceedings of the 2019 4th International Conference on Automation, Control and Robotics EngineeringRandomised sampling-based algorithms such as RRT and RRT* have widespread use in path planning, but they tend to take a considerable amount of time and space to converge towards the destination. RRT* with artificial potential field (RRT*-APF) is a novel ...
AM-RRT*: An Automatic Robot Motion Planning Algorithm Based on RRT
Neural Information ProcessingAbstractMotion planning is a very important part of robot technology, where the quality of planning directly affects the energy consumption and safety of robots. Focusing on the shortcomings of traditional RRT methods such as long, unsmooth paths, and ...
Path planning for crawler crane using RRT*
ICICA'12: Proceedings of the Third international conference on Information Computing and ApplicationsLift path planning is a key subtask in preparing lift plan. Many researchers have concerned the topic of automated path planning for crane lifts. Previous studies provided some exact approaches or optimization methods to solve the problem. However, ...
Comments