Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-24T17:10:00.216Z Has data issue: false hasContentIssue false
  • English
  • Français

Real-time obstacle avoidance for multiple mobile robots

Published online by Cambridge University Press:  01 March 2009

Farbod Fahimi ,
C. Nataraj  and
Hashem Ashrafiuon
Farbod Fahimi*
Affiliation:
Mechanical Engineering Department, University of Alberta, Edmonton, AB T6G 2G8, Canada
C. Nataraj
Affiliation:
Center for Nonlinear Dynamics & Control (CENDAC), Villanova University, Villanova, PA 19085, US
Hashem Ashrafiuon
Affiliation:
Center for Nonlinear Dynamics & Control (CENDAC), Villanova University, Villanova, PA 19085, US
*
*Corresponding author. E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Summary

An efficient, simple, and practical real time path planning method for multiple mobile robots in dynamic environments is introduced. Harmonic potential functions are utilized along with the panel method known in fluid mechanics. First, a complement to the traditional panel method is introduced to generate a more effective harmonic potential field for obstacle avoidance in dynamically changing environments. Second, a group of mobile robots working in an environment containing stationary and moving obstacles is considered. Each robot is assigned to move from its current position to a goal position. The group is not forced to maintain a formation during the motion. Every robot considers the other robots of the group as moving obstacles and hence the physical dimensions of the robots are also taken into account. The path of each robot is planned based on the changing position of the other robots and the position of stationary and moving obstacles. Finally, the effectiveness of the scheme is shown by modeling an arbitrary number of mobile robots and the theory is validated by several computer simulations and hardware experiments.

Keywords

Trajectory planningmultiple robotsobstacle avoidancepotential field methodharmonic potentialspanel method
Type
Article
Information
Robotica , Volume 27 , Issue 2 , March 2009 , pp. 189 - 198
Copyright
Copyright © Cambridge University Press 2008

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.Canny, J., The Complexity of Robot Motion Planning (The MIT Press, Cambridge, MA, 1987).Google Scholar
2.Zexiang, L. and Canny, J. F., Nonholonomic Motion Planning (Kluwer Academic Publishers, Norwell, MA, 1993).Google Scholar
3.Latombe, J., Robot Motion Planning (Kluwer Academic Publishers, Boston, MA, 1991).CrossRefGoogle Scholar
4.Schwartz, J. T. and Sharir, M., “On the piano movers' problem: III. Coordinating the motion of several independent bodies amidst polygon barriers,” Int. J. Robot. Res. 2 (3), 46–75 (1983).CrossRefGoogle Scholar
5.Hopcrof, J. E., Schwartz, J. T. and Sharir, M., “On the complexity of motion planning for multiple independent objects; pspace-hardness of the warehouseman's problem,” Int. J. Robot. Res. 3 (4), 76–88 (1984).CrossRefGoogle Scholar
6.LaValle, S. M. and Hutchinson, S. A., “Optimal motion planning for multiple robots having independent goals,” IEEE Trans. Robot. Autom. 14 (6), 912–925 (1998).CrossRefGoogle Scholar
7.Gulec, N. and Unel, M., “A Novel Algorithm for the Coordination of Multiple Mobile Robots,” Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 3733 NCS, (2005) pp. 422–431.Google Scholar
8.van den Berg, J. P. and Overmars, M. H., “Roadmap-based motion planning in dynamic environments,” IEEE Trans. Robot. 21 (5), 885–897 (2005).CrossRefGoogle Scholar
9.Lee, S. and Adams, T. M., “Spatial model for path planning of multiple mobile construction robots,” Comput.-Aided Civ. Infrastruct. Eng. 19 (4), 231–245 (2004).CrossRefGoogle Scholar
10.Desai, J. P., Ostrowski, P. J. and Kumar, V., “Modeling and control of formations of nonholonomic mobile robots,” IEEE Trans. Robot. Autom. 6, 905–908 (2001).CrossRefGoogle Scholar
11.Hirota, K., Kuwabara, T., Kenichi, I., Miyanohara, A., Ohdachi, H., Ohsawa, T., Takeuchi, W., Yubazaki, N. and Ohtani, M., “Robots Moving in Formation by IEEE International Conference on Fuzzy Systems, vol. 1, Yokohama, Japan Using Neural Network and Radial Basis Functions,” Proceedings of the (1995) pp. 91–94.Google Scholar
12.Jing, X.-J. and Wang, Y.-C., “Control of Behavior Dynamics for Motion Planning of Mobile Robots in Uncertain Environments,” Proceedings of the 2005 IEEE International Conference on Mechatronics, ICM '05, vol. 2005, Taipei, Taiwan (2005) pp. 364–369.Google Scholar
13.Liang, Y. and Lee, H.-H., “Avoidance of Multiple Obstacles for a Mobile Robot with Nonholonomic Constraints,” American Society of Mechanical Engineers, Dynamic Systems and Control Division (Publication) DSC, vol. 74 DSC, no. 2 PART B, Orlando, FL, United States (2005) pp. 1657–1663.Google Scholar
14.Lawton, R. J., Young, B. J. and Beard, R. W., “A Decentralized Approach to Elementary Formation Maneuvers,” Proceedings of the IEEE International Conference on Robotics and Automation, vol. 1, San Francisco, CA, USA (2000) pp. 2728–2743.Google Scholar
15.Yamaguchi, H., “Cooperative hunting behavior by mobile robot troops,” Int. J. Robot. Res. 9, 931–940 (1999).CrossRefGoogle Scholar
16.Shao, J., Xie, G., Yu, J. and Wang, L., “Leader-Following Formation Control of Multiple Mobile Robots,” Proceedings of the 20th IEEE International Symposium on Intelligent Control, ISIC '05 and the 13th Mediterranean Conference on Control and Automation, MED '05, vol. 2005, (Limassol, Cyprus), pp. 808–813, 2005.Google Scholar
17.Balch, T. and Arkin, R. C., “Behavior-based formation control for multi-robot teams,” IEEE Trans. Robot. Autom. 6, 926–939 (1998).CrossRefGoogle Scholar
18.Cao, Z., Xie, L., Zhang, B., Wang, S. and Tan, M., “Formation Constrained Multi-robot System in Unknown Environments,” Proceedings of IEEE International Conference on Robotics and Automation, vol. 1, Taipei, Taiwan (2003) pp. 735–740.Google Scholar
19.Marchese, F. M. and Negro, M. D., “Path-Planning for Multiple Generic-Shaped Mobile Robots with MCA,” Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 3993 NCS–III, (2006) pp. 264–271.Google Scholar
20.Warren, C., “Multiple Robot Path Coordination Using Artificial Potential Fields,” Proceedings of the IEEE International Conference on Robotics and Automation, vol. 1, Cincinnati, OH, USA (1990) pp. 500–505.CrossRefGoogle Scholar
21.Sheu, C. and Young, K., “Heuristic approach to robot path planning based on task requirements using a genetic algorithm,” J. Intell. Robot. Syst.: Theory and Appl. 1, 65–88 (1996).CrossRefGoogle Scholar
22.Yun, X. and Tan, K., “Wall-Following Method for Escaping Local Minima in Potential Field Based Motion Planning,” Proceeding of the 8th International Conference on Advanced Robotics, ICAR'97, Monterey, CA, USA (1997) pp. 421–426.Google Scholar
23.Cosio, F. A. and Castaneda, M. P., “Autonomous robot navigation using adaptive potential fields,” Math. Comput. Modelling 40 (9–10), 1141–1156 (2004).CrossRefGoogle Scholar
24.Ge, S. S. and Cui, Y. J., “Dynamic motion planning for mobile robot using potential field method,” Auton. Robot. 1, 207–222 (2002).CrossRefGoogle Scholar
25.Kim, D. H., Wang, H. O., Ye, G. and Shin, S., “Decentralized Control of Autonomous Swarm Systems Using Artificial Potential Functions: Analytical Design Guidelines,” Proceedings of the IEEE Conference on Decision and Control, vol. 1, Nassau, Bahamas (2004) pp. 159–164.Google Scholar
26.Chester, C. R., Techniques in Partial Differential Equations (McGraw-Hill, New York, 1971).Google Scholar
27.Kim, J. and Khosla, P. K., “Real-time obstacle avoidance using harmonic potential functions,” IEEE Trans. Robot. Autom. 3, 338–349 (1992).CrossRefGoogle Scholar
28.Connolly, C. I., Burnd, J. B. and Weiss, R., “Path Planning Using Laplace's Equation,” Proceedings of the IEEE International Conference on Robotics and Automation, Cincinnati, OH, USA (1990) pp. 2102–2106.Google Scholar
29.Guldner, J., Utkin, V. I. and Bauer, R., “A three-layered hierarchical path control system for mobile robots: Algorithms and experiments,” Robot. Autom. Syst. 14, 133–147 (1995).CrossRefGoogle Scholar
30.Arai, T. and Ota, J., “Motion planning of multiple mobile robots using virtual impedance,” J. Robot. Mechatronics 8 (1), 67–74 (1996).CrossRefGoogle Scholar
31.Akishita, S., Kawamura, S., and Hisanobu, T., “Velocity potential approach to path planning for avoiding moving obstacles,” Adv. Robot. 7 (5), 463–478 (1996).CrossRefGoogle Scholar
32.Sugiyama, S. and Akishita, S., “Path Planning for Mobile Robot at Crossroads by Using Hydrodynamic Potential,” Proceedings of 1998 Japan–USA Symposium on Flexible Automation, Ohstu, Japan (1998) pp. 595–602.Google Scholar
33.Kuethe, A. M. and Chow, C. Y., Foundation of Aerodynamics: Bases of Aerodynamic Design, 4th ed. (Wiley, New York, 1986).Google Scholar
34.Fahimi, F., Ashrafiuon, H. and Nataraj, C., “Obstacle avoidance for spatial hyper-redundant manipulators using harmonic potential functions and the mode shape technique,” J. Robot. Syst. 20 (1), 23–33 (2003).CrossRefGoogle Scholar
35.Zhang, Y. and Valavanis, K. P., “Sensor-based 2-D potential panel method for robot motion planning,” Robotica 1, 81–89 (1996).CrossRefGoogle Scholar
36.Zhang, Y. and Valavanis, K. P., “A 3-D panel method for robot motion planning,” Robotica 1, 421–434 (1997).CrossRefGoogle Scholar
37.Luca, A. D., Oriolo, G. and Samson, C., Feedback Control of a Nonholonomic Car-Like Robot, Robot Motion Planning and Control (Springer-Verlag, Berlin, Germany, 1998).Google Scholar