论文部分内容阅读
摘 要 文章基于“拉线原理”，研究了给定场景下机器人避障行走的最短路径及最短时间路径问题。获得了给定场景下机器人避障行走的最短路径；最短时间路径。
关键词 最短路径；最短时间路径；拉线原理；避障路径
中图分类号：TP242 文献标识码：A 文章编号：1671-7597（2013）16-0059-02
1 问题的提出
一个有障碍物的平面场景（图1所示）中有一个机器人在区域内活动，障碍物（表1所示）外指定一点为机器人要到达的目标点。机器人直线行走的最大速度为个单位/秒。机器人转弯时，最大转弯速度。如果超过该速度，机器人将发生侧翻，无法完成行走。
2 需要解决的问题
建立机器人从区域中一点到达另一点的避障最短路径和最短时间路径的数学模型。对场景图中，具体计算：机器人从出发，的最短路径。2）机器人从O出发，到达A的最短时间路径。
3 模型分析及建模思路
1）行走路线与最短路径：机器人从起点到终点由于障碍物不同会有多种不同路线，在同一路线中则存在唯一的最短路径。基于“拉线原理”可寻得最短路径。“拉线原理”：从起点到终点沿行走路线拉一根线，此线被障碍区域阻隔，当将线拉紧时，起点到终点的线长即为该行走路线的唯一最短路径。
2）单障碍与多障碍：当起点与终点之间只有一个障碍时称单障碍模型，此时便有两条行走路线，可分别根据“拉线原理”得到相应最短路径再进行比较，即可得最短路径。当起点与终点之间超过一个障碍时称多障碍模型，选择恰当的划分方法，依据“拉线原理”可将多障碍模型进行划分成由多个单障碍模型连接组成。
3）折线转向与圆弧转弯：从起点（或终点）面向障碍物的视野有两个边界，“拉线原理”在边界点处，存在折线转向与圆弧转弯两种情况。由于机器人行走的限制，必须对视野边界点进行圆弧化处理后再应用“拉线原理”。按模型要求，在边界点为圆心，为半径画圆作为障碍区域新边界，再应用“拉线原理”可得本模型最短路径。
4）考虑到机器人转弯速度因素，当转弯半径越小时，行走速度会越小，可在转弯圆弧中点处做一條切线，以此切线切点为准的公共切线圆作为转弯圆弧，应用“拉线原理”求得最短时间路径。
4 模型建立
4.1 单障碍最短路径模型
设机器人行走起点与目标终点之间存在一个障碍，以O为圆心，为半径作圆，按照“拉线原理”，所求路线中最短路径满足
利用程序求解得：，此模型是解决机器人避障模型的基本单元。
4.2 多障碍最短路径模型
由于机器人行走起点与目标终点有多个障碍区域（或单个复杂区域），造成视野边界点无法同时看到起点与中点，假设机器人从起点到目标点可划分为n个单障碍模型基本单元（i=1，2，……n）。那么目标函数可以表示为：
用此模型就可以对起点到目标点之间的路径进行优化求解。
4.3 给定场景下最短路径模型求解
应用“拉线原理”，计算各个路线的最短路径相互比较可得最优行走路线以及最短路径。知的最优行走路线为，最短路径；的最优行走路线最短路径；
4.4 最短时间路径模型求解
根据单障碍最短路径模型，可得：
5 模型评价与改进
模型优点：运用多方案对路径进行优化，从简到繁，取得最优解；模型优化后用几何图形结合计算机数学软件进行求解，精确度较高；通过软件模型进行绘图，简单易懂，便于实际检验及应用。
模型缺陷：在障碍物较多时，且形状不规则时，模型需要进一步改进。
参考文献
[1]机器人行走问题.http：//wenku.baidu.com/view/59fd857aa26925c52cc5bf4c.html.
[2]尤承业.解析几何[M].北京，北京大学出版社，2004.
[3]周培德.计算几何—算法与设计[M].北京清华大学出版社，2005.
关键词 最短路径；最短时间路径；拉线原理；避障路径
中图分类号：TP242 文献标识码：A 文章编号：1671-7597（2013）16-0059-02
1 问题的提出
一个有障碍物的平面场景（图1所示）中有一个机器人在区域内活动，障碍物（表1所示）外指定一点为机器人要到达的目标点。机器人直线行走的最大速度为个单位/秒。机器人转弯时，最大转弯速度。如果超过该速度，机器人将发生侧翻，无法完成行走。
2 需要解决的问题
建立机器人从区域中一点到达另一点的避障最短路径和最短时间路径的数学模型。对场景图中，具体计算：机器人从出发，的最短路径。2）机器人从O出发，到达A的最短时间路径。
3 模型分析及建模思路
1）行走路线与最短路径：机器人从起点到终点由于障碍物不同会有多种不同路线，在同一路线中则存在唯一的最短路径。基于“拉线原理”可寻得最短路径。“拉线原理”：从起点到终点沿行走路线拉一根线，此线被障碍区域阻隔，当将线拉紧时，起点到终点的线长即为该行走路线的唯一最短路径。
2）单障碍与多障碍：当起点与终点之间只有一个障碍时称单障碍模型，此时便有两条行走路线，可分别根据“拉线原理”得到相应最短路径再进行比较，即可得最短路径。当起点与终点之间超过一个障碍时称多障碍模型，选择恰当的划分方法，依据“拉线原理”可将多障碍模型进行划分成由多个单障碍模型连接组成。
3）折线转向与圆弧转弯：从起点（或终点）面向障碍物的视野有两个边界，“拉线原理”在边界点处，存在折线转向与圆弧转弯两种情况。由于机器人行走的限制，必须对视野边界点进行圆弧化处理后再应用“拉线原理”。按模型要求，在边界点为圆心，为半径画圆作为障碍区域新边界，再应用“拉线原理”可得本模型最短路径。
4）考虑到机器人转弯速度因素，当转弯半径越小时，行走速度会越小，可在转弯圆弧中点处做一條切线，以此切线切点为准的公共切线圆作为转弯圆弧，应用“拉线原理”求得最短时间路径。
4 模型建立
4.1 单障碍最短路径模型
设机器人行走起点与目标终点之间存在一个障碍，以O为圆心，为半径作圆，按照“拉线原理”，所求路线中最短路径满足
利用程序求解得：，此模型是解决机器人避障模型的基本单元。
4.2 多障碍最短路径模型
由于机器人行走起点与目标终点有多个障碍区域（或单个复杂区域），造成视野边界点无法同时看到起点与中点，假设机器人从起点到目标点可划分为n个单障碍模型基本单元（i=1，2，……n）。那么目标函数可以表示为：
用此模型就可以对起点到目标点之间的路径进行优化求解。
4.3 给定场景下最短路径模型求解
应用“拉线原理”，计算各个路线的最短路径相互比较可得最优行走路线以及最短路径。知的最优行走路线为，最短路径；的最优行走路线最短路径；
4.4 最短时间路径模型求解
根据单障碍最短路径模型，可得：
5 模型评价与改进
模型优点：运用多方案对路径进行优化，从简到繁，取得最优解；模型优化后用几何图形结合计算机数学软件进行求解，精确度较高；通过软件模型进行绘图，简单易懂，便于实际检验及应用。
模型缺陷：在障碍物较多时，且形状不规则时，模型需要进一步改进。
参考文献
[1]机器人行走问题.http：//wenku.baidu.com/view/59fd857aa26925c52cc5bf4c.html.
[2]尤承业.解析几何[M].北京，北京大学出版社，2004.
[3]周培德.计算几何—算法与设计[M].北京清华大学出版社，2005.