Section Patterns: Efficiently Solving Narrow Passage Problems in Multilevel Motion Planning

Sampling-based planning methods often become inefficient due to narrow\npassages. Narrow passages induce a higher runtime, because the chance to sample\nthem becomes vanishingly small. In recent work, we showed that narrow passages\ncan be approached by relaxing the problem using admissible lower-dimensional\nprojections of the state space. Those relaxations often increase the volume of\nnarrow passages under projection. Solving the relaxed problem is often\nefficient and produces an admissible heuristic we can exploit. However, given a\nbase path, i.e. a solution to a relaxed problem, there are currently no\ntailored methods to efficiently exploit the base path. To efficiently exploit\nthe base path and thereby its admissible heuristic, we develop section\npatterns, which are solution strategies to efficiently exploit base paths in\nparticular around narrow passages. To coordinate section patterns, we develop\nthe pattern dance algorithm, which efficiently coordinates section patterns to\nreactively traverse narrow passages. We combine the pattern dance algorithm\nwith previously developed multilevel planning algorithms and benchmark them on\nchallenging planning problems like the Bugtrap, the double L-shape, an egress\nproblem and on four pregrasp scenarios for a 37 degrees of freedom shadow hand\nmounted on a KUKA LWR robot. Our results confirm that section patterns are\nuseful to efficiently solve high-dimensional narrow passage motion planning\nproblems.\n