足球后卫 毕业论文由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“足球毕业论文”。
目 录
摘要------------------------1 ABSTRACT------------------2 第一章绪论---------------1 1．1 课题来源及研究背景----------------------1 1.1.1课题来源10 3.2.1 阵形-----10 3.2.2 阵形因子-----------------------------10 3.2.3 阵形分类-----------------------------11 3.2.4 Agent阵形库------------------------11 I
3.3 基于阵形变换的防守模型--------------12 3.3.1.常用阵形变换方法-----------------12 3.3.2.一种新型的阵形变换方法--------13 3.4 小结------------14 第四章 基于SBD策略的后卫防守模型-----15 4.1 几种常见的后卫防守模型--------------15 4.1.1 盯人防守模型-----------------------15 4.1.2 角色防守模型-----------------------17 4.1.3 区域防守模型-----------------------18 4.2 基于SBD策略的后卫防守模型------19 4.2.1 SBD策略------------------------------19 4.2.2 防守型SBD策略--------------------19 4.2.3 基于SBD策略的后卫防守模型6)(3)当 n >_2时: OptDir=Ai+ MaxAng/2.0(4一 7)其中 i 值 由MaxAng对应的角决定。
计算 出 OptDir后，我方控球队员踢球的方向就确定了，图4-4是当n>_2时表示OptDir的示意图。当我方控球队员将球以OptDir方向踢出后，由于采用的是大力踢球策略，这样使球能够得到较大的速度，同时踢球方向的推倒过程又保证了球进入对方半场或踢到边线之前不易被对手截获。这样，在我方半场的对方球员回防之前，球被很快压入对方半场，我方山防守转向进攻，此时对方的防守相对较弱，增加了我方射门得分的机会。可见，当对手攻入我方半场时，在我方球员断球成功后应用SBDD策略，能够较好地达到破坏对手协作进攻的目的。
2.实例学习在SBDD策略中的应用
SBDD策略的具体应用中，扇形区域Sec(amin,amax,r)大小的确定是一个关键问题，在CSU YunLu2003中我们采用了实例学习[46】的方法来获得这三个量的值。
实例学习是人工智能中一类机器学习方法，这种学习方法也称为归纳学习(Learning by induction)，是目前机器学习方法中最成熟的一种。通过实例学习 就是从具体训练例子中推导出一般规则，学习活动的全过程可用两空间模型来说 明，如图4-5所示。
图 4一 5 两 空 间 模 型
例子空间就是向系统提供的训练例集合，规则空Nl是对事物所具有的规律性的描述。实例学习的过程就是要在训练例的指导下，在规则空间进行搜索，以找到我们所要学习的概念描述。结合SBDD策略，各变量的各种取值组成了例子空间，以机器人足球仿真比赛中的相关规则作为规则空间，通过实际比赛进行训练，从中找到合适的Sec区域。
在学 习 过 程中，我们以实际比赛中球在对方半场的时间t与整场比赛的时间 T的比值R=OT作为衡量Sec取值的性能指标。R越大表明球被压入对方半场的时间越长，而对应的Sec取值越合适。
3.SBDD策略的采用度d 在仿真比赛中，当球员得到控球权后，要采用某种策略来选择下一步动作，如传球、带球过人、下底传中等等。我们把一场比赛中控球队员执行SBDD策略的次数。与该球员控球时所采用策略的总数N的比值称为SBDD策略的采用度，用d表示，其中
d=n1N。提出采用度的概念，主要为了研究SBDD策略的不同使用程度对整个仿真球队的影响。
SBDD 策 略具有较强的反协作能力，但由此也带来了一定的震荡性，即可能导致某段时间球在两个半场之间拉锯，从而造成球员体力消耗过大。我们从训练中发现这种震荡性与d的取值有关，而且d值越大出现震荡的可能性也随之增大。因此，在采用SBDD策略时一定要根据球队的自身特点来确定d的取值。
在 CSU_YunLu2003仿真球队中我们对己经实现的多种SBD策略进行了测试。测试比赛是在SoccerServer9.xx版本下完成的，先后对采用SBDD策略和不采用该略的CSU一 YunLu2003仿真球队作了长时间的训练，训练结果表明，SBDD策略是可行有效的。为了减少比赛随机性对结果的影响，我们取同一支球队作为对抗球队，表4-1中给出了部分统计的对比数据，用来说明SBDD策略的采用对比赛结果的影响。表 4一 1 S BD 策 略 的 采 用 时 比赛 结 果 的 影 响
由表 4-1可以看出应用SBDD策略后，球在对方半场的平均时间比提高了25.5%，进球机会有了明显增加。
4.2.3 基于SBD策略的后卫防守模型
将防 守 型 SBD策略应用在后卫防守工作中，并取d一l.就是基于SBD策略的后卫防守模型的核心思想。上文提到在SBDD策略中，若d的取值过大，可能引起振荡，但由于后卫的战略位置比较靠近球门，他们断球后如果不迅速作出判断很容易被对方球员再次夺得控球权，另外在球员其它技能水平不高(如传球、带球)的情况下，即使判断及时，也可能在下一步动作中使我方球队失去控球权.因此，当后卫控球后只采用SBDD策略不仅可以缩短决策选择的时间，还能够弥补球队某些技能上的不足。而且通过实际比赛发现，后卫对SBDD策略采用度的大小对整个比赛振荡性的影响不是很明显。SBDD策略应用的前提是球员首先得到控球权，因此在后卫的防守过程中需要具有较强的断球技能。
4.3 小结
本章内容主要从智能体局部合作的角度出发，研究了后刃.的防守模型。在对己有防守模型分析比较的基础上，提出了基于SBD策略的后卫防守模型，这种防守模型打破了传统防守策略被动性的特点。基于SBD策略的后卫防守模型，主要解决了后卫断球以后的防守问题，采用这种防守方式的仿真球队，大大减小了门前危机，从而有效缓解了守门员的防守压力。SBD策略是后卫防守模型的核心，这是CSU YunLu2003的研究者在大量仿真实验的基础上提出的新思想，这个策略具有很强的适应性和可扩展性，能够有效瓦解对手有组织的协作。
第五章 总结与展望
5.1 论文总结
通过论文的写作不仅熟悉了整个RoboCup仿真足球机器人系统的设计和开发流程，而且对MAS系统中多智能体的合作、协调和对抗等方面己有了较深的认识。在对RoboCup仿真球队高层策略的研究过程中，论文提出一套可行、有效的防守策略，并将其理论化、系统化，其主要研究工作有:(1)将阵形引入到仿真比赛中，可以对多智能体之间的协调起到重要的作用。不同的阵形可以用在不同的比赛阶段或起到不同的攻防作用。防守型的阵形能够从整体上提高球队的防守水平，基于这一点文中提出了基于阵形变换的防守模型。主要研究了防守阵形的采样方法和动态变换算法，并研究了案例学习在阵形采用中的应用。该模型突破了单凭直接经验设置阵形因子的方式，将机器学习的方法应用到阵形设计中，在很大程度上降低了经验参数对阵形的影响。另外，在阵形变换上，该模型没有沿袭以攻防阵形转换为主的阵形变换方法，而是将防守分成积极防守和消极防守两个阶段，阵形转换工作在两种防守阵形之间进行。这种阵形动态变换方式加强了防守的力度，显著提高了球队的整体防守性能。
(2)在研究智能体局部合作的过程中，论文提出了反协作的SBD策略思想，并将该策略应用到后卫的防守工作中。在已有的后卫防守模型中，所采取的策略都是基于传统意义上的防守，研究的是在对方球员控球时本方球员应如何行动的问题，这类防守具有很大的被动性。而基于SBD策略的后卫防守模型，所采取的是一种积极的防守方法，主要解决了后卫断球以后的防守问题。该模型简单有效，在比赛过程中能够瓦解对手有组织的协作，从而大大减小了门前危机，并能有效缓解守门员的防守压 力。而且该模型对球队的底层技术要求不是很高，具有较强的适应性。(3)基于防线的守门员跑位模式是目前较为成熟的守门员防守方法，利用这种方法能够取得较好的防守性能，但必须处理好守门员体力消耗大的问题和足球越过防线的情况。论文在对基于防线的守门员跑位模式进行研究和分析的基础上，用设置临界线的方法解决了守门员体力消耗问题，并提出了可变防线的思想，研究了平行可变防线和交叉可变防线两种方法。可变防线的守门员防守策略打破了一条防线的限制，能够有效防止对手带球穿越防线，从而更好地发挥了守门员的防守作用。
为了将防守模型应用到CSU-YunLu2003中，在实验过程中还研究了CVs并行版本系统的使用方法和Linux操作系统的管理及其环境下的编程思想。
5.2 后期工作展望
机器人足球比赛作为一项集技术与竞技于一体的项目，为机器人学和人工智能的研究提供了良好的平台，越来越多的科研单位和院校参与到了足球机器人的研究与开发中，因此，应该继续我们在这方面的研究，并应不断深入。
论文所作的工作只是RoboCup仿真机器人中的一部分，在此基础上，还有很多工作有待完成。进一步的研究工作主要包括:(I)加强对阵形采样方法的研究，并寻求Q学习和遗传算法在阵形训练中的应用方法。加强对在线学习的研究，使Agent能够通过自身的学习能力进行阵形变换。
(2)进一步研究后卫之间的合作。在SBD策略方面，除了继续加强其在防守方面的研究，还要寻求更多的应用前景.(3)在对守门员防守模型的研究中，要继续在可变防线上的研究工作，并能够将一些成熟的人工智能方法逐步应用到参数设置和防线变换中。
(4)加强对RoboCup仿真球队其它高层策略的研究，进一步提高队伍的综合实力。
参考文献
[1] 薛宏涛、叶媛媛、沈林成、常文森.多智能体系统体系结构及协调机制研究综述[J].机器人.2001,23(1):85—89 [2] 洪炳熔、刘新宇、王月海.基于多智能体系统的机器人足球比赛[J].中南大学学报.2000,31(专辑):47—50 [3] 徐心和、佟国峰、机器人.足球比赛是推动机器人技术基础研究的舞台[J].中南大学学报.2000,31(专辑):483—486 [4] 曹卫华、桂卫华、吴敏、蔡自兴.足球机器人系统中人工智能的应用[J].中南大学学报.2000, 31(专辑):494—496 [5] 陈小平.国际机器人足球(RoboCup)最新进展[J].机器人技术与应用.2001,(1):25—28 [6] 徐心和.足球机器人六步推理模型研究[Ａ].机器人足球研讨班论文集[Ｃ].1998.42-46 [7] 傅京孙、蔡自兴、徐光佑.人工智能及其应用[Ｍ].北京:清华大学出版社.1988 [8] Kim J H, Shim H S.A cooperative multi-agent system and real time application to robot soccer[A].Proc of IEEE Int Conf on Robotics and Automation[C].Albuquerque.1997.638-643 [9] Fujisawa K, Hayakawa S, Aoki T.Real time search for autonomous mobile robot using the framework of anytime algorithm[A].Proc ofthe Fourth Int Symp on Artifical Life and Robotics(AROB 4th,99)[c].Japan.1999.291-296
[10]陈建中.支持协商的面向Agent程序设计方法研究:[博士学位论文].吉林:吉林 大 学，1998 [11]胡舜耕，张莉，钟义信.多Agent系统的理论、技术及其应用[J].计算机科学，1 99 9.2 6(9):2 0-24 [12]张波，蔡庆生，陈小平等.基于智能团队的RoboCup仿真球队[J] Jun 28--July2 ,200 0, Hefei, P.R.China.[13]李实，徐旭明，叶棒，孙增沂.机器人足球仿真比赛的Server模型[J].系统仿真 学 报，Vol.12N o.2,March,2 000 [14]李实，徐旭明，叶棒，孙增沂，综述:国际机器人足球比赛及其相关技术[J].机 器 人ROBOT,2 000,9(22):4 20426 [15]彭军，吴敏，曹卫华.RoboCup机器人足球仿真比赛的关键技术[Jl.计算机1程，第 30卷第4期:49^-50,2 004.2 [16] 孙增忻.机器人足球中的协作[Jl.第四届全球智能与自动化大会论文，2002.469-473，中国上海
[17]陈世福，陈兆乾.人工智能与知识工程[M].南京:南京大学出版社，1997.12 [18]马光伟，徐晋晖，石纯一Agent思维状态模型[J].软件学报，1999, 10(4):34 2^ 34 8 [19]王文凤，彭军.多层结构在RoboCup仿真球队中的应用〔J].计算机仿真，第21 卷 第 3期:88^-90,2 004.3 [20] 陆汝铃.人1智能[M].北京:科学出版社，1996.8 71-883 [21] 陈志涌等.精通MATLAB5.3[M].北京:北京航空航天大学出版社，2002.8 227-243 [22]件博.multi-agent协作模型及其在RoboCup中的应用:〔硕士学位论文l.长沙: 中南 大学，2003 [23]张晓勇，彭军.RoboCup中传球策略的实现[J].计算机工程，已录用，于2005 年 1月发表
[24」彭军，王文凤，张晓勇.SBD策略在多智能体协作中的应用研究〔Jl.计算机工 程，已录用，于2005年3月发表
[25]石纯一，黄昌宁等.人工智能原理[M].北京:清华大学出版社，1993.185-236 27
附录一:后卫队员状态自动机
//////////初始化程序 #include “stdafx.h” #include “CActionTranslator.h” #include “output.h” #include #include #include
using namespace zealot;/* * 类 CActionTranslator 的静态成员初始化 */ const char CActionTranslator::ROLE_NAME[][MAX_ROLE_NAME_SIZE] = { “VANGUARD”, “GOALIE”, “DEFENCE_MAN”, “KICK_MAN”，“WALK_MAN”, “AVOIDER”, };
const char CActionTranslator::ACTION_NAME [][MAX_STATUS_NAME_SIZE] = { “WALK”，“ACCESS_BALL”, “FACE_BALL”, “STRAIGHT_TOUCH_BALL”, “TOUCH_BALL”, “DRIBBLE”, “KICK”, “STOP”, “SEARCH_BALL”, “AIM”, 28
“RETURN_GOAL”, “SHUT_ANGLE”, “DEFENCE_GOAL”, “ALERT”，“DEFENCE”，“RETURN_POS”, “PATROL”，“AVOID”, };/** * CActionTranslator::CActionTranslator()构造函数 * * 参数: * v_Role--机器人的角色 * 返回值: * 无 */ CActionTranslator::CActionTranslator(int v_RoleIdx){ m_Role =(ROLE)v_RoleIdx;
InitAction();} /** * CActionTranslator::~CActionTranslator()析构函数 * * 参数: * 无 * 返回值: * 无 */ CActionTranslator::~CActionTranslator(){ } 29
/** * CActionTranslator::Action()得到机器人的当前状态 * * 参数: * 无 * 返回值: * 机器人的当前状态 */ CActionTranslator::ACTION CActionTranslator::Action()const { return m_Action;} /** * CActionTranslator::ActionName()得到机器人的状态名(用于调试输出)* * 参数: * 无 * 返回值: * 机器人的当前状态名 */ const char* CActionTranslator::ActionName()const { return ACTION_NAME[m_Action];} /** * CActionTranslator::RoleName()得到机器人的角色名(用于调试输出)* * 参数: * 无 * 返回值: * 机器人的角色名 */ const char* CActionTranslator::RoleName()const { return ROLE_NAME[m_Role];} 30
/** * CActionTranslator::ActionCounter()得到机器人的状态计数 * 也就是机器人处于当前状态的决策周期数 * * 参数: * 无 * 返回值: * 状态计数 */ int CActionTranslator::ActionCounter()const { return m_ActionCounter;} /** * CActionTranslator::InitAction()根据机器人角色初始化 * 机器人的状态 * * 参数: * 无 * 返回值: * 机器人的当前(初始)状态 */ CActionTranslator::ACTION CActionTranslator::InitAction(){ /* 根据机器人的角色确定机器人的初始状态 */ switch(m_Role){ case VANGUARD: // 前锋的初始状态是 SEARCH_BALL m_Action = SEARCH_BALL;break;
case GOALIE: // 守门员的初始状态是 SHUT_ANGLE m_Action = SHUT_ANGLE;// m_Action = ALERT;break;
case DEFENCE_MAN: // 后卫的初始状态是 RETURN_POS m_Action = DEFENCE;31
break;
case KICK_MAN: // 助攻的初始状态是 RETURN_POS m_Action = RETURN_POS;break;
case WALK_MAN: // 不依赖视觉反馈, 走一套确定的动作 m_Action = WALK;break;
case AVOIDER: // 避障人员的状态一直是壁障 m_Action = AVOID;break;}
#ifdef CONSOLE_OUTPUT printf(“Role: %sn”, ROLE_NAME[m_Role]);printf(“Action Initialize to %sn”, ACTION_NAME[m_Action]);#endif // CONSOLE_OUTPUT
#ifdef WIN_OUTPUT pZealotDlg->m_editAction.SetWindowText(ACTION_NAME[m_Action]);#endif // WIN_OUTPUT
m_ActionCounter = 0;// 清零状态计数器
return m_Action;} /** * CActionTranslator::TranslateAction()根据视觉信息和机器人当前速度 * 进行状态跃迁, 并返回机器人的当前状态 * * 参数: * v_Memory--机器人记忆, 内含视觉信息 * v_Speed--机器人的当前速度 * 返回值: * 机器人的当前状态 */ CActionTranslator::ACTION CActionTranslator::TranslateAction 32
(const CMemory& v_Memory, const CSpeed& v_Speed){ char msg[20];
ACTION last_action = m_Action;
/* 根据机器人在球队中的角色采用不同的状态自动机, 来控制状态的跃迁 */ switch(m_Role){ case VANGUARD: VanguardAction(v_Memory, v_Speed);break;
case GOALIE: GoalieAction(v_Memory, v_Speed);break;
case DEFENCE_MAN: DefenceManAction(v_Memory, v_Speed);break;
case KICK_MAN: KickManAction(v_Memory, v_Speed);break;
case WALK_MAN: break;
case AVOIDER: break;
default: sprintf(msg, “Unknown ROLE : %d”, m_Role);ReportError(msg);break;}
if(m_Action == last_action){ m_ActionCounter++;// 累加状态计数器
} else { m_ActionCounter = 0;// 清零状态计数器
#ifdef CONSOLE_OUTPUT printf(“Action changed to %sn”, ACTION_NAME[m_Action]);#endif // CONSOLE_OUTPUT
#ifdef WIN_OUTPUT pZealotDlg->m_editAction.SetWindowText(ACTION_NAME[m_Action]);#endif // WIN_OUTPUT } return m_Action;} /** * CActionTranslator::VanguardAction()前锋的决策自动机 * * 参数: * v_Memory--机器人记忆, 内含视觉信息 * v_Speed--机器人的当前速度 * 返回值: * 无 */ void CActionTranslator::VanguardAction(const CMemory& v_Memory, const CSpeed& v_Speed){ static int kick_counter = 0;static const int NEARBY_DISTANCE = 50;// 距离球多远时停车, 进入该距离机器人将停车
static const int DRIBBLE_DISTANCE = 10;// 距离球多远时带球
static const int STOP_SPEED = 20;// 停车速度, 速度达到多少时算静止
static const float FACE_ANGLE = CVector2d::PI / 10;// 选择是否正对着靠近球的阈值角度
static const float KICK_ANGLE = CVector2d::PI / 4;// 带球时的射门条件(角度)static const int KICK_DISTANCE = 200;// 带球时的射门条件(距离)34
static const int KICK_TERM = 10;// 击球周期 CVector2d ball = v_Memory.Position(CSnapshot::BALL);// 球的位置 CVector2d enemy_goal = v_Memory.Position(CSnapshot::ENEMY_GOAL);// 对方球门位置
/**后卫队员的决策自动机 * CActionTranslator::DefenceManAction()后卫队员的决策自动机 * * 参数: * v_Memory--机器人记忆, 内含视觉信息 * v_Speed--机器人的当前速度 * 返回值: * 无 */ void CActionTranslator::DefenceManAction(const CMemory& v_Memory, const CSpeed& v_Speed){ static const int FIGHT_OUT_DISTANCE = 150;// 出击距离(距球多远时出击)
CVector2d ball = v_Memory.Position(CSnapshot::BALL);// 球的位置
/* 后卫的状态机 */ switch(m_Action){ case DEFENCE: // 处于待命状态时
if(ball.Valid()&& ball.Norm()
case ACCESS_BALL: /* 不再发生状态跳转 */ break;} } 35
附录二 :论文
Local Multiresolution Path Planning_
Sven Behnke
International Computer Science Institute
Berkeley, CA, 94704, USA behnke@icsi.berkeley.edu Abstract.Grid-based methods for finding cost optimal paths are popular because oft heir flexibility and simple implementation.However, their computational complexity becomes unfeasible for real-time path planning ifthe resolution of the grid is high.These methods aume complete knowledge about the world, but in dynamic environments where sensing is done on board the robot, le is known about far-away obstacles than about the ones in close proximity.The paper proposes to utilize this observation by employing a grid of variable resolution.The resolution is high next to the robot and becomes lower with increasing distance.This results in huge savings in computational costs while the initial parts ofthe paths are still planned with high accuracy.1 Introduction Path planning is an important subtask of the robot navigation problem, which is to find a path from a start configuration to a target state and to traverse it without collision.The navigation problem can be decomposed into three subtasks: mapping and modeling the environment, path planning, and path traversal with collision avoidance.Manya pproaches to path planning have been described in the literature [7, 8].Theyca n be grouped into local and global methods.Local path planning methods do not attempt to solve the problem in its full generality, but use only the information available at the moving robot to determine the next motion command.One well known local path planning technique is the potential field method [6].Here, the robot follows the gradient of a force field.The field is generated bya ttractive potentials from a start position towards a target and by repulsive potentials that point awayf rom obstacles.The potential field method has a low computational load and generates smooth paths that staya way from obstacles.However, the greedygrad ient descent mayget trapped in local minima.It is hence most useful in environments where local minima are unlikely.Furthermore, it can be used for fast reactive obstacle avoidance.In contrast, global methods aume complete knowledge about the world.The frequentlyrel y on the concept of free space, the configurations the robot _ This work was supported by a fellowship within the postdoc program of the German Academic Exchange Service(DAAD).36
can take without collision [9].It is convenient to shrink the robot to a point while growing the obstacles accordinglyto obtain the free space.Roadmap path planning methods inscribe a graph into the free space that contains all poible paths.For instance, a roadmap defined bya visibility graph [10] can be used to find the shortest path around polygonal obstacles.Another poibilityto define a roadmap is to use Voronoi borders [11] as graph edges in order to find a path that stays far away from obstacles.To rapidly explore high-dimensional configuration spaces planners have been proposed that randomlysa mple configurations and connect samples in free space by simple local paths, therebycr eating probabilistic roadmaps [5].One disadvantage of these methods is that onlya binaryr epresentation(occupied/free)of the configuration space is poible.Another cla of global planning methods decompose the free space into cells.Exact cell decomposition results in cells of different simple shapes as required by the shape of obstacles.Approximate cell decomposition methods use predetermined cell shapes, sizes, and positions to approximate the free space [1].Popular approximate cell decompositions include uniform coverage with square cells and quadtree representations [4] that use smaller cells next to the obstacle borders.Once the decomposition is determined, dynamic programming can be used to find an optimal path.This requires to fill out a data structure, e.g.a multidimensional table, that contains solutions for all poible subproblems.If the resolution of a decomposition is high or the state space has manydimensio ns this can still be computationallydema nding.The computational efficiencyo f path planning is eential for online-problems [2], where paths are planned and executed in real time, for on board planning, where the computational resources are limited, and for planning in dynamic environments, where frequent replanning is required.All three of the above constraints are present in manyl eagues of the RoboCup competition.On the other hand, in dynamic environments a detailed path from the start to the target has little chance of execution.Obstacles move unexpectedlyas the robot traverses the path and hence continuous replanning is required.Furthermore, due to limited local sensing capabilities, far-awayo bstacles can be determined onlywith reduced accuracy.These observations motivate the local multiresolution path planning method proposed in this paper.The idea is to use high resolution to represent the configuration space in close proximityto the robot and to lower the resolution with increasing distance from the robot.This concentrates the planning resources to the begin of the path, the part that must be traversed first and where the information about obstacles is most reliable.While the computational load is reduced dramatically, the immediate movement of the robot can still be planned with high accuracy.The paper is organized as follows.The next section describes grid-based path planning and details its extension to the multiresolutional case.In Section 3, the traversal of planned paths and the effects of the initial robot motion are covered.The paper concludes with a discuion of the experimental results and indicates poibilities for future work.37
PlanPath(target, obstacles, N){ grid = eval = ClearGrid();q = InitPriorityQueue();while(!q.empty()){ p = q.pop();if(target == p)return previous;for(n∈ N(p)){ if(eval(n)== 0)best = ∞;else best = eval(n);new = p.cost + grid(p)·n.l0 + getGrid(n, obstacles, grid)·n.l1;if(new
of a fixed component, which represents the radius of the obstacle ro plus the radius of the robot rr, and a variable component rd that increases linearly with distance from the grid center.The far-awayob stacles are modeled larger, because their position can be sensed with le accuracyf rom the perspective of the robot and because theym ight move before the robot gets close to them.Each obstacle is also characterized bya height h is inverselyp roportional to the squared radius to keep its integral constant.The cost increase of a grid cell that is caused bya n obstacle depends on their distance.It is constant if the distance is smaller than the radius and decreases linearlyto zero at three times the radius.To compute the cost of a grid cell, the contributions from all obstacles are added to a uniform base cost.The cost function is a simple and flexible wayto expre uncertainty.Obstacles with noncircular shapes could be included into the cost function in an analogous way.2.3 Non-Uniform Resolution It is not necearyt o represent the entire grid with a high uniform resolution.Since far-awayob stacles cover a larger area, a coarser resolution suffices there to approximate them.This is illustrated in Figure 2(b).Here, the resolution is high in the center of the grid and decreases towards the outside.This corresponds to the situation shown in Figure 2(c).Multiple low-resolution grids of size M ×M are stacked concentrically.The inner part of a gridis not used, but the next grid level is placed there, until the highest resolutionis reached.To cover the same area as a uniform N ×N grid with the same inner resolution, only K = log2(N/M)+ 1 levels of size M × M are needed.If N is large compared to M, this lowers the number of grid cells substantially.In the following experiments, I use N = 256, M = 16, and K = 5.Hence, the flat grid has 64 times as manycel ls as the multiresolutional grid.The connectivitywithin cells of the same level of this multiresolutional hierarchyi s set to the 8-neighborhood.Care must be taken at the borders between resolution levels to connect the neighboring cells.Figure 3 illustrates the connectivitythat is used for the experiments.Except for the corners, each high resolution cell connects to two adjacent low resolution cells and each low resolution cell connects to four high resolution cells.2.4 Heuristics The A∗ algorithm [3] is an efficient and well studied best-first search algorithm.It uses a heuristic function to guide the search.This function is an optimistic estimate of a path’s total cost.Since each grid cell has at least the base cost, the remaining part of the path from a grid point to the target cannot be le expansive than the Euclidean target distance weighted bythe base cost.Hence, the sum of the accumulated cost of the best path to a grid point plus this heuristics can be used to determine the expansion order.As can be seen in
Figure 4, the use of this heuristics can substantiallylo wer the number of visited grid cells.The altered expansion order mayal ter the path found onlyi f two paths have the same costs.The figure also compares the algorithm for the flat and the multiresolutional grid representation.One can observe that the produced paths are verysimilar.39
In particular, the start of the multiresolutional path is as detailed as the path produced using the flat grid.2.5 Runtime
The different cell numbers between the flat and the multiresolutional grid result in different runtimes.Figure 5 displays how this difference grows with the problem size.The runtimes represent the measured average running time of the path planner to random targets with random obstacles.A 1GHz Athlon proceor has been used for the measurement.The algorithm has been implemented in C++.At the leftmost data point, where K = 1 and N = M = 16, both representations are identical.As N gets larger, K is adjusted accordingly.One can observe that the runtime grows approximatelyexp onential with K when a single resolution is used and grows, after some cache effects, approximatelylinear when multiple resolutions are used.This corresponds well to the growth of the cell numbers.For K = 8 and N = 2048, the flat search needs on average 4.55s while the multiresolutional search needs only4.70ms on average.3 Continuous Planning and Execution In a dynamic environment, a planned path cannot simply be executed.Since the obstacles move, the plan must be updated as the robot follows its trajectory.Furthermore, in order to make consecutive plans compatible, the initial robot motion must be taken into account.3.1 Initial Condition One simple wayt o account for the initial velocity of the robot is to place an additional obstacle behind it, as shown in Figure 6.This obstacle favors paths that initiallyco ntinue in a similar direction the robot is already moving.The larger the robot’s initial velocity, the more severe a sudden change in direction would be and hence the more pronounced this obstacle must be.3.2 Partial Execution and Replanning Figure 7 illustrates how two different initial conditions lead to two different paths.The figure also shows, how the robot generates a trajectoryb y moving along the initial segment of the path.The path is continuouslyu pdated.As the robot comes closer to initiallyfa r-away obstacles, their radius decreases, since their position can now be determined with greater precision and theyare le likelyt o move.Hence, the robot paes these obstacles closer than originally planned.Figure 8 shows some additional trajectories that have been generated in an environment with more obstacles.The trajectories are smooth, relativelyshort, and staya wayf rom obstacles.Hence, they are suitable to reach the target fast while avoiding the chance of collisions.4 Conclusions The paper proposed a local multidimensional path planning algorithm.In contrast to quadtree algoritms [4] that focus the computational reources at the obstacle borders, this algorithm represents the configuration space next to the robot with higher resolution than far-awayfr om it.This leads to the use of fewer grid cells, as compared to a representation that is based on a uniform grid.These savings result in substantiallylo wer runtimes.40
The coarse approximation of far-awayob stacles was motivated by the limited precision of robot-based sensing for far-awayob jects and by the larger obstacle movements that are poible before the robot comes close to them.If these conditions are met, the generated paths have simular qualityas the ones generated using a grid of uniformlyhig h resolution.Since the runtime of the multiresolutional path planner is verysho rt, it can be used for continuous replanning.This is not wasteful, since onlythe initial part of the path that is executed immediatelya fter planning is planned in detail.An example with a two-dimensional configuration space has been presented.The generated trajectories facilitated the fast movement towards the target while at the same time minimizing the chances of collisions.So far, the obstacles were static and the kinematics of the robot has not been included in the configuration space.Since the running time of the planner is only a few milliseconds long, it would be feasible to increase the dimensionality of the configuration space and still replan at a high rate.One could e.g.explicitly model time or the orientation of the robot.This will be subject to future research.References 1.R.Brooks and T.Lozano-P′erez.A subdivision algorithm in configuration space for findpath with rotation.In Proceedings of the 8th International Conference on Artificial Intelligence(ICAI), pages 799–806, 1983.2.James Bruce and Maria Manuela Veloso.Real-time randomized path planning for robot navigation.In Proceedings of the 2002 IEEE/RSJ International Conference on Intelligent Robots and Systems(IROS ’02), October 2002.3.P.E.Hart, N.J.Nilon, and B.Raphael.A formal basis for the heuristic determination ofm inimum cost paths in graphs.IEEE Transactions on Systems Science and Cybernetics, SSC-4(2):100–107, 1968.4.S.Kambhampati and L.S.Davis.Multiresolution path planning for mobile robots.IEEE Journal of Robotics and Automation, RA-2(3):135–145, 1986.5.L.Kavraki, P.Svestka, J.C.Latombe, and M.Overmars.Probabilistic road maps for path planning in high-dimensional configuration spaces.IEEE Transactions on Robotics and Automation, 12(4):566–580, 1996.6.O.Khatib.Real-time obstacle avoidance for manipulators and mobile robots.International Journal of Robotic Research, 5(1):90–98, 1986.7.J.-C.Latombe.Robot Motion Planning.Kluwer Academic Publishers, Boston, MA, 1991.8.J.-C.Latombe.Motion planning: A journey ofrob ots, molecules, digital actors, and other artifacts.International Journal of Robotics Research, 18(11):1119–1128, 1999.9.T.Lozano-P′erez.Spatial planning: A configuration space approach.IEEE Transactions on Computers, C-32(2):108–120, 1983.10.N.J.Nilon.A mobile automaton: An application ofart ificial intelligence techniques.In Proceedings of the 1st International Joint Conference on Artificial Intelligence, pages 509–520, Washington, DC, 1969.11.C.O’Dunlaing and C.K.Yap.A ’retraction’ method for planning the motion of a disc.Journal of Algorithms, 6:104–111, 1986.41
致谢
光阴似箭，岁月如梭，转眼间大学生活就要结束了。在论文完成、即将答辩、毕业之际，谨向培养我的学校和那些曾给予我关怀、帮助的所有人表示深深的谢意。
首先，我要忠心感谢我的导师李铁军老师。在我作论文期间，李老师不仅为我提供了很好的学习和研究环境，而且为我提供了许多学术上的具体指导，使我受益匪浅，论文的研究工作更是在彭老师的精心指导下完成的。李老师在学习、生活中也给予了我许多教诲与启迪。在论文的选题、开题直至定稿完成的整个过程中，老师都付出了大量的心血和无私的劳动。导师对我的关心、帮助和激励，我将永远铭记在心，他严谨的治学态度、勤勉的工作作风、谦逊宽厚的为人水远值得我敬仰和学习。在此我再一次向他表达深深的敬意和感激。
感谢计算机科学与工程学院的几位老师和同学们对机器人足球课题组的关心与支持。他们为我的论文提供了许多宝贵的修改意见和建议。
感谢同课题组的崔金生，张继军，石绍绅等同学，我论文中的很多研究工作都是和他们合作完成的，得到了他们的许多启发和帮助。在我论文的写作过程中，沈建波，蒋林等几位同学也提出了很多中肯的意见。我能顺利地完成论文，与他们的热心帮助是分不开的。
感谢同实验室的王耀羚，张丽等同学，他们在学习和工作中给我很多鼓励和支持。在我大学期间他们对我的生活和学习给予了很多帮助，这些深厚友情是难以忘怀的。
随着我学位论文的完成，我即将告别大学生活，这段宝贵的经历是我一生都难以忘记的。在我求学的这些年里，我的家人一直是我的坚实支柱。在这里我要特别感谢亲人们多年来对我的关爱、理解和勉励。
最后，再一次忠心地感谢所有曾经关心和帮助过我的人们。
