The speed graph method: pseudo time optimal navigation among obstacles subject to uniform braking safety constraints

详细信息    查看全文

• 作者：Gil Manor ; Elon Rimon
• 关键词：Mobile robot time optimal navigation ; High speed navigation ; Mobile robot safety
• 刊名：Autonomous Robots
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：41
• 期：2
• 页码：385-400
• 全文大小：
• 刊物类别：Computer Science
• 刊物主题：Robotics and Automation; Artificial Intelligence (incl. Robotics); Computer Imaging, Vision, Pattern Recognition and Graphics; Control, Robotics, Mechatronics;
• 出版者：Springer US
• ISSN：1573-7527
• 卷排序：41

文摘

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.