Online bidirectional local trajectory planning and waypoint path refinement for mobile robots in state-time space

Abstract

We suggest a computationally efficient online local motion planning algorithm for mobile robots in unknown cluttered dynamic environments. The algorithm plans a trajectory incrementally up to the finite 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 first. Second, we use approximated reachable timed configuration or state region with uniform input. Moreover, for the computational efficiency, we check future collisions in configuration-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 modification 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 refinement method which refines the given path into shortest path based on visible space with little effort. Performances of the proposed algorithm are validated through extensive simulations and experiment with two types of mobile robots: a holonomic mobile robot and a differential drive mobile robot.

In this dissertation, online local motion planning for mobile robots in unknown cluttered dynamic environments is configured as three sub-problms.

First, We investigate a timed state or configuration space which is the state or configuration space at a given time of state-time space. In the timed state or configuration space, we define two important concepts, reachable region and safe region. Reachable region is the part of timed state or configuration 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 configuration) 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 modification 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 effectively, 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 refine 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.