Bidirectional Heuristic Search for Motion Planning with an Extend Operator Samplingbased approaches are often favored in robotics for highdimensional motion planning for their fast exploration of the search space. However, at best they offer asymptotic guarantees on solution quality due to their inherent stochasticity. While planning, the majority of effort is often spent near the start and goal configurations with a large amount of free space in between. Bidirectional approaches such as RRTConnect exploit this fact by greedily extending and connecting search frontiers that simultaneously propagate from the start and goal configurations of a planning problem. In this work, we use such an extend operator for bidirectional heuristic searchbased planners, which typically struggle with highdimensionality. In doing so, we address the difficulty that these bidirectional planners face with connecting frontiers of both search efforts while providing suboptimality bounds on solution quality. We validate our simple approach on highdimensional manipulation tasks, demonstrating significantly reduced search effort when compared against other popular bidirectional algorithms, both searchbased and sampling. Our algorithm maintains theoretical guarantees on suboptimality and completeness for a given resolution. In addition, the solutions found by our planner are of higher quality compared to those found by the other baseline algorithms.

Escaping Local Minima in SearchBased Planning using Soft Duplicate Detection Searchbased planning for relatively lowdimensional motionplanning 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 statespace 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 nontrivial and often impossible depending on the dynamic constraints. In this paper, we explore a soft version of discretization, wherein the statespace 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 highlyconstrained settings and outperforms alternatives on several domains.