TR2019-029

Improved A-search guided tree construction for kinodynamic planning


    •  Wang, Y., "Improved A-search guided tree construction for kinodynamic planning", IEEE International Conference on Robotics and Automation (ICRA), DOI: 10.1109/ICRA.2019.8793705, May 2019, pp. 5530-5536.
      BibTeX TR2019-029 PDF
      • @inproceedings{Wang2019may3,
      • author = {Wang, Yebin},
      • title = {Improved A-search guided tree construction for kinodynamic planning},
      • booktitle = {IEEE International Conference on Robotics and Automation (ICRA)},
      • year = 2019,
      • pages = {5530--5536},
      • month = may,
      • doi = {10.1109/ICRA.2019.8793705},
      • url = {https://www.merl.com/publications/TR2019-029}
      • }
  • MERL Contact:
  • Research Area:

    Control

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.