A Reasonable Path Planning via Path Energy Minimization
Masashi Yokozuka and Osamu Matsumoto
Intelligent Systems Research Institute, National Institute of Advanced Industrial Science and Technology (AIST), 1-1-1 Umezono, Tsukuba, Ibaraki 305-8568, Japan
This paper presents a path planning method by path energy minimizing that enables mobile robots to move smoothly in the real world with optimizing path shape for shortest distance or minimum curvature. It also enables robots to travel safely toward a destination because pedestrian motion prediction is embedded in path planning. This path planning method is based on problems experienced in a robot competition called Tsukuba Challenge. The problems involved nonsmooth motion arising from finite path patterns in A* algorithm, stuck motion arising from frequently path switching, and near misses arising from nonpredictive planning. Our path planning method minimizes pathshape energy defined as the connection between path points. Minimizing energy provides smooth paths and avoids path switching. We propose a path planning method with prediction of dynamic obstacle motion embedded to avoid near misses. Experimental results showed improvements in solving these problems.
-  P. E. Hart et al., “A Formal Basis for the Heuristic Determination of Minimum Cost Paths,” IEEE Trans. on Systems Science and Cybernetics, Vol.4, pp. 100-107, 1968.
-  A. Stentz, “Optimal and Efficient Path Planning for Partially-Known Environments,” Proc. of the Int. Conf. on Robotics and Automation, pp. 3310-3317, 1994.
-  S. Koenig et al., “Fast Replanning for Navigation in Unknown Terrain,” Trans. on Robotics, Vol.21, Issue 3, pp. 354-363, 2005.
-  L. E. Kavraki et al., “Probabilistic roadmaps for path planning in high-dimensional configuration spaces,” IEEE Trans. on Robotics and Automation, Vol.12, Issue 4, pp. 566-580, 1996.
-  S. M. Lavalle, “Rapidly-exploring random trees: A new tool for path planning,” Technical Report, Computer Science Department, Iowa State University, 1998.
-  S. Karaman et al., “Incremental sampling-based algorithms for optimal motion planning,” in Robotics, Science and Systems (RSS), 2010.
-  S. Choudhury et al., “RRT*-AR: Sampling-Based Alternate Routes Planning with Applications to Autonomous Emergency Landing of a Helicopter,” Proc. of Int. Conf. on Robotics and Automation, 2013.
-  S. Quinlan et al., “Elastic Bands: Connecting Path Planning and Control,” Proc. of Int. Conf. on Robotics and Automation, pp. 802-807, 1993.
-  T.M. Howard et al., “Optimal rough terrain trajectory generation for wheeled mobile robots,” The Int. J. of Robotics Research, Vol.26, No.2, pp. 141-166, 2007.
-  D. Ferguson et al., “Motion planning in urban environments: Part 1,” Proc. of IEEE/RSJ Int. Conf. on Intelligent Robots and Systems, pp. 1063-1069, 2008.
-  S. Gulati et al., “A Framework for Planning Comfortable and Customizable Motion of an Assistive Mobile Robot,” Proc. of IEEE/RSJ Int. Conf. on Intelligent Robots and Systems, pp. 4253-4260, 2009.
-  C. I. Connolly et al., “Path Planning Using Laplace’s Equation,” Proc. of Int. Conf. on Robotics and Automation, pp. 2102-2106, 1990.
-  L. Huang, “Velocity Planning for a Mobile Robot to Track aMoving Target – a Potential Field Approach,” Robotics and Autonomous Systems, Vol.57, pp. 55-63, 2009.
-  W. Kumahara et al., “Navigation System for Mobile Robot Based on Local Path Information and Pedestrian Flow in Dynamic Unknown Environment,” Robotics Symposia, 2013 (in Japanese).
-  M. Seder et al., “Dynamic window based approach to mobile robot motion control in the presence of moving obstacles,” Proc. of Int. Conf. on Robotics and Automation, 2007.
-  M. Montemerlo et al., “Dynamic Environment,” in Section 5 of “FastSLAM: Scalable Method for the Simultaneous Localization and Mapping Problem in Robotics,” Springer tracts in advanced robotics, Vol.27, 2006.
-  R. Kurazume et al., “Target tracking using SIR and MCMC particle filters by multiple cameras and laser range finders,” Proc. of IEEE/RSJ Int. Conf. on Intelligent Robots and Systems, pp. 3838-3844, 2008.
-  A. Fod et al., “Laser-Based People Tracking,” Proc. of Int. Conf. on Robotics and Automation, pp. 3024-3029, 2002.
-  D. Ferguson et al., “Detection, Prediction, and Avoidance of Dynamic Obstacles in Urban Environments,” Proc. of the 2008 IEEE Intelligent Vehicles Symposium, pp. 1149-1154, June 2008.
-  S. J. Osher et al. “Level Set Methods and Dynamic Implicit Surfaces,” Springer, 2002.
-  C. M. Bishop, “Regularization in Neural Network,” in Section 5.5 of “Pattern Recognition and Machine Learning,” Springer, 2006.
-  T. Tsubouchi et al., “Planning and navigation by a mobile robot in the presence of multiple moving obstacles and their velocities,” J. of the Robotics Society of Japan, Vol.12, No.7, pp. 1029-1037, 1994 (in Japanese).
-  M. Yokozuka et al., “Sub-Map Dividing and Realignment Fast-SLAM by Blocking Gibbs MCEM for Large 3-D Grid Mapping,” Advanced Robotics, Vol.26, No.14, 2012.
-  M. Yokozuka et al., “Robotic Wheelchair with Autonomous Traveling Capability for Transportation Assistance in an Urban Environment,” Proc. of IEEE/RSJ Int. Conf. on Intelligent Robots and Systems, pp. 3838-3844, 2012.
- [a] Willow Garage, Path Optimization by Elastic Band, 2010.
[Accessed December 3, 2013]
Supporting Online Materials: