TR2019-029

Improved A-search guided tree construction for kinodynamic planning



With node selection being directed by a heuristic cost [1]–[3], A-search guided tree (AGT) is constructed on-thefly and enables fast kinodynamic planning. This work presents two variants of AGT to improve computation efficiency. An improved AGT (i-AGT) biases node expansion through prioritizing control actions, an analogy of prioritizing nodes. Focusing on node selection, a bi-directional AGT (BAGT) introduces a second tree originated from the goal in order to offer a better heuristic cost of the first tree. Effectiveness of BAGT pivots on the fact that the second tree encodes obstacles information near the goal. Case study demonstrates that i-AGT consistently reduces the complexity of the tree and improves computation efficiency; and BAGT works largely but not always, particularly with no benefit observed for simple cases.