Multi-Resolution State Roadmap Method for Trajectory Planning

Yuichi TAZAKI; Jingyu XIANG; Tatsuya SUZUKI; Blaine LEVEDAHL

doi:10.1587/transfun.E99.A.954

Multi-Resolution State Roadmap Method for Trajectory Planning

Yuichi TAZAKI, Jingyu XIANG, Tatsuya SUZUKI, Blaine LEVEDAHL

Full Text Views

0

Cite this

Summary :

This research develops a method for trajectory planning of robotic systems with differential constraints based on hierarchical partitioning of a continuous state space. Unlike conventional roadmaps which is constructed in the configuration space, the proposed state roadmap also includes additional state information, such as velocity and orientation. A bounded domain of the additional state is partitioned into sub-intervals with multiple resolution levels. Each node of a state roadmap consists of a fixed position and an interval of additional state values. A valid transition is defined between a pair of nodes if any combination of additional states, within their respective intervals, produces a trajectory that satisfies a set of safety constraints. In this manner, a trajectory connecting arbitrary start and goal states subject to safety constraints can be obtained by applying a graph search technique on the state roadmap. The hierarchical nature of the state roadmap reduces the computational cost of roadmap construction, the required storage size of computed roadmaps, as well as the computational cost of path planning. The state roadmap method is evaluated in the trajectory planning examples of an omni-directional mobile robot and a car-like robot with collision avoidance and various types of constraints.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E99-A No.5 pp.954-962

Publication Date: 2016/05/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1587/transfun.E99.A.954

Type of Manuscript: PAPER

Category: Mathematical Systems Science

Authors

Yuichi TAZAKI
  Nagoya University
Jingyu XIANG
  Nagoya University
Tatsuya SUZUKI
  Nagoya University
Blaine LEVEDAHL
  Nagoya University

Keyword

multi-resolution, roadmap, trajectory planning

Cite this

Copy

Yuichi TAZAKI, Jingyu XIANG, Tatsuya SUZUKI, Blaine LEVEDAHL, "Multi-Resolution State Roadmap Method for Trajectory Planning" in IEICE TRANSACTIONS on Fundamentals, vol. E99-A, no. 5, pp. 954-962, May 2016, doi: 10.1587/transfun.E99.A.954.
Abstract: This research develops a method for trajectory planning of robotic systems with differential constraints based on hierarchical partitioning of a continuous state space. Unlike conventional roadmaps which is constructed in the configuration space, the proposed state roadmap also includes additional state information, such as velocity and orientation. A bounded domain of the additional state is partitioned into sub-intervals with multiple resolution levels. Each node of a state roadmap consists of a fixed position and an interval of additional state values. A valid transition is defined between a pair of nodes if any combination of additional states, within their respective intervals, produces a trajectory that satisfies a set of safety constraints. In this manner, a trajectory connecting arbitrary start and goal states subject to safety constraints can be obtained by applying a graph search technique on the state roadmap. The hierarchical nature of the state roadmap reduces the computational cost of roadmap construction, the required storage size of computed roadmaps, as well as the computational cost of path planning. The state roadmap method is evaluated in the trajectory planning examples of an omni-directional mobile robot and a car-like robot with collision avoidance and various types of constraints.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E99.A.954/_p

Copy

@ARTICLE{e99-a_5_954,
author={Yuichi TAZAKI, Jingyu XIANG, Tatsuya SUZUKI, Blaine LEVEDAHL, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Multi-Resolution State Roadmap Method for Trajectory Planning},
year={2016},
volume={E99-A},
number={5},
pages={954-962},
abstract={This research develops a method for trajectory planning of robotic systems with differential constraints based on hierarchical partitioning of a continuous state space. Unlike conventional roadmaps which is constructed in the configuration space, the proposed state roadmap also includes additional state information, such as velocity and orientation. A bounded domain of the additional state is partitioned into sub-intervals with multiple resolution levels. Each node of a state roadmap consists of a fixed position and an interval of additional state values. A valid transition is defined between a pair of nodes if any combination of additional states, within their respective intervals, produces a trajectory that satisfies a set of safety constraints. In this manner, a trajectory connecting arbitrary start and goal states subject to safety constraints can be obtained by applying a graph search technique on the state roadmap. The hierarchical nature of the state roadmap reduces the computational cost of roadmap construction, the required storage size of computed roadmaps, as well as the computational cost of path planning. The state roadmap method is evaluated in the trajectory planning examples of an omni-directional mobile robot and a car-like robot with collision avoidance and various types of constraints.},
keywords={},
doi={10.1587/transfun.E99.A.954},
ISSN={1745-1337},
month={May},}

Copy

TY - JOUR
TI - Multi-Resolution State Roadmap Method for Trajectory Planning
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 954
EP - 962
AU - Yuichi TAZAKI
AU - Jingyu XIANG
AU - Tatsuya SUZUKI
AU - Blaine LEVEDAHL
PY - 2016
DO - 10.1587/transfun.E99.A.954
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E99-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 2016
AB - This research develops a method for trajectory planning of robotic systems with differential constraints based on hierarchical partitioning of a continuous state space. Unlike conventional roadmaps which is constructed in the configuration space, the proposed state roadmap also includes additional state information, such as velocity and orientation. A bounded domain of the additional state is partitioned into sub-intervals with multiple resolution levels. Each node of a state roadmap consists of a fixed position and an interval of additional state values. A valid transition is defined between a pair of nodes if any combination of additional states, within their respective intervals, produces a trajectory that satisfies a set of safety constraints. In this manner, a trajectory connecting arbitrary start and goal states subject to safety constraints can be obtained by applying a graph search technique on the state roadmap. The hierarchical nature of the state roadmap reduces the computational cost of roadmap construction, the required storage size of computed roadmaps, as well as the computational cost of path planning. The state roadmap method is evaluated in the trajectory planning examples of an omni-directional mobile robot and a car-like robot with collision avoidance and various types of constraints.
ER -