Hostname: page-component-586b7cd67f-dsjbd Total loading time: 0 Render date: 2024-11-22T13:23:45.798Z Has data issue: false hasContentIssue false
  • English
  • Français

NRR: a nonholonomic random replanner for navigation of car-like robots in unknown environments

Published online by Cambridge University Press:  15 January 2014

Ellips Masehian  and
Hossein Kakahaji
Ellips Masehian
Affiliation:
Faculty of Engineering, Tarbiat Modares University, Jalalé Alé Ahmad, Tehran, Iran
Hossein Kakahaji*
Affiliation:
Sama Technical and Vocational Training College, Islamic Azad University, Tehran Branch, Tehran, Iran
*
*Corresponding author. E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Summary

In this paper, a new sensor-based approach called nonholonomic random replanner (NRR) is presented for motion planning of car-like mobile robots. The robot is incrementally directed toward its destination using a nonholonomic rapidly exploring random tree (RRT) algorithm. At each iteration, the robot's perceived map of the environment is updated using sensor readings and is used for local motion planning. If the goal was not visible to the robot, an approximate path toward the goal is calculated and the robot traces it to an extent within its sensor range. The robot updates its motion to goal through replanning. This procedure is repeated until the goal lies within the scope of the robot, after which it finds a more precise path by sampling in a tighter Goal Region for the nonholonomic RRT. Three main replanning strategies are proposed to decide when to perform a visibility scan and when to replan a new path. Those are named Basic, Deliberative and Greedy strategies, which yield different paths. The NRR was also modified for motion planning of Dubin's car-like robots. The proposed algorithm is probabilistically complete and its effectiveness and efficiency were tested by running several simulations and the resulting runtimes and path lengths were compared to the basic RRT method.

Keywords

Sensor-based motion planningCar-like robotsNonholonomic constraintsReplanning strategySampling-based methods
Type
Articles
Information
Robotica , Volume 32 , Issue 7 , October 2014 , pp. 1101 - 1123
Copyright
Copyright © Cambridge University Press 2014 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1.Rimon, E. and Koditschek, D. E., “Exact robot navigation using artificial potential functions,” IEEE Trans. Robot. Autom. 8, 501–518 (1992).Google Scholar
2.Rohnert, H., “Shortest path in the plane with convex polygonal obstacles,” Inf. Process. Lett. 23, 71–76 (1986).Google Scholar
3.Kamon, E., Rimon, E. and Rivlin, E., “Tangentbug: A range-sensor based navigation algorithm,” Int. J. Robot. Res. 17, 934–953 (1998).Google Scholar
4.Choset, H., Walker, S., Eiamsa-Ard, K. and Burdick, J., “Sensor–based exploration: Incremental construction of the hierarchical generalized Voronoi graph,” Int. J. Robot. Res. 19, 126–148 (2000).CrossRefGoogle Scholar
5.Masehian, E. and Amin-Naseri, M. R., “Sensor-based robot motion planning a tabu search approach,” J. Robot. Autom. 15, 48–57 (2008).Google Scholar
6.Murray, R. M., “Nonholonomic motion planning: Steering using sinusoids,” IEEE Trans. Autom. Control 38, 700–716 (1993).Google Scholar
7.Barraquand, J. and Latombe, J. C., “Nonholonomic multibody mobile robots: Controllability and motion planning in the presence of obstacles,” J. Algorithmica 10, 121–155 (1993).Google Scholar
8.Laumond, J. P., Jacobs, P. E., Taix, M. and Murray, R. M., “A motion planner for nonholonomic mobile robots,” IEEE Trans. Robot. Autom. 10, 577–593 (1994).Google Scholar
9.Khatib, M., Jaouni, H., Chatila, R. and Laumod, J. P., “Dynamic Path Modification for Car-Like Nonholonomic Mobile Robots,” Proceedings of IEEE International Conference on Robotics and Automation, Albuquerque NM (Apr. 20–25, 1997) pp. 2920–2925.Google Scholar
10.Kavraki, L. E., Svestka, P., Latombe, J. C. and Overmars, M. H., “Probabilistic roadmaps for path planning in high-dimensional configuration spaces,” IEEE Trans. Robot. Autom. 12, 566–580 (1996).Google Scholar
11.LaValle, S. M., Rapidly-Exploring Random Trees: A New Tool for Path Planning (Computer Science Department, Iowa State University, Ames, IA, 1998).Google Scholar
12.Svestka, P. and Overmars, M. H., “Motion planning for car-like robots, a probabilistic learning approach,” Int. J. Robot. Res. 16, 119–143 (1997).CrossRefGoogle Scholar
13.LaValle, S. M. and Kuffner, J. J., “Randomized kinodynamic planning,” Int. J. Robot. Res. 20, 378–400 (2001).Google Scholar
14.LaValle, S. M. and Kuffner, J. J., “Rapidly-Exploring Random Trees: Progress and Prospects,” In: Algorithmic and Computational Robototics: New Directions (Donald, B. R., Lynch, K. M. and Rus, D., eds.) (A K Peters, Natick, MA, 2001) pp. 293–308.Google Scholar
15.Nietro, J., Slawinski, E., Mut, V. and Wagner, B., “Online Path Planning Based on Rapidly-Exploring Random Trees,” Proceedings of IEEE International Conference on Industrial Technology (ICIT), Vi a del Mar, Chile (Mar. 14–17, 2010) pp. 1451–1456.Google Scholar
16.Lanzoni, C., Sanchez, A. and Zapata, R., “Sensor-Based Motion Planning for Car-Like Mobile Robots in Unknown Environments,” Proceedings of IEEE International Conference on Robotics and Automation, Taipei, Taiwan (Sep. 14–19, 2003) pp. 4258–4263.Google Scholar
17.Reeds, J. A. and Shepp, R. A., “Optimal paths for a car that goes both forward and backwards,” Pac. J. Math. 145, 367–393 (1990).CrossRefGoogle Scholar
18.Ferguson, D., Kalra, N. and Stentz, N., “Replanning with RRTs,” Proceedings of the IEEE International Conference on Robotics and Automation, Orlando, FL (May 15–19, 2006) pp. 1243–1248.Google Scholar
19.Noborio, H., Yamamoto, I. and Kom, T., “Sensor-Based Path-Planning Algorithms for a Nonholonomic Mobile Robot,” Proceedings of IEEE International Conference on Intelligent Robots and Systems, Takamatsu, Japan (Oct. 31, 2000) pp. 917–924.Google Scholar
20.Nagatani, K., Iwai, Y. and Tanaka, Y., “Sensor Based Navigation for Car-Like Mobile Robots Using Generalized Voronoi Graph,” Proceedings of IEEE International Conference on Intelligent Robots and Systems, Maui, HI (Oct. 29, 2001) pp. 1017–1022.Google Scholar
21.Hashim, M. S. M. and Lu, T. F., “Multiple Waypoints Trajectory Planning with Specific Position, Orientation, Velocity and Time Using Geometric Approach for a Car-Like Robot,” Proceedings of Australasian Conference on Robotics and Automation (ACRA), Australia (Dec. 2–4, 2009) pp. 1–7.Google Scholar
22.Yuan, Q., Lee, J. Y. and Han, C., “Sensor-based Navigation Algorithm for Car-like Robot to Generate Completed GVG,” Proceedings of International Conference on Control, Automation and Systems, Gyeonggi-do, South Korea (Oct. 26–29, 2011) pp. 1442–1447.Google Scholar
23.Oriolo, G., Vendittelli, M., Freda, L. and Troso, G., “The SRT Method: Randomized Strategies for Exploration,” Proceedings of the IEEE International Conference on Robotics and Automation, New Orleans, LA (Apr. 26, 2004) pp. 4688–4694.Google Scholar
24.Ghita, N., Kloetzer, M. and Pastravanu, O., “Probabilistic Car-Like Robot Path Planning from Temporal Logic Specifications,” Proceedings of International Conference on System Theory, Control, and Computing (ICSTCC), Sinaia, Romania (Oct. 14–16, 2011) pp. 1–6.Google Scholar
25.Grady, D. K., Moll, M., Hegde, C., Sankaranarayanan, A. C., Baraniuk, R. G. and Kavraki, L. E., “Multi-Objective Sensor-Based Replanning for a Car-Like Robot,” In: Proceedings of IEEE International Symposium on Safety, Security, and Rescue Robotics (SSRR), College Station, TX (Nov. 5–8, 2012) pp. 1–6.CrossRefGoogle Scholar
26.Kim, D. H., Lee, J. Y. and Han, C. S., “Sensor-based motion planning for a car-like robot based on bug family algorithms,” World Acad. Sci. Eng. Technol. 71, 1588–1594 (2012).Google Scholar
27.Lumelsky, V. J. and Stepanov, A., “Path planning strategies for point automaton moving amidst unknown obstacles of arbitrary shape,” Algorithmica 2, 403–430 (1987).Google Scholar
28.Choset, H., Lynch, K. M., Hutchinson, S., Kantor, G., Burgard, W., Kavraki, L. E. and Thrun, S., Principles of Robot Motion: Theory, Algorithms, and Implementations (MIT Press, Cambridge, MA, 2005) pp. 401–462.Google Scholar
29.Laumond, J. P., “Guidelines in Nonholonomic Motion Planning for Mobile Robots,” In: Robot Motion Planning and Control (Laumond, J. P., ed.) (Springer, 1998) pp. 1–53.Google Scholar
30.LaValle, S. M., “Differential Models,” In: Planning Algorithms (Cambridge University Press, Cambridge, UK, 2006) pp. 711–782.Google Scholar
31.Podsedkowski, L., “Path Planner for Nonholonomic Mobile Robot with Fast Replanning Procedure,” Proceedings of IEEE International Conference on Robotics and Automation, Leuven, Belgium (May 16–20, 1998) pp. 3588–3593.Google Scholar
32.Yang, S. X. and Meng, M., “Real-time collision-free motion planning of a mobile robot using a neural dynamics-based approach,” IEEE Trans. Neural Netw. 14, 1541–1552 (2003).Google Scholar
33.Huang, Y. and Gupta, K., “RRT-SLAM for Motion Planning with Motion and Map Uncertainty for Robot Exploration,” Proceedings of the IEEE International Conference Intelligent Robots and System, Nice, France (Sep. 22–26, 2008) pp. 1077–1082.Google Scholar
34.Stentz, A. “The Focused D* Algorithm for Real-Time Replanning,” In: Proceedings of the International Joint Conference on Artificial Intelligence (Morgan Kaufmann, San Francisco, CA, 1995) pp. 1652–1659.Google Scholar
35.Koenig, S. and Likhachev, M. “D* Lite,” Proceedings of the AAAI Conference of Artificial Intelligence (AAAI), Edmonton, Alberta (Jul. 28, 2002).Google Scholar
36.Likhachev, M., Ferguson, D., Gordon, G., Stentz, A. and Thrun, S., “Anytime Dynamic A*: An Anytime, Replanning Algorithm,” Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS), Monterey, CA (Jun. 5, 2005) pp. 262–271.Google Scholar
37.Ferguson, D. and Stentz, A., “The Delayed D* Algorithm for Efficient Path Replanning,” Proceedings of the IEEE International Conference on Robotics and Automation, Barcelona, Spain (Apr. 18–22, 2005) pp. 2045–2050.Google Scholar
38.Khatib, O., “Real-time obstacle avoidance for manipulators and mobile robots,” Int. J. Robot. Res. 5, 90–98 (1986).Google Scholar
39.Podsedkowski, L., Nowakowski, J., Idzikowski, M. and Vizvary, I. “A new solution for path planning in partially known or unknown environment for nonholonomic mobile robots,” Robot. Auton. Syst. 34, 145–152 (2001).Google Scholar
40.Lee, H. C., Yaniss, T. and Lee, B. H.,. “Grafting: A path replanning technique for rapidly-exploring random trees in dynamic environments,” Adv. Robot. 26, 2145–2168 (2012).CrossRefGoogle Scholar
41.Bekris, K. E., Grady, D. K., Moll, M. and Kavraki, L. E., “Safe distributed motion coordination for second-order systems with different planning cycles,” Int. J. Robot. Res. 31 (2), 129–149 (2012).Google Scholar
42.Dubins, L. E., “On curves of minimal length with a constraint on average curvature and with prescribed initial and terminal positions and tangents,” Am. J. Math. 79, 497–516 (1957).Google Scholar
43.Giordano, P. R., Vendittelli, M., Laumond, J. P. and Souères, P., “Nonholonomic distance to polygonal obstacles for a car-like robot of polygonal shape,” IEEE Trans. Robot. 22, 1040–1047 (2006).Google Scholar
44.Vendittelli, M., Laumond, J. P. and Nissoux, C., “Obstacle distance for car-like robots,” Trans. Rob. Autom. 15, 678–691 (1999).Google Scholar