This paper considers the synthesis of pseudo time optimal paths for a mobile robot navigating among obstacles subject to uniform braking safety constraints. The classical Brachistochrone problem studies the time optimal path of a particle moving in an obstacle free environment subject to a constant force field. By encoding the mobile robot’s braking safety constraint as a force field surrounding each obstacle, the paper generalizes the Brachistochrone problem into safe time optimal navigation of a mobile robot in environments populated by polygonal obstacles. Convexity of the safe travel time functional, a path dependent function, allows efficient construction of a speed graph for the environment. The speed graph consists of safe time optimal arcs computed as convex optimization problems in \(O(n^3 \log (1/\epsilon ))\) total time, where n is the number of obstacle features in the environment and \(\epsilon \) is the desired solution accuracy. Once the speed graph is constructed for a given environment, pseudo time optimal paths between any start and target robot positions can be computed along the speed graph in \(O(n^2\log n)\) time. The results are illustrated with examples and described as a readily implementable procedure.
['Gil Manor', 'Elon Rimon']
The speed graph method: pseudo time optimal navigation among obstacles subject to uniform braking safety constraints