避障问题最短路径的两级动态规划算法

研究了任意点对的平面避障问题.用凸多边形表示障碍物,凸多边形的集合构成障碍环境.在此基础上,提出了一种新的路径规划思路:对图结构进行扩展,用传统的Floyed算法进行一级规划;对传统Floyed算法扩展后进行二级规划,很好地解决了任意点对的平面避障问题.利用矢量间夹角的关系来判断障碍环境中点对的连线是否交叉于多边形.经理论证明和算例验证,该算法方便简洁,容易实现,表明了算法的正确性.