A Linear Interpolation-Based Algorithm for Path Planning and Replanning on Girds

• 作者: Changwen Zheng Huafei Yin Jiawei Cai
• 来源期刊: 线性代数与矩阵理论研究进展(英文)
• 学科: 数学
• 关键词: Field D* Algorithm PATH Planning and Replanning Any-Angle PATH Linear INTERPOLATION GRID Cell
• 年，卷（期）: 2012,（2）
• 页码范围: 20-24
• 页数: 5页
• 分类号: O1

摘要

Field D* algorithm is widely used in mobile robot navigation since it can plan and replan any-angle paths through non-uniform cost grids. However, it still suffers from inefficiency and sub-optimality. In this article, a new linear interpolation-based planning and replanning algorithm, Update-Reducing Field D*, is proposed. It employs different approaches during initial planning and replanning respectively in order to reduce the number of updates of the rhs-values of vertices. Experiments have shown that Update-Reducing Field D* runs faster than Field D* and returns smoother and lower-cost paths.