中文摘要：

为保证室内机器人以低成本在一条无碰有效的路径上移动,提出了基于CA模型的改进D＊路径规划算法。结合元胞自动机理论,引入扩展Moore型邻居结构,降低机器人角度变化的最小增量,并为障碍物周围元胞设置碰撞系数,离障碍物越近的元胞被选中的概率越低。采用多个地图针对不同情况进行仿真实验。实验结果表明,在一般环境下,该算法与D＊算法相比,转角数目减少36.36%,算法运行时间缩短31.25%,且规划出的路径与障碍物保持安全距离,同时避免了路径穿越障碍物,具有很高的可行性。

英文摘要：

In order to ensure the indoor robot moving in an effective path with no collision at low cost, improved D ＊ path planning algorithm based on CA（ cellular automata） model is proposed, in which extended Moore neighbor- hood structure of cellular automata is used to reduce the minimum incremental changes of angle and collision coeffi- cients are setted for cells around obstacles to reduce the probability of being chosen. The author conducted experi- ments on different maps and the results have shown that compared with D ＊ algorithm in the general surroundings, improved algorithm can reduce the number of corners by 36.36% and shorten running time of the algorithm by 31. 25%. What＇s more, the path planned with improved D ＊ algorithm guarantees a safe distance between path and obstacles , and it also avoids acrossing the obstacles. In the aetual indoor environment, the improved D ＊ algorithm has very high feasibility.