On responsiveness, safety, and completeness in real-time motion planning

Kris Hauser

Autonomous Robots, 2012

Summary

                  Replanning appears to be a powerful mechanism for controlling robot motion under hard constraints and unpredictable disturbances, involving a tradeoff between the planning horizon and its responsiveness to disturbances. A method commonly used is reactively replan at fixed time steps, with the risk of creating a myopic system, therefore adaptive time steps are proposed using “adaptive time stepping with exponential back-off” (ATS-EB), which learn a suitable time step according on whether the planner is able to make progress within the time limit. In order to perform research in this area, key aspect are: correctness, completeness and optimality (with this left for future research). Safety is a big concern in the literature (together with bounded rationality, time stepping issue and speed), Feron et al. introduced the notion of τ-safety, for which a trajectory results safe for at least time τ, establishing a hard deadline for replanning. Petti and Fraichard introduced the notion of “inevitable collision states” (ICS): a state for which no possible control can recover from a collision (using virtual obstacles is can prevent unnecessary explorations).

·       Model

In deterministic environment we the planner generated iteratively subsets of feasible states starting from an initial state at time t₀, planning can be stopped at any time when the trajectory that attains the least value of cost functional C(y) is found, if the planner is given no time limit on any query that admits a solution trajectory, then the planner find a solution in expected finite time. The ATS+EB algorithm (page 38) is supported by two theorems which ensure safety, completeness and competitiveness. The ATS+EB will never drive the robot to unfeasible state and the in a deterministic and perfectly modeled environment, with a reachable goal, it will always find the solution trajectory in finite expected time (which is demonstrated to be loosely bounded at 4NT_mac, where N are the iterations and T_max is the expected running time). Failures of type I are the one which go against the first theorem, therefore for which the global minima may alternate between to locally easy but globally difficult problems, type II errors are those for which the robot gets inadvertently into a dead-end.

In the case of uncertainty no safety guarantees are logically possible, therefore the “time to potential failure” (TTPF) is introduced in the ATS+C algorithm, which manages the replanning time step using this new parameter, keeping the robot safe as long as planning can increase TTPF faster than it is consumed (algorithm at page 43).

If the robot may seek to optimize the potential function V(x), then some degree of safety must sacrificed, since the algorithm seeks to both increase TTPF and improving V(x). The proposed algorithm (page 44) maintains both optimistic and pessimistic trajectory (the role of the pessimistic one, which is followed by default, is to optimize the TTPF, while the the optimistic one guides towards the goal).

In this case again there are two possible failures: type I, consisting of states for which escaping failure is difficult for the planner, type II, consisting in inevitable failure. Increasing the computational power these two errors can be considerably resuced.

Key Concepts

Adaptive time step, replanning

Key Results

The experiments and results prove that using fixed cutoff with windows which are too short provoke unrealiability, since escaping can be possible on local minima, but also an extended windows my be problematic under the point of view of time to achieve the goal. The adaptive strategy appears to be the best except for narrow passages for which it is 45% slower than the best constant cutoff. Replanning is demonstrated to be a viable mechanism for real-time navigation and obstacle avoidance in dynamic environments.