Abstract
In this paper we propose a machine learning technique for real-time robot path planning for an autonomous robot in a planar environment with obstacles where the robot possess no a priori map of its environment. Our main insight in this paper is that a robot’s path planning times can be significantly reduced if it can refer to previous maneuvers it used to avoid obstacles during earlier missions, and adapt that information to avoid obstacles during its current navigation. We propose an online path planning algorithm called LearnerRRT that utilizes a pattern matching technique called Sample Consensus Initial Alignment (SAC-IA) in combination with an experience-based learning technique to adapt obstacle boundary patterns encountered in previous environments to the current scenario followed by corresponding adaptations in the obstacle-avoidance paths. Our proposed algorithm LearnerRRT works as a learning-based reactive path planning technique which enables robots to improve their overall path planning performance by locally improving maneuvers around commonly encountered obstacle patterns by accessing previously accumulated environmental information. We have conducted several experiments in simulations and hardware to verify the performance of the LearnerRRT algorithm and compared it with a state-of-the-art sampling-based planner. LearnerRRT on average takes approximately 10% of the planning time and 14% of the total time taken by the sampling-based planner to solve the same navigation task based on simulation results and takes only 33% of the planning time, 46% of total time and 95% of total distance compared to the sampling-based planner based on our hardware results.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Alt, H., Buchin, M.: Can we compute the similarity between surfaces? Discret Comput Geom 43(1), 78–99 (2010)
Amato, N.M., Bayazit, O.B., Dale, L.K.: Obprm: An obstacle-based prm for 3d workspaces. In: 3rd International Workshop on Algorithmic Foundations of Robotics (WAFR), pp. 155–168 (1998)
Arslan, O., Tsiotras, P.: Use of relaxation methods in sampling-based algorithms for optimal motion planning. In: IEEE International Conference on Robotics and Automation (ICRA), p 2013. IEEE (2013)
Berenson, D., Abbeel, P.: A robot path planning framework that learns from experience. In: IEEE International Conference on Robotics and Automation (ICRA) A robot path planning, p 2012. IEEE (2012)
Bohlin, R., Kavraki, L.E.: Path planning using lazy prm. In: 2000. Proceedings. ICRA’00. IEEE International Conference on Robotics and Automation, vol. 1, pp. 521–528. IEEE (2000)
Bruce, J., Veloso, M.: Real-time randomized path planning for robot navigation, vol. 3, pp. 2383–2388. IEEE (2002)
Choset, H., Burgard, W., Hutchinson, S., Kantor, G., Kavraki, L.E., Lynch, K., Thrun, S.: Principles of robot motion: theory, algorithms, and implementation. MIT Press, Cambridge (2005)
Coleman, D., Sucan, I.A., Moll, M., Okada, K., Correll, N.: Experience-based planning with sparse roadmap spanners. arXiv:1410.1950 (2014)
Cui, R., Gao, B., Guo, J.: Pareto-optimal coordination of multiple robots with safety guarantees. Auton. Robots. 32(3), 189–205 (2012)
Cui, R., Li, Y., Yan, W.: Mutual information-based multi-auv path planning for scalar field sampling using multidimensional RRT. IEEE Trans. Syst. Man Cybern. Syst. 46(7), 993–1004 (2016)
Da Silva, B.N., Mackworth, A.: Using spatial hints to improve policy reuse in a reinforcement learning agent. In: Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems: Volume 1, pp. 317–324. International Foundation for Autonomous Agents and Multiagent Systems (2010)
D’Andrea, R.: Guest editorial: A revolution in the warehouse: A retrospective on kiva systems and the grand challenges ahead. IEEE Trans. Autom. Sci. Eng. 9(4), 638–639 (Oct 2012)
Elbanhawi, M., Simic, M.: Sampling-based robot motion planning: A review. IEEE Access 2, 56–77 (2014)
Elgamal, T., Hefeeda, M.: Analysis of pca algorithms in distributed environments. arXiv:1503.05214 (2015)
Ferguson, D., Kalra, N., Stentz, A.: Replanning with rrts. In: Proceedings 2006 IEEE International Conference on Robotics and Automation, 2006. ICRA 2006, pp. 1243–1248. IEEE (2006)
Fernández, F., Veloso, M.: Probabilistic policy reuse in a reinforcement learning agent. In: Proceedings of the fifth international joint conference on Autonomous Agents and Multiagent Systems, pp. 720–727. ACM (2006)
Gammell, J., Srinivasa, S., Barfoot, T.: Informed rrt*: Optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic. In: 2014 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2014), pp. 2997–3004 (2014)
Gayle, R., Klingler, K.R., Xavier, P.G.: Lazy reconfiguration forest (lrf)-an approach for motion planning with multiple tasks in dynamic environments. In: Proceedings 2007 IEEE International Conference on Robotics and Automation, pp. 1316–1323. IEEE (2007)
Hwang, V., Phillips, M., Srinivasa, S., Likhachev, M.: Lazy validation of experience graphs. In: IEEE International Conference on Robotics and Automation (ICRA), pp. 912–919. IEEE (2015)
Karaman, S., Frazzoli, E.: Sampling-based algorithms for optimal motion planning. Int. J. Robot. Res. 30 (7), 846–894 (2011)
Kavraki, L.E., Latombe, J.-C.: Probabilistic roadmaps for robot path planning (1998)
Kuffner, J.J., LaValle, S.M.: Rrt-connect: An efficient approach to single-query path planning. In: 2000. Proceedings. ICRA’00. IEEE International Conference on Robotics and Automation, vol. 2, pp. 995–1001. IEEE (2000)
LaValle, S.M.: Rapidly-exploring random trees: A new tool for path planning (1998)
Lien, J.-M., Lu, Y.: Planning motion in environments with similar obstacles. In: Robotics: Science and Systems. Citeseer (2009)
Menon, A., Cohen, B., Likhachev, M.: Motion planning for smooth pickup of moving objects. In: Robotics and Automation (ICRA) IEEE International Conference on, pp. 453–460. IEEE (2014)
Otte, M., Frazzoli, E.: Rrtx: Real-time motion planning/replanning for environments with unpredictable obstacles. In: Algorithmic Foundations of Robotics XI, pp. 461–478. Springer (2015)
Paden, B., Ċáp, M., Yong, S.Z., Yershov, D., Frazzoli, E.: A survey of motion planning and control techniques for self-driving urban vehicles. IEEE Trans. Intell. Veh. 1(1), 33–55 (2016)
Phillips, M., Cohen, B.J., Chitta, S., Likhachev, M.: E-graphs: Bootstrapping planning with experience graphs. In: Robotics: Science and Systems (2012)
Phillips, M., Likhachev, M.: Speeding up heuristic computation in planning with experience graphs. In: IEEE International Conference on Robotics and Automation (ICRA), p 2015. IEEE (2015)
Rusu, R., Blodow, N., Beetz, M.: Fast point feature histograms (fpfh) for 3d registration. In: 2009. ICRA ’09. IEEE International Conference on Robotics and Automation, pp. 3212–3217 (2009)
Rusu, R.B., Bradski, G.R., Thibaux, R., Hsu, J.M.: Fast 3d recognition and pose using the viewpoint feature histogram. In: 2010 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 2155–2162, Taipei (2010)
Saha, O., Dasgupta, P.: Fast path planning using experience learning from obstacle patterns. AAAI Spring Symposium Series. https://www.aaai.org/ocs/index.php/SSS/SSS16/paper/view/12725 (2016)
Saha, O., Dasgupta, P.: Real-time robot path planning using experience learning from common obstacle patterns. In: Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems, pp. 1339–1340. International Foundation for Autonomous Agents and Multiagent Systems (2016)
Sherwood, R., Mishkin, A., Chien, S., Estlin, T., Backes, P., Cooper, B., Rabideau, G., Engelhardt, B.: An integrated planning and scheduling prototype for automated mars rover command generation. In: Sixth European Conference on Planning (2014)
Shi, K., Denny, J., Amato, N.M.: Spark prm: Using rrts within prms to efficiently explore narrow passages. In: 2014 IEEE International Conference on Robotics and Automation (ICRA), pp. 4659–4666. IEEE (2014)
Song, B.D., Kim, J., Morrison, J.R.: Rolling horizon path planning of an autonomous system of uavs for persistent cooperative service: MILP formulation and efficient heuristics. J. Intell. Robot. Syst. 84(1-4), 241–258 (2016)
Stolle, M., Atkeson, C.G.: Policies based on trajectory libraries. In: Proceedings 2006 IEEE International Conference on Robotics and Automation, 2006. ICRA 2006, pp. 3344–3349. IEEE (2006)
Stolle, M., Tappeiner, H., Chestnutt, J., Atkeson, C.G.: Transfer of policies based on trajectory libraries. In: IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 2981–2986. IEEE (2007)
Strandberg, M.: Augmenting rrt-planners with local trees. In: 2004. Proceedings. ICRA’04. 2004 IEEE International Conference on Robotics and Automation, vol. 4, pp. 3258–3262. IEEE (2004)
Talvitie, E., Singh, S.P.: An experts algorithm for transfer learning. In: IJCAI, pp. 1065–1070 (2007)
Taylor, M.E., Kuhlmann, G., Stone, P.: Accelerating search with transferred heuristics. In: ICAPS Workshop on AI Planning and Learning (2007)
Taylor, M.E., Kuhlmann, G., Stone, P.: Autonomous transfer for reinforcement learning. In: Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems-Volume 1, pp. 283–290. International Foundation for Autonomous Agents and Multiagent Systems (2008)
Taylor, M.E., Stone, P.: Transfer learning for reinforcement learning domains A survey. J. Mach. Learn. Res. 10, 1633–1685 (2009)
Torrey, L., Shavlik, J.: Policy transfer via markov logic networks. In: Inductive Logic Programming, pp. 234–248. Springer (2010)
Torrey, L., Shavlik, J., Walker, T., Maclin, R.: Skill acquisition via transfer learning and advice taking. In: Machine Learning: ECML 2006, pp. 425–436. Springer (2006)
Tsardoulias, E., Iliakopoulou, A., Kargakos, A., Petrou, L.: A review of global path planning methods for occupancy grid maps regardless of obstacle density. J. Intell. Robot. Syst. 84(1-4), 829–858 (2016)
Yeh, H.-Y., Thomas, S., Eppstein, D., Amato, N.M.: Uobprm: A uniformly distributed obstacle-based prm. In: 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 2655–2662. IEEE (2012)
Zucker, M., Kuffner, J., Branicky, M.: Multipartite rrts for rapid replanning in dynamic environments. In: Proceedings IEEE International Conference on Robotics and Automation, p 2007. IEEE (2007)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Saha, O., Dasgupta, P. Experience Learning From Basic Patterns for Efficient Robot Navigation in Indoor Environments. J Intell Robot Syst 92, 545–564 (2018). https://doi.org/10.1007/s10846-017-0739-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10846-017-0739-7