Generalized Lazy Search for Robot Motion Planning: Interleaving Search\n and Edge Evaluation via Event-based Toggles

Abstract

Lazy search algorithms can efficiently solve problems where edge evaluation\nis the bottleneck in computation, as is the case for robotic motion planning.\nThe optimal algorithm in this class, LazySP, lazily restricts edge evaluation\nto only the shortest path. Doing so comes at the expense of search effort,\ni.e., LazySP must recompute the search tree every time an edge is found to be\ninvalid. This becomes prohibitively expensive when dealing with large graphs or\nhighly cluttered environments. Our key insight is the need to balance both edge\nevaluation and search effort to minimize the total planning time. Our\ncontribution is two-fold. First, we propose a framework, Generalized Lazy\nSearch (GLS), that seamlessly toggles between search and evaluation to prevent\nwasted efforts. We show that for a choice of toggle, GLS is provably more\nefficient than LazySP. Second, we leverage prior experience of edge\nprobabilities to derive GLS policies that minimize expected planning time. We\nshow that GLS equipped with such priors significantly outperforms competitive\nbaselines for many simulated environments in R2, SE(2) and 7-DoF manipulation.\n