We suggest a computationally eﬃcient online local motion planning algorithm for mobile robots in unknown cluttered dynamic environments. The algorithm plans a trajectory incrementally up to the ﬁnite horizon in state-time space. We systematize bidirectional trajectory planning with three kinds of trajectories: a forward trajectory from the current robot state, a backward trajectory from the state of current target waypoint, and a connecting trajectory between the forward and backward trajectories. Since it is computationally complex to plan a trajectory minimizing given cost-to-go in state-time space, we adopt two simplifying approaches: First, we decompose a cost-to-go function into several parts and we minimize the more dominant part ﬁrst. Second, we use approximated reachable timed conﬁguration or state region with uniform input. Moreover, for the computational eﬃciency, we check future collisions in conﬁguration-time space instead of checking inevitable collision state (ICS) in state-time space in order to predict future collisions in advance. When the incrementally planned trajectory is fallen in ICS, we perform the partial trajectory modiﬁcation scheme using interim goal (a temporary goal for the robot to pass through at the expected collision time in order to avoid the collision), which enables the robot to cope with cluttered dynamic environments. Additionally, we suggest an online path reﬁnement method which reﬁnes the given path into shortest path based on visible space with little eﬀort. Performances of the proposed algorithm are validated through extensive simulations and experiment with two types of mobile robots: a holonomic mobile robot and a diﬀerential drive mobile robot.
In this dissertation, online local motion planning for mobile robots in unknown cluttered dynamic environments is conﬁgured as three sub-problms.
First, We investigate a timed state or conﬁguration space which is the state or conﬁguration space at a given time of state-time space. In the timed state or conﬁguration space, we deﬁne two important concepts, reachable region and safe region. Reachable region is the part of timed state or conﬁguration space bounded by motion constraint. Safe region is the region limited by obstacle constraint as well as motion constraint. And we suggest the way how to determine a timed state in a timed state (or conﬁguration) space which is the state sapce at a certain time in state-time space with given motion and obstacle constraints.
Second, we suggest an approach how to avoid obstacles in dynamic cluttered environments based on state-time space. In spite of the small computaional load, suggested method copes with cluttered dynamic environments avoiding ICS using the partial trajectory modiﬁcation scheme.
Third, we suggest an approach how to minimize cost-to-go near waypoints and goal. To pass through given waypoints and arrive at the goal eﬀectively, we adopt the bidirectional trajectory planning which plans three trajectories: forward trajectory from the robot state and backward trajectory from the current target waypoint that forward trajectory is heading to pass through, and connection trajectory between forward and backward trajectories.
Fourth, we suggest an approach how to reﬁne the waypoint path online. A local waypoint path from the robot to a local goal on global waypoint path is planned to follow the global waypoint path without falling in local minima or any collision with sensed obstacles.
The last one is included in further work.