动态环境中移动机器人路径规划

摘要

如今机器人在静态环境下的路径规划问题已经有了很成熟的研究成果，并且可以高效地解决任何静态环境下的机器人寻路问题。然而，动态环境下机器人的路径规划问题仍然是一个具有挑战性的课题，因为我们需要为机器人增加一个新的维度——时间维度来描述并且解决问题。为了避免增加这个时间维度而使问题复杂化，很多处理动态环境的算法都将当前动态环境看成是静态的，并且每次运行都运用静态算法加以解决。这种算法看似高效，但是它有时找到的路径不是最优路径，并且很可能无解。本文引入了安全时间间隔这个概念，它所描述的是当前点无碰撞的持续时间段，也就是说，如果机器人在该点经过安全时间间隔之后或者之前的一个时间步，都会与障碍物发生碰撞。所以，在给予机器人路径信息的时候，不仅要有各节点的坐标，还要有每个节点的安全时间间隔。运用安全时间间隔的这种算法能够进行路径规划，在遇到障碍物的时候，可以等待运动障碍物通过再行走，而不是一味地寻找其他路径，这种算法会更加快捷、更加高效，而且更符合人类的思维。
　　 对于一个已经证明是最优的路径规划方法，它不像那种次优的路径规划方法那样易于扩展。因为加权A*算法已经被证明是比A*算法搜索速度更快的一种方法，所以本文使用加权A*算法对该算法进行扩展，减少了访问的节点数，并通过仿真实验证明了改进算法的有效性。
　　 在移动机器人路径规划过程中，当要求机器人在一个十分复杂的环境中快速搜索一条路径时，由于环境复杂，计算节点的数量过多，寻找到一条最优路径是很困难的。在实际生活中，往往需要机器人在给定的时间内，找出在这个时间内的可能最优路径，ARA*算法可以很好地解决这个问题。因此，本文利用ARA*算法的思想对上述算法进行改进，首先使机器人快速规划出一条较优路径，然后在时间允许的条件下尽可能地优化这条路径，因此本文的算法适合于更大、更复杂、更高维的动态环境。

目录

声明

学位论文的主要创新点

摘要

第一章 绪论

1．1 移动机器人概述

1．2 移动机器人路径规划研究现状

1．3 移动机器人路径规划发展趋势

1．4 课题的研究目的与意义

1．5 论文的结构安排

1．6 论文创新点

1．7 本章小结

第二章 移动机器人路径规划算法

2．1 路径规划概念简述

2．2 路径规划算法

2．2．1 传统路径规划算法

2．2．2 智能路径规划算法

2．3 A*算法

2．3．1 静态环境下的A*算法

2．3．2 动态环境下A*算法

2．4 本章小结

第三章 SIPP算法及其改进

3．1 引言

3．2 安全时间间隔的概念

3．3 寻找后继节点

3．4 SIPP算法

3．5 SIPP算法的仿真

3．6 基于加权A*算法的移动机器人路径规划

3．6．1 概述

3．6．2 加权A*算法的原理

3．6．2 基于加权A*算法的移动机器人路径规划的仿真

3．6．3 算法影响因素的分析

3．7 SIPP算法的理论分析

3．8 本章小结

第四章 基于加权A*算法的移动机器人路径规划的改进

4．1 引言

4．2 ARA*算法原理及仿真

4．2．1 ARA*算法的思想

4．2．1 搜索结果的重复利用

4．2．2 算法的执行过程

4．3 ARA*算法的仿真

4．3．1 静态环境下的仿真

4．3．2 动态环境下的仿真

4．3 算法的理论分析

4．4 本章小结

第五章 结论与展望

5．1 工作总结

5．2 未来展望

参考文献

发表论文和参加科研情况

附录

致谢