Route planning for mobile robots in time-dependent networks is investigated. The mobile robot is constrained to move in a prespecified network of roads. The environment contains a set of moving obstacles which are not necessarily constrained to move along arcs of the network and whose motions are assumed to be known. Due to dynamic objects in the environment, connectivity in the network changes over time, i.e., the network is time-dependent. Given such an environment, a method is presented to find a collision free route in the network that takes the mobile robot from a given start node to a destination node in minimum time. Our method generates a time-minimum path for all time intervals during which the destination node is reachable. The problem is solved by a two-level graph search: (1) path search using a space-time spanning tree and (2) path search in a time-dependent network. Algorithms for the two subproblems are presented and execution time of the algorithms is analyzed. © 1995 IEEE
https://doi.org/10.1109/70.388776Cite as:
@article{Fujimura_1995,
doi = {10.1109/70.388776},
url = {https://doi.org/10.1109%2F70.388776},
year = 1995,
month = {jun},
publisher = {Institute of Electrical and Electronics Engineers ({IEEE})},
volume = {11},
number = {3},
pages = {343--351},
author = {K. Fujimura},
title = {Time-minimum routes in time-dependent networks},
journal = {{IEEE} Transactions on Robotics and Automation}
}