Planning the Waypoint - Following Task for a Unicycle - Like Robot in Cluttered Environments

• Autorzy: Gawron T. , Michalek M. M.

Identyfikatory

DOI

10.14313/JAMRIS_1-2015/10

• Języki publikacji: EN

Abstrakty

EN

The paper presents a two-stage, global planning algorithm for the waypoint-following task realized by a unicycle-like robot in a clutiered environment. It assumes motion execution with the VFO (Vector Field Orientation) controller. The planner is a result of a controllerdriven design process and exploits particular properties of the VFO controller. Emphasis has been put on the plan safety in the sense of maximizing the distance from the obstacles. In the first stage of planning, an A*-like pathfinding algorithm is used to find a safe geometric plan (i.e. a polyline) in a two-dimensional occupancy grid. During the second stage, a sequence of waypoint posi tions is selected from the geometric plan and reference orientations at the waypoints are planned. Orienta tion planning exploits properties of the VFO controller used for subsequent motion execution. Proposed twostage algorithm admits changes of robot motion strategy (forward/backward movement) and has lower computational cost than the full configuration space search. Performance of the algorithm can be intuitively tuned with provided design parameters.

Słowa kluczowe

EN

VFO control; waypoint-following; unicyclelike robot; combinatorial search; controller-driven motion planning

• Wydawca: Łukasiewicz Industrial Research Institute for Automation and Measurements PIAP
• Czasopismo: Journal of Automation Mobile Robotics and Intelligent Systems
• Rocznik: 2015
• Tom: Vol. 9, No. 1
• Strony: 77--90
• Opis fizyczny: Bibliogr. 27 poz.., rys.

Twórcy

autor

Gawron T.

• Chair of Control and Systems Engineering, Piotrowo 3A, Poland, Poznań, 60-965, www.tomaszgawron.pl

autor

Michalek M. M.

• Chair of Control and Systems Engineering, Piotrowo 3A, Poland, Poznań, 60-965, www.put.poznan.pl/~maciej.michalek

Bibliografia

• [1] B. Akgun and M. Stilman, “Sampling heuristics for optimal motion planning in high dimensions”. In: 2011 IEEE/RSJ Int. Conf. Intelligent Robots and Systems, San Francisco, CA, USA, 2011, 2640–2645, DOI: 10.1109/IROS.2011.6095077.
• [2] M. Cikes, M. Dakulovic, and I. Petrovic, “The path planning algorithms for a mobile robot based on the occupancy grid map of the environment - A comparative study”. In: Proc. XXIII International Symposium on Information, Communication and Automation Technologies (ICAT), Sarajevo, Bosnia and Herzegovina, 2011, 1–8.
• [3] T. Davies and A. Jnifene, “Multiple waypoint path planning for a mobile robot using genetic algorithms”. In: 2006 IEEE Int. Conf. on Computational Intelligence for Measurement Systems and Applications, La Coruńa, Spain, 2006, 21–26, DOI: 10.1109/CIMSA.2006.250741.
• [4] M. Elbanhawi and M. Simic, “Sampling-based robot motion planning: A review”, IEEE Access, vol. 2, 2014, 56–77.
• [5] D. Ferguson and A. Stentz, “Field D*: An interpolation-based path planner and replanner”. In: Proc. of the Int. Symposium on Robotics Research (ISRR), San Francisco, CA, USA, 2005, 1926–1931.
• [6] T. Gawron and M. Michałek. “Planowanie przejazdu przez zbiór punktów dla zadania zrobotyzowanej inspekcji”. In: K. Tchoń and C. Zieliński, eds., Problemy robotyki, volume 194 of Prace naukowe. Elektronika, 35–44. Ofiicyna Wydawnicza Politechniki Warszawskiej, Warszawa, 2014. in Polish.
• [7] D. Harabor and A. Grastien, “Online graph pruning for pathfiinding on grid maps”. In: 25th Conference on Arti􀏔icial Intelligence (AAAI-11), San Francisco, CA, USA, 2011, 1114–1119.
• [8] D. D. Harabor and A. Grastien, “An optimal anyangle pathfiinding algorithm”. In: 2013 Int. Conf. on Automated Planning and Scheduling, Rome, Italy, 2013, 308–311.
• [9] P. Hart, N. Nilsson, and B. Raphael, “A formal basis for the heuristic determination of minimum cost paths”, IEEE Transactions on Systems Science and Cybernetics, vol. 4, no. 2, 1968, 100–107.
• [10] L. Janson and M. Pavone. “Fast marching trees: a fast marching sampling-based method for optimal motion planning in many dimensions”. 2013 Int. Symp. on Robotics Research, Seoul, Korea, Available online:http://web.stanford.edu/ pavone/papers/Janson.Pavone.ISRR13.pdf, Dec 2013.
• [11] N. Jouandeau and Z. Yan, “Decentralized waypoint-based multi-robot coordination”. In: 2012 IEEE Int. Conf. on Cyber Technology in Automation, Control, and Intelligent Systems (CYBER), Bangkok, Thailand, 2012, 175–178,DDOI: 10.1109/CYBER.2012.6392549.
• [12] R. Junqueira Magalhaes Afonso, R. Kawakami Harrop Galvao, and K. Kienitz, “Waypoint trajectory planning in the presence of obstacles with a tunnel-milp approach”. In: 2013 European Control Conference (ECC), Zurich, Switzerland, 2013, 1390–1397.
• [13] S. Karaman and E. Frazzoli, “Sampling-based algorithms for optimal motion planning”, Int. J. Rob. Res., vol. 30, no. 7, 2011, 846–894.
• [14] R. Knepper and A. Kelly, “High performance state lattice planning using heuristic look-up tables”. In: 2006 IEEE/RSJ Int. Conf. Intelligent Robots and Systems, Beijing, China, 2006, 3375–3380, DOI: 10.1109/IROS.2006.282515.
• [15] J.-C. Latombe, Robot Motion Planning, Kluwer Academic Publishers: Norwell, MA, USA, 1991.
• [16] S. M. Lavalle and J. J. Kuffner, “Rapidly-Exploring Random Trees: Progress and prospects”. In: Algorithmic and Computational Robotics: New Directions, 2000, 293–308.
• [17] S. LaValle, Planning Algorithms, Cambridge University Press, 2006.
• [18] S. LaValle and M. Branicky. “On the relationship between classical grid search and probabilistic roadmaps”. In: Algorithmic Foundations of Robotics V, volume 7 of STAR, 59–76. Springer Berlin Heidelberg, 2004.
• [19] M. Likhachev, G. Gordon, and S. Thrun, “ARA*: Anytime A* with provable bounds on suboptimality”. In: Advances in Neural Information Processing Systems 16, British Columbia, Canada, 2004, 767–774.
• [20] A. Mandow, J. L. Martinez, J. Morales, J. L. Blanco, A. Garcia-Cerezo, and J. Gonzalez, “Experimental kinematics for wheeled skid-steer mobile robots”. In: 2007 IEEE/RSJ Int. Conf. Intelligent Robots and Systems, San Diego, USA, 2007, 1222–1227.
• [21] M. Michałek and K. Kozłowski, “Vector-Field-Orientation feedback control method for a differentially driven vehicle”, IEEE Transactions on Control Systems Technology, vol. 18, no. 1, 2010, 45–65, DOI: 10.1109/TCST.2008.2010406.
• [22] M. Michałek and K. Kozłowski, “Feedback control framework for car-like robots using the unicycle controllers”, Robotica, vol. 30, 2012, 517–535.
• [23] M. Michałek and K. Kozłowski, “Motion planning and feedback control for a unicycle in a way point following task: The VFO approach”, Int. J. Appl. Math. Comput. Sci., vol. 19, no. 4, 2009, 533–545, DOI: 10.2478/v10006-009-0042-2.
• [24] J. Pearl, Heuristics: Intelligent Search Strategies for Computer Problem Solving, Addison-Wesley Longman Publishing Co., Inc.: Boston, MA, USA, 1984.
• [25] M. Pivtoraiko and A. Kelly, “Differentially constrained motion replanning using state lattices with graduated fiidelity”. In: 2008 IEEE/RSJ Int. Conf. on Intelligent Robots and Systems, Nice, France, 2008, 2611–2616.
• [26] S. J. Russell and P. Norvig, Artifiicial Intelligence: A Modern Approach, Pearson Education, 2003.
• [27] D. S. Yershov and S. LaValle, “Simplicial Dijkstra and A* algorithms for optimal feedback planning”. In: 2011 IEEE/RSJ Int. Conf. on Intelligent Robots and Systems, San Francisco, CA, USA, 2011, 3862–3867.