Paper Info
Title
The speed graph method: pseudo time optimal navigation among obstacles subject to uniform braking safety constraints.
Abstract
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 ))$$O(n3log(1/∈)) 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)$$O(n2logn) time. The results are illustrated with examples and described as a readily implementable procedure.
Year
DOI
Venue
2017
10.1007/s10514-015-9538-9
Auton. Robots
Keywords
Field
DocType
Mobile robot time optimal navigation,High speed navigation,Mobile robot safety
Binary logarithm,Obstacle,Polygon,Convexity,Computer science,Simulation,Brachistochrone curve,Robot,Convex optimization,Mobile robot
Journal
Volume
Issue
ISSN
41
2
0929-5593
Citations 
PageRank 
References 
0
0.34
10
Authors
2
Name
Order
Citations
PageRank
Gil Manor131.45
Elon Rimon21128157.34