Learning real-time search on c-space GVDs

Abstract

In the context of robotics, configuration space (cspace) is widely used for non-circular robots to engage tasks such as path planning, collision check, and motion planning. In many real-time applications, it is important for a robot to give a quick response to the user’s command. Therefore, a constant bound on planning time per action is severely imposed. However, existing search algorithms used in c-space gain first move lags which vary with the size of the underlying problem. Furthermore, applying real-time search algorithms on c-space maps often causes the robots being trapped within local minima. In order to solve the above mentioned problems, we extend the learning real-time search (LRTS) algorithm to search on a set of c-space generalized Voronoi diagrams (c-space GVDs), helping the robots to incrementally plan a path, to efficiently avoid local minima, and to execute fast movement. In our work, an incremental algorithm is firstly proposed to build and represent the c-space maps in Boolean vectors. Then, the method of detecting grid-based GVDs from the c-space maps is further discussed. Based on the c-space GVDs, details of the LRTS and its implementation considerations are studied. The resulting experiments and analysis show that, using LRTS to search on the c-space GVDs can 1) gain smaller and constant first move lags which is independent of the problem size; 2) gain maximal clearance from obstacles so that collision checks are much reduced; 3) avoid local minima and thus prevent the robot from visually unrealistic scratching.

Keywords

generalized Voronoi diagrams / real-time search / robotics / configuration space / incremental algorithms

References

[1] HartP E, Nilsson N J, RaphaelB . A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 1968, 4(2): 100–107

[2] StoutB. Smart moves: intelligent pathfinding. Game Developer Magazine, 1996, 10: 28–35

[3] HansenE A, ZhouR. Anytime heuristic search. Journal of Artificial Intelligence Research, 2007, 28: 267–297

[4] FurcyD. Itsa*: iterative tunneling search with a*. In: Proceedings of the National Conference on Artificial Intelligence, Workshop on Heuristic Search, Memory-Based Heuristics and Their Applications. 2006

[5] StentzA. The focussed D* algorithm for real-time replanning. In: Proceedings of International Joint Conference on Artificial Intelligence. 1995, 1652–1659

[6] KoenigS, Simmons R G. Solving robot navigation problems with initial pose uncertainty using real-time heuristic search. In: Proceedings of the National Academy of Sciences of the United States of America. 1998, 145–153

[7] KoeingS, ToveyC, SmirnovY. Performance bounds for planning in unknown terrain. Artificial Intelligence, 2003, 147(1): 253–279

[8] KorfR E. Real-time heuristic search. Artificial Intelligence, 1990, 42(2): 189–211

[9] Lozano-PerezT. Spatial planning: a configuration space approach. IEEE Transactions on Computers, 1983, 100(2): 108–120

[10] MedinaO, TaitzA, MosheB B, Shvalb N. C-space compression for robots motion planning. International Journal of Advanced Robotic Systems, 2013, 10(1):6

[11] MaL, XueJ R, KawabataK, Zhu J H, MaC , ZhengN N. Efficient sampling-based motion planning for on-road autonomous driving. IEEE Transactions on Intelligent Transportation Systems, 2015, 16(4): 1961–1976

[12] WiseK D, BowyerA. A survey of global configuration-space mapping techniques for a single robot in a static environment. The International Journal of Robotics Research, 2000, 19(8):762–779

[13] JiaoL N, TangZ M. Building configuration space for multiple UGVs. In: Proceedings of IEEE International Conference on Vehicular Electronics and Safety. 2005, 245–250

[14] BeharE, LienJ M. A new method for mapping the configuration-space obstacles of polygons. Technical Report GMU–CS-TR-2011-11. 2010

[15] KavrakiL E. Computation of configuration-space obstacles using the fast Fourier transform. IEEE Transactions on Robotics and Automation, 1995, 11(3): 408–413

[16] LauB, SprunkC, BurgardW. Efficient grid-based spatial representations for robot navigation in dynamic environments. Robotics and Autonomous Systems, 2013, 61(10): 1116–1130

[17] RussellS J, WefaldE. Do the Right Thing: Studies in Limited Rationality. Cambridge: MIT press, 1991

[18] KoenigS. A comparison of fast search methods for real-time situated agents. In: Proceedings of the 3rd International Joint Conference on Autonomous Agents and Multiagent Systems—Volume 2. 2004, 864–871

[19] BulitkoV. Lookahead pathologies and meta-level control in real-time heuristic search. In: Proceedings of the 15th Euromicro Conference on Real-Time Systems. 2003, 13–16

[20] BulitkoV, LiL, GreinerR, Levner I. Lookahead pathologies for single agent search. In: Proceedings of International Joint Conference on Artificial Intelligence. 2003, 1531–1533

[21] ShimboM, IshidaT. Controlling the learning process of real-time heuristic search. Artificial Intelligence, 2003, 146(1): 1–41

[22] SturtevantN, BuroM. Partial pathfinding using map abstraction and refinement. In: Proceedings of the National Conference on Artificial Intelligence. 2005, 1392–1397

[23] SturtevantN, JansenR. An analysis of map-based abstraction and refinement. In: Proceedings of International Symposium on Abstraction, Reformulation, and Approximation. 2007, 344–358

[24] BulitkoV, Sturtevant N, LuJ S , YauT. Graph abstraction in real-time heuristic search. Journal of Aritificial Intelligence Research, 2007, 30: 51–100

[25] BulitkoV, Sturtevant N, KazakevichM . Speeding up learning in realtime search via automatic state abstraction. In: Proceedings of the National Conference on Artificial Intelligence. 2005, 1349–1354

[26] BulitkoV, Sturtevant N. State abstraction for real-time moving target pursuit: a pilot study. In: Proceedings of AAAIWorkshop on Learning For Research. 2006, 72–79

[27] LawrenceR, Bulitko V. Database-driven real-time heuristic search in video-game pathfinding. IEEE Transactions on Computational Intelligence and AI in Games, 2013,5(3): 227–241

[28] YaziciA, KirlikG, ParlaktunaO , SipahiogluA. A dynamic path planning approach for multi-robot sensor-based coverage considering energy constraints. In: Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems. 2009, 5930–5935

[29] TsardouliasE G, SerafiA T, PanourgiaM N , PapazoglouA, Petrou L. Construction of minimized topological graphs on occupancy grid maps based on GVD and sensor coverage information. Journal of Intelligent and Robotic Systems, 2014, 75(3–4): 457–474

[30] TakahashiO, Schilling R J. Motion planning in a plane using generalized Voronoi diagrams. IEEE Transactions on Robotics and Automation, 1989, 5(2): 143–150

[31] ChosetH, Nagatani K. Topological simultaneous localization and mapping: toward exact localization without explicit localization.IEEE Transactions on Robotics and Automation, 2001, 17(2): 125–137

[32] FranchiA, FredaL, OrioloG, Vendittelli M. The sensor-based random graph method for cooperative robot exploration.IEEE/ASME Transactions on Mechatronics, 2009, 14(2): 163–175

[33] GarridoS, MorenoL, BlancoD, Jurewicz P. Path planning for mobile robot navigation using voronoi diagram and fast marching. International Journal of Robot Automation, 2011, 2(1): 42–64

[34] WuL, García M A, Puig VallsD , Solé RibaltaA. Voronoi-based space partitioning for coordinated multi-robot exploration. Journal of Physical Agents, 2007, 1(1): 37–44

[35] KalraN, Ferguson D, StentzA . Incremental reconstruction of generalizedVoronoi diagrams on grids. Robotics and Autonomous Systems, 2009, 57(2): 123–128

[36] SchererS, Ferguson D, SinghS . Efficient c-space and cost function updates in 3D for unmanned aerial vehicles. In: Proceedings of IEEE International Conference on Robotics and Automation. 2009, 2049–2054

[37] LauB, SprunkC, BurgardW. Improved updating of Euclidean distance maps and Voronoi diagrams. In: Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems. 2010, 281–286

[38] TheronR, MorenoV, CurtoB, Blanco F J. Configuration space of 3D mobile robots: parallel processing. In: Proceedings of the 11th International Conference on Advanced Robotics. 2003

RIGHTS & PERMISSIONS

2017 Higher Education Press and Springer-Verlag Berlin Heidelberg