Escaping Local Minima in Search-Based Planning Using Soft Duplicate Detection

November 2019

Escaping Local Minima in Search-Based Planning Using Soft Duplicate Detection

Authors:

Wei Du, Sung Kyun Kim, Oren Salzman, and Maxim Likhachev
Conference Paper
Proceedings of (IROS) IEEE/RSJ International Conference on Intelligent Robots and Systems

Abstract:

Search-based planning for relatively low-dimensional motion-planning problems such as for autonomous navigation and autonomous flight has been shown to be very successful. Such framework relies on laying a grid over a state-space and constructing a set of actions (motion primitives) that connect the centers of cells. However, in some cases such as kinodynamic motion planning, planning for bipedal robots with high balance requirements, computing these actions can be highly non-trivial and often impossible depending on the dynamic constraints. In this paper, we explore a soft version of discretization, wherein the state-space remains to be continuous but the search tries to avoid exploring states that are likely to be duplicates of states that have already been explored. We refer to this property of the search as soft duplicate detection and view it as a relaxation of the standard notion of duplicate detection. Empirically, we show that the search can efficiently compute paths in highly-constrained settings and outperforms alternatives on several domains.
@conference{Du-2019-120146,
author = {Wei Du And Sung Kyun Kim And Oren Salzman And Maxim Likhachev},
title = {Escaping Local Minima in Search-Based Planning Using Soft Duplicate Detection},
booktitle = {Proceedings of (IROS) IEEE/RSJ International Conference on Intelligent Robots and Systems},
year = {2019},
month = {November},
pages = {2365 - 2371},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.