Proximate time-optimal algorithm for on-line path parameterization and modification

This paper presents an new, proximate-optimal solution to the path-constrained time-parameterization problem. This new algorithm has three distinguishing features: First, the run-time worst-case complexity of the proximate time-optimal algorithm is linear with respect to path-length and it is shown to be more efficient than any other truly time-optimal algorithm. Second, for a given robotic system, the algorithm's running-time is predictable as a function of the length of the path (allowing its use in combination with time-aware planners). Third, the algorithm easily supports the modification of on-going trajectories. The algorithm has been extensively tested and is operational in a number of robotic systems including a dual-arm workcell, an underwater robotic system, and the Marsokhod Rover vehicle. Experimental results presented illustrate the online use of the algorithm with a path planner to allow capture and delivery of objects from a moving conveyor belt.