Open Source Integrated Planner for Autonomous Navigation in Highly Dynamic Environments
Hatem Darweesh*, Eijiro Takeuchi*, Kazuya Takeda*, Yoshiki Ninomiya*, Adi Sujiwo*, Luis Yoichi Morales*, Naoki Akai*, Tetsuo Tomizawa**, and Shinpei Kato***
Furo-cho, Chikusa-ku, Nagoya, Aichi 464-8601, Japan
**National Defense Academy of Japan
1-10-20 Hashirimizu, Yokosuka, Kanagawa 239-8686, Japan
***The University of Tokyo
7-3-1 Hongo, Bunkyo-ku, Tokyo 113-8654, Japan
Planning is one of the cornerstones of autonomous robot navigation. In this paper we introduce an open source planner called “OpenPlanner” for mobile robot navigation, composed of a global path planner, a behavior state generator and a local planner. OpenPlanner requires a map and a goal position to compute a global path and execute it while avoiding obstacles. It can also trigger behaviors, such as stopping at traffic lights. The global planner generates smooth, global paths to be used as a reference, after considering traffic costs annotated in the map. The local planner generates smooth, obstacle-free local trajectories which are used by a trajectory tracker to achieve low level control. The behavior state generator handles situations such as path tracking, object following, obstacle avoidance, emergency stopping, stopping at stop signs and traffic light negotiation. OpenPlanner is evaluated in simulation and field experimentation using a non-holonomic Ackerman steering-based mobile robot. Results from simulation and field experimentation indicate that OpenPlanner can generate global and local paths dynamically, navigate smoothly through a highly dynamic environments and operate reliably in real time. OpenPlanner has been implemented in the Autoware open source autonomous driving framework’s Robot Operating System (ROS).
-  W. Burgard, A. Cremers, D. Fox, D. Hanel, G. Lakemeyer, D. Schulz, W. Steiner, and S. Thrun, “The interactive museum tourguide robot,” Proc. of the Fifteenth National Conf. on Artificial Intelligence (AAAI-98), 1998.
-  Y. Morales, E. Takeuchi, A. Carballo, A. Aburadani, and T. Tsubouchi, “Autonomous robot navigation in outdoor cluttered pedestrian walkways,” J. of Field Robotics, Vol.26, No.8, pp. 609-635, 2009.
-  R. Kümmerle, M. Ruhnke, B. Steder, C. Stachniss, and W. Burgard, “Autonomous robot navigation in highly populated pedestrian zones,” J. of Field Robotics, 2014.
-  S. Thrun, M. Montemerlo, H. Dahlkamp, D. Stavens, A. Aron, J. Diebel, P. Fong, J. Gale, M. Halpenny, G. Hoffmann, K. Lau, C. Oakley, M. Palatucci, V. Pratt, P. Stang, S. Strohband, C. Dupont, L.-E. Jendrossek, C. Koelen, C. Markey, C. Rummel, J. van Niekerk, E. Jensen, P. Alessandrini, G. Bradski, B. Davies, S. Ettinger, A. Kaehler, A. Nefian, and P. Mahoney, “Stanley: The robot that won the DARPA grand challenge,” J. of Field Robotics, Vol.23, No.1, pp. 661-692, June 2006.
-  C. Urmson, J. Anhalt, H. Bae, J. D. Bagnell, C. Baker, R. E. Bittner, T. Brown, M. N. Clark, M. Darms, D. Demitrish, J. Dolan, D. Duggins, D. Ferguson, T. Galatali, C. M. Geyer, M. Gittleman, S. Harbaugh, M. Hebert, T. Howard, S. Kolski, M. Likhachev, B. Litkouhi, A. Kelly, M. McNaughton, N. Miller, J. Nickolaou, K. Peterson, B. Pilnick, R. Rajkumar, P. Rybski, V. Sadekar, B. Salesky, Y.-W. Seo, S. Singh, J. M. Snider, J. C. Struble, A. T. Stentz, M. Taylor, W. R. L. Whittaker, Z. Wolkowicki, W. Zhang, and J. Ziglar, “Autonomous driving in urban environments: Boss and the urban challenge,” Special Issue on the 2007 DARPA Urban Challenge, Part I, J. of Field Robotics, Vol.25, No.1, pp. 425-466, June 2008.
-  S. Kato, E. Takeuchi, Y. Ishiguro, Y. Ninomiya, K. Takeda, and T. Hamada, “An open approach to autonomous vehicles,” IEEE Micro, Vol.35, No.6, pp. 60-68, Nov. 2015.
-  M. Quigley, K. Conley, B. Gerkey, J. Faust, T. Foote, J. Leibs, R. Wheeler, and A. Y. Ng, “ROS: an open-source Robot Operating System,” ICRA workshop on open source software, Vol.3, Issue 3.2, Dec. 2009.
-  P. Weber and M. (M.) Haklay, “OpenStreetMap: User Generated Street Maps,” IEEE Pervasive Computing, Vol.7, pp. 12-18, October-December 2008. doi: 10.1109/MPRV.2008.80.
-  S. LaValle, “Motion planning: The essentials,” IEEE Robotics Automation Magazine, Vol.18, No.1, pp. 79-89, 2011.
-  S. LaValle, “Motion planning: Wild frontiers,” IEEE Robotics Automation Magazine, Vol.18, No.2, pp. 108-118, 2011.
-  E. W. Dijkstra, “A note on two problems in connexion with graphs,” Numerische Mathematik, Vol.1, pp. 269-271, 1959.
-  P. E. Hart, N. J. Nilsson, and B. Raphael, “A formal basis for the heuristic determination of minimum cost paths,” IEEE Trans. on Systems, Science, and Cybernetics, Vol.SSC-4, No.2, pp. 100-107, 1968.
-  M. Likhachev, D. I. Ferguson, G. J. Gordon, A. Stentz, and S. Thrun, “Anytime dynamic A*: An anytime replanning algorithm,” Proc. of the Int. Conf. on Automated Planning and Scheduling 2005 (ICAPS 2005), pp. 262-271, 2005.
-  S. Koenig and M. Likhachev, “D*lite,” Eighteenth National Conf. on Artificial Intelligence, Menlo Park, CA, USA: American Association for Artificial Intelligence, pp. 476-483, 2002.
-  P. Beeson, N. K. Jong, and B. Kuipers, “Towards Autonomous Topological Place Detection Using the Extended Voronoi Graph,” Proc. of the 2005 IEEE Int. Conf. on Robotics and Automation, pp. 4373-4379, April 2005.
-  J. J. Park and B. Kuipers, “A smooth control law for graceful motion of differential wheeled mobile robots in 2D environment,” 2011 IEEE Int. Conf. on Robotics and Automation (ICRA), pp. 4896-4902, May 2011.
-  P. Czerwionka, M. Wang, and F. Wiesel, “Optimized route network graph as map reference for autonomous cars operating on German autobahn,” 2011 5th Int. Conf. on Automation Robotics and Applications (ICARA), pp. 78-83, December 2011.
-  C. Chen, A. Gaschler, M. Rickert, and A Knoll, “Task Planning for Highly Automated Driving,” 2015 IEEE Intelligent Vehicles Symposium (IV2015), 2015.
-  R. Simmons, “The Curvature-Velocity Method for Local Obstacle Avoidance,” Proc. of the IEEE Int. Conf. on Robotics and Automation (ICRA 1996), pp. 3375-3382, 1996.
-  D. Fox, W. Burgard, and S. Thrun, “The dynamic window approach to collision avoidance,” IEEE Robotics and Automation Magazine, Vol.4, No.1, pp. 23-33, 1997.
-  O. Brock and O. Khatib, “High-speed navigation using the global dynamic window approach,” IEEE Int. Conf. on Robotics and Automation, pp. 341-346, 1999.
-  Y. Morales, A. Watanabe, F. Ferreri, J. Even, T. Ikeda, K. Shinozawa, T. Miyashita, and N. Hagita, “Including Human Factors for Planning Comfortable Paths,” 2015 IEEE Int. Conf. on Robotics and Automation (ICRA 2015), pp. 6153-6159, May 2015.
-  X. Li, Z. Sun, A. Kurt, and Q. Zhu, “A Sampling-Based Local Trajectory Planner for Autonomous Driving along a Reference Path,” Proc. of 2014 IEEE Intelligent Vehicles Symposium (IV 2014), 2014.
-  R. Ding and W. Chen, “Moving object tracking in support of unmanned vehicle operation,” 2013 19th Int. Conf. on Automation and Computing (ICAC), pp. 1-6, 2013.
-  I. A. Şucan, M. Moll, and L. E. Kavraki, “The Open Motion Planning Library,” IEEE Robotics and Automation Magazine, Vol.19, No.4, pp. 72-82, December 2012.
-  S. Karaman and E. Frazzoli, “Sampling-based Algorithms for Optimal Motion Planning,” Int. J. of Robotics Research, Vol.30, No.7, 2011.
-  Y. Saad, “Iterative methods for sparse linear systems (2nd ed.),” Chapter 6, SIAM, 2003. ISBN 978-0-89871-534-7.
-  R. C. Coulter, “Implementation of the pure-pursuit path tracking algorithm,” Tech. Rep. CMU-RI-TR-92-01, Robotics Institute, Carnegie Mellon University, Pittsburgh, Pa, USA, 1992.
-  D. Dolgov, S. Thrun, M. Montemerlo, and J. Diebel, “Practical search techniques in path planning for autonomous driving,” Proc. of the First Int. Symposium on Search Techniques in Artificial Intelligence and Robotics (STAIR-08), Chicago, IL, Menlo Park, CA, 2008.
-  S. Muramatsu, T. Tomizawa, S. Kudoh, and T. Suehiro, “Development of Intelligent Mobile Cart in a Crowded Environment – Robust Localization Technique with Unknown Objects,” J. of Robotics and Mechatronics, Vol.26, No.2, pp. 204-213, 2014.
-  H. Bruyninckx, “Open robot control software: The OROCOS project,” Proc. of 2001 IEEE Int. Conf. on Robotics and Automation (ICRA’01), Seoul, Korea, 2001.