【《基于用图的最短路径算法的AGV调度系统设计》22000字】

基于用图的最短路径算法的AGV调度系统设计摘要21世纪，全球制造业将要进入一个新的阶段，企业的主导模式页向着敏捷制造转变。抓住市场机遇，开发出创新的产品将是企业在激烈的竞争中脱颖而出的必要手段。想要降低生产成本对生产批量的依赖关系，发展敏捷制造的装备是重点。繁重制造装备所具有的可编程、可重组以及快速响应能力使得在进行小批量生产的时候，可以实现接近中、大批量生产的生产效率。由于机器人的可自主规划、可编程、可协调作业和基于传感器控制等特点，它将成为可重组的敏捷制造生产装备及系统的重要组成部分，为传统制造企业向敏捷制造企业跨越发展提供重要的技术支持。自动导引车（AutomatedGuidedVehicle，简称AGV），指的是车身安装有自动导航牵引系统、沿着既定的导航路线或通过视觉导航等方式运动并具有装卸、搬运货物等功能的无人驾驶车辆（机器人）。在最近的这些年，AGV的发展在汽车工业、港口运输、仓储物流等技术领域取得了跨越式进展。由多台AGV组成的物流系统可以在具有各种预设路径的仓储环境中无冲突地运行，然而在大多数制造车间里，AGV的运行路径不能自由的铺设，并且还要受到空间和场地的限制，因此实际的环境对多AGV系统是一个非常大的挑战。在仓储物流的整个过程中，货物的装卸、运输等环节耗费了大量的时间，占据了整个物流过程总耗时的绝大部分，这就导致物料运输成本增加。而AGV车辆（机器人）路径规划方法，对改善物流运输系统结构、降低物流运输成本、提升系统运行效率起着重要的作用，因此在仓储物流中具有巨大的应用价值。综合以上的叙述，我们知道，在仓库里完成搬运任务的AGV车辆的调度便是我们需要解决的问题。因此，本文提出一种使用图的最短路径算法以求取AGV车辆最适路径的方法，并以此为基础设计出了一个AGV调度系统。关键词：自动导引车、仓储物流、AGV调度、路径规划目录1绪论 61.1AGV及其调度问题 61.1.1AGV的定义 61.1.2AGV调度系统定义 71.1.3AGV调度问题 71.2研究意义 81.3发展现状 101.4AGV的应用 111.5研究内容 131.6研究方法 152相关算法理论 162.1Dijkstra算法 162.2经典A*算法 163系统设计 173.1AGV车辆（机器人）调度系统工作流程 173.2路径规划方法 193.2.1采用迪杰斯特拉（dijkstra）算法构造的AGV调度系统 193.2.2采用A*算法构造的AGV调度系统 253.2两种算法的比较 253.3工作空间模型建立方法 263.4使用经典A*算法求取最短路径 284算法设计与编写 304.1软件及开发环境介绍 304.2C++语言介绍 304.2.1C++语言的起源 304.2.2C++的特点 314.3使用C++进行系统设计 314.3.1运行C++程序的步骤 314.3.2代码说明 325总结 55参考文献 561绪论制造业作为国民经济的主体，是各个国家综合国力的象征。随着世界经济一体化程度的不断扩增，国际工业市场上的竞争也愈演愈烈，甲方们对产品的功能要求也越来越多样化。长尾理论从产品的角度，重点对长尾的集群价值与产品供应的意义做出说明。由此，在工业4.0这个新时代，创生了全新的生产模式——个性化量产。然而，当前制造企业普遍应用的生产模式和生产工具已经跟不上经济发展高速增长的脚步。为此，美国推进“再工业化”计划，德国提出“工业4.0”的计划，韩国制定了“制造业革新3.0”规划，我国也根据国情提出“中国制造2025”战略。在20世纪80年代初，还处于发展初期的AGV技术更多的是应用在制造业的生产领域。传统的制造系统的物流运输部分一般来说是传送带和叉车构成的，这种运输方式的运输路径单一且效率低下。有相关研究显示，在传统制造业系统的生产过程中，用于加工制造的时间仅占整个工作阶段的不到十分之一，大部分的时间都用在货物的储存、装卸和运输等环节，因为这个原因，物料的运输成本大大增加，几乎占据了生产总成本的30%-50%。AGV车辆自动物流系统的出现可以说是改变了传统制造业的车间、仓储物流的结构，大幅度降低了生产成本，提高了企业仓储环节的工作效率。时间来到21世纪，人工智能技术、计算机图像处理技术、计算机集成制造技术和传感器融合技术的快速发展，推动着AGV物流技术继续向更深层次发展，AGV车辆的应用场景也越来越多样化。AGV车辆也逐渐从早先的物料搬运工具向着自动化、智能化分拣配送工具转变。特别是随着电子商务的飞速发展，以AGV技术为核心组成部分的物流自动化仓储系统不断得到强化。AGV智能仓储系统是综合了机电一体化技术、通信技术、自动控制技术、传感器技术和计算机技术等多种学科技术的产物。对于AGV智能仓储系统而言，路径规划的问题始终是AGV研发领域的核心问题之一。在目前市场竞争日益激烈的环境下，能够合理有效的为AGV规划出一条无碰撞，不仅可以提升企业生产自动化水平，也可以提高企业生产的效率。由此可见，AGV路径规划问题的研究具有深远的意义。1.1AGV及其调度问题1.1.1AGV的定义国家标准对AGV的定义是：AGV：装备有电磁或光学等自动导引装置，由计算机控制，主要移动方式为轮式移动，自带动力或动力转换装置，并且能够沿规定的导引路径自动行驶的运输工具，一般具有安全防护、移载等多种功能。用普通用户的视角来看，AGV可以理解为是一个可以完成装卸搬运货物的移动机器人，是仓储物流车间中的机器“搬运工”，把货物从A处运到B处，因此AGV的大部分研究也是包含在移动机器人领域内的。1.1.2AGV调度系统定义国家标准对AGV调度系统的定义是：调度系统：在上位控制系统中用于任务调度、车辆管理及交通管理的控制软件。对于单独一个AGV来说，其工作流程和工作原理其实并没有多么复杂。比如说机床要加工零件时，上位机电脑控制系统给AGV的调度控制中心发出请求命令，调度系统派出一台AGV车辆（机器人）前去把材料从仓库运送到机床。这个过程我们可以称之为一个“任务”，所以AGV的任务就是在货物存放区和目的地之间来回移动。在这个例子中，机床（用户）只是提出了需求（我在什么时间，什么地点，需要什么材料），至于选择哪一辆AGV运送零件原料，AGV该沿哪条路线运动，这些都是调度系统的工作。调度系统一旦为AGV指定好路径后，AGV上的车载控制器会根据指令完成具体的运动控制任务，例如速度保持在多少，遇到路口转向时轮子怎么转动等等。所以在一个完整的大系统中，AGV调度系统位于上层控制系统和底层控制系统的中间，其到管家的作用。但是对于多个AGV，调度问题的难度直接上升了一个量级，系统中AGV的数量越多，处理难度越大。因此，调度控制的算法设计便是AGV控制系统中最关键的技术。所以，即便目前市场上的主营AGV技术的公司有非常多家，但是能有自主研发调度技术的企业并没有多少，而能够真正把调度系统优化好、能够最高效率地利用AGV系统的企业更是凤毛麟角。实际应用中的AGV调度系统，其的功能通常包括：任务管理，车辆状态实时监控，路径规划，地图编辑，数据库查询等。1.1.3AGV调度问题在外行人眼中对于AGV调度系统这个概念，可能未必了解其中的工作原理，但对此光从字面上看也会产生一些感性的认识。如果此时你正在火车站或者飞机场里使用电脑浏览本文，那么你同时正在经历两种调度过程：大量的火车和飞机需要调度，与此同时你电脑里的操作系统也在对大量的任务进行调度。当很多事件同时发生，而且存在竞争时就需要调度了。如果只有一个事件发生，那么所有资源都由这个事件支配（火车可以在任何一条铁轨上跑），我们不需要调度；如果多个事件同时发生，但是没有竞争关系（美国的一列火车和中国的一列火车），我们也不需要调度，因为它们不会发生冲突。首先，我们应该能分辨一个问题是不是调度问题。假设工厂中只有一台AGV在工作，此时调度问题就退化成单纯的路径规划问题了。不需要考虑该将任务分配给哪台AGV，也不需要考虑在路口相遇时，谁先谁后。所以调度问题的前提是多个AGV共享路径网络，换言之是AGV之间存在资源（空间）争夺。就像马路上的车辆一样，都是赶时间前往各自的目的地，如果每个司机都只考虑自己而不考虑对方，那么后果大概就是大家都拥堵在一起，谁都别想走。所以，调度系统是非常有存在的必要的。多数情况下，调度系统需要统筹所有AGV的行为，它追求的不是某几个AGV的最适解决方案，而是要使整体的效率达到最高。我们可以设想一下，能不能做一款调度软件来调度一个城市里所有的车辆，让整体解是最优的。这个最优解一定存在，但是实际不可能有这种完美的解决方案的，有两个难点：首先，调度系统需要输入和存储非常巨量的信息，第二个问题是，调度问题的复杂程度随着其系统内控制的机器数量呈指数形式增加。若只有少数的几十辆车，还可以以现在计算机硬件以及设计合适的算法勉强解决，如果数量增加到成千上万辆车，那以现在的普通工程用计算机的CPU的算力，基本没有实现的可能。所以综合对以上问题的考量，我们在设计和解决AGV调度问题时需要根据实际情况做出取舍，合理利用工作环境中所能提供的条件，以达到一个尽量合理的解决方案。1.2研究意义在人口老龄化的大环境下，我国国内的人力成本不断增高，产业结构的进一步升级带来了非常大的压力，此外，还有一些行业因为技术水平的限制、工作环境恶劣等因素造成了严重的“招工难”现象。还有就是现今制造业的发展，随着科技水平不断地提高，现代工厂对生产力、鲁棒性的要求与以往不同日语，如今的社会对生产力的提高的有了迫切的需求。2015年二月，根据IFR发布的《2014年世界机器人统计数据报告》，预测到2017年，在中国的制造行业在加工制造以及装配车间等场所所使用的工业机器人的数量将由现有的16.2万台增加到42.8万台。由此可以推测出，到了2017年，工业机器人在中国的使用量将攀升到世界第一，制造企业自动化程度也会达到世界领先水平。然而，据学者统计，我国制造业的整体水平还是与发达国家存在着一定的差距，在车间仓储物流过程中运输效率比较低、运输成较高等。由此AGV技术应运而生。作为作为现代制造产业的一个新成员，AGV车辆可以根据工厂不同的生产需要、工艺流程、仓储要求等情况随时对工作做出调整，降低了车间里对工人的需求、组成了智能化物流系统、提高了鲁棒性、消除了传统物流的局限性。这样的系统自动化程度高、安全可靠、维修方便、与传统的输送带和传送线相比运行过程中无噪音无污染运行成本低廉等优点，AGV车辆自动运输系统在我国的烟草、汽车组装、制造业等方面有广大的发展前景。美国运输与物流协会（AST&L）对AGV的定义是这样的：AGV（AutomaticGuidedVehicle）是一种使用电力驱动的，以工控机（IPC—IndustrialPersonalComputer）作为逻辑核心，具备一台以上动力设备以及定位、寻径功能，能在预设的路径轨道中完成运输任务的物资输送装置。它的研究与发展涉及到计算机、自动化、信息传输、机械结构设计和软件编程等多个学科领域的知识，集机电一体化、光电子学、通信技术、自动化技术及计算机技术于一身的现代化仓储物流运输技术。在大型车间里如何正确进行对于AGV车辆（机器人）的系统调度这一重要相关技术研究课题，当前国外技术研究及其发展重点方向大多指的是将AGV车辆（机器人）在其行驶的运动过程中所可能存在的技术问题，对调度问题的关注并不多；国内针对AGV车辆或类似的相关技术课题研究大都集中在以机械臂为关注点的车间调度，而机械臂的工作方式仅仅是在工作台或者仓库这种工作环境中对物料的上下料操作，与AGV车辆（机器人）系统调度的关系不大。使用AGV车辆（机器人）智能物流系统可以非常高效地提高企业制造生产或仓储物流的工作效率以及仓储车间的自动化水平，而对AGV车辆（机器人）的调度则是整个运输系统中核心，起着协调系统中每一辆AGV车辆（机器人）之间的工作的作用。因为生产车间内工件以及物料的运输任务是由AGV车辆（机器人）执行，因此AGV车辆（机器人）的调度方案制定的合理可行性将会直接影响整个生产设备车间的实际工作效率,所以AGV车辆（机器人）的调度解决方案对于整个AGV车辆（机器人）的系统都有着十分重要的意义。本文是针对AGV车辆（机器人）调度存在的问题,结合实际的情况增加假设的条件对于车间生产制造控制系统的AGV调度方法进行了优化,对于车间制造工作效率的改善具有一定价值。AGV技术应用的意义有以下这些方面：（1）先进性：AGV技术的研究与发展涉及到计算机、自动化、信息传输、机械结构设计和软件编程等多个学科领域的知识，集机电一体化，光电子学，通信技术，自动化技术及计算机技术于一身。定位精准，自动化程度较高。（2）灵活性：AGV系统设备可以很便捷地与各类大型生产线、设备以及装配线、运输线等机械设备、仓储、工作台和多个RS/AS/出入口等多个大型作业管理平台设备进行相互配合。按照在企业实际操作过程中的各种应用情况和不同需求对其进行功能组合,以不同应用形式的设计方法对其进行功能组合,达到所需要设定的企业预期工作目标基本功能。以最大限度缩短物流周转周期、减低能源消耗、实现物料与加工物料与生产等的柔性对接，最大程度地提高生产效率。（3）可靠性：每时每刻AGV车辆（机器人）与主系统之间进行着信息数据的交换发生在AGV车辆（机器人）系统工作运行过程中，依附于后台设置好的数据库系统，调度系统能为AGV车辆（机器人）实际工作中遇到的各种突发情况快速有效的做出分析和判断，并迅速做出合理的调整，在消除人为因素干扰的情况下，充分保障了AGV车辆（机器人）作业过程中的可靠性，完成任务的及时性，数据信息的准确性。（4）独立性：在一些极端条件下，比如说没有其他系统或装置的支持，单独的AGV车辆（机器人）也可以以自身作为一个独立的系统，作为一个独立单元完成一些任务。（5）兼容性：相对于单个设备独立工作，AGV系统更善长于与其它系统如：调度系统、生产管理系统、监督管理系统等将这些功能紧密地结合在一起进行操作，这就说明AGV系统在设计上具有良好的兼容性和高度的适应能力。（6）安全性：作为无人驾驶的智能物流运输车辆。AGV车辆能够在一些不太适合于人类生活和工作的恶劣条件下，例如在高温、低辐射的场合里进行正常的运转。另外AGV车辆还具备了智能化的信息采集和分辨判别处理的自动控制功能和交通管理、应急刹车、安全防范、故障预警、多层次的警示等技术手段。1.3发展现状若一个系统中，仅仅包含一辆AGV，那么他的工作原理和控制流程并不复杂，但对于包含有多个AGV的调度系统，我们所需要考虑的问题就会变得非常复杂，AGV数量越多，难度越大。目前在国内市场上，在调度系统方面，市场上一些有核心技术的AGV企业会采用自己研发的调度系统，而对于另一部分没有核心技术的企业则会选择采购有调度系统开发成品的厂家合作，购买相关系统软件。对于自主研发的AGV调度系统，一方面是由于市场竞争的必要性，出色的软件及硬件实力的应用领域更能赢得别人的好感，也可以提升企业在市场上的竞争力，另一方面也可以减少在这方面用来采购的费用，内部技术升级和重复工作可以完成得更好。按照市场需求，目前在世界仓储机器人领域，已经有了实现上千数量级的调度系统。2018年菜鸟公司在无锡机器人仓中上线的AGV仓储物流系统中，已经实现了700多台AGV协同工作。与仓储AGV机器人不同的是，叉车AGV或者其他激光导航的重载AGV产品，因为应用情况相对复杂，且同一场景实际应用数量并不太多，多机协同作业技术难度大，一般的调度系统能调度的数量大概在几十台左右，上百台的并不多。目前规模最大的应该是科尔摩根NDC在英国某乳品企业中同时调度110多台激光叉车AGV，据了解，在叉车领域，科尔摩根NDC8经典AGV调度系统单个系统可以最大项目达到120台，目前其国内合作伙伴在轮胎行行业实际单个系统实施到50台左右。除了数量和规模需要进一步增加的问题之外，调度系统目前的应用还存在兼容性的问题，同一品牌的AGV车辆（机器人）用一个调度系统，但两家不同品牌的AGV要想在一个系统里兼容目前还很难实现，因此，需要推动相关接口规范与统一。中国移动机器人（AGV）产业联盟正在着手制定的《工业应用移动机器人数据通信接口规范》团体标准，就是在推动相关产品通信协议与接口规范化，据悉，该标准将在年内推出，未来将有助于调度系统的进一步优化。综合各方面因素，虽然自研调度系统有一定的好处，但因为技术门槛高、需要的投入也大，对于有些中小公司来说并不经济划算，因此它们会选择与专门的调度系统厂家合作。最开始，市场上大多是使用国外的调度系统，科尔摩根NDC占据了大部分的市场，不过伴随着国内AGV产业的不断发展，国产软件商也在不断精进技术，满足市场需要。表1-1：国内部分专业调度系统厂商及其产品公司名称发展现状上海宾通2017年成立，以机器人算法为核心，提供柔性制造与智慧物流系统软件和解决方案，其多机调度系统已经有了成熟的市场应用。深圳格局2016年成立，以技术为中心的创新型高科技公司。专注于移动机器人行业，为机器人行业集成商、设备商和终端客户提供专业性的软件解决方案、核心零部件和定制化服务。悦飞科技2013年成立，主要产品有AGV控制系统、AGV调度系统、WMS系统。凯钒科技2017年成立，产品包括AGV控制系统、WMS、WCS、MES、ERP等。中极智能2018年成立，专注于企业内部物流工业车辆的无人驾驶控制器、多智能体调度系统等。从上表可以看出，目前国内一些专门的调度系统厂商成立时间都并不久，一方面主要是因为此前国内整体的AGV产业都并不发达，专门的软件公司市场不大，另一方面则在于技术限制，与国外的差距过大，市场基本上处于被外企垄断阶段。但伴随着仓储机器人引爆国内市场，AGV的规模化应用对系统的大规模集群调度有了更高的要求，AGV厂商开始在调度系统方面下功夫，同时，市场的扩大也催生了一波专业的优质国产调度系统厂商。1.4AGV的应用AGV智能物流系统在我国的制造行业中，已经有了非常广泛的应用，主要用于仓储、加工制造、产品装配、物料分发等方面。（1）仓储业仓储行业是最早采用了AGV智能物流系统的行业。现如今，全世界大约有两千多座仓库使用了AGV车辆（机器人）系统进行仓储运输，在这些系统中大约使用了两万多台AGV车辆（机器人）。据一家研究开发机构透露，2000年海尔集团在投资建设智能型立体仓库时，使用了柔性AGV车辆（机器人）装卸系统。多辆AGV车辆（机器人）每天可以完成超过2万次的仓储和运输任务。其原因主要有两点：第一，货物运输需求在行业发展中的增长速度是非常快的，而人力运输方式一般货损率高，效率低。第二，传统的人工运输运营降低了仓库企业的自动化、信息化、智能化程度，难以对大量的仓储任务进行管理和信息反馈。（2）制造业AGV系统广泛应用于制造业生产线中。灵活的AGV系统由多辆AGV车辆（机器人）组成，可根据不同突发情况随时调整AGV车辆（机器人）运输路径、实际订单需求、生产流程、紧急程度等，增加系统的“鲁棒性”。随着企业的发展，技术企业的附加值和企业竞争中包含着决定性因素，技术越先进企业的利润越高，保有新技术的企业的利润越多，走上这条路的企业越多。某汽车企业研发中心的权威人士指出汽车制造业的未来发展蓝图是智能化、信息化、活性化、灵活化。AGV车辆（机器人）的出现将对未来制造商的发展起到很好的促进作用。（3）汽车装配美国通用汽车公司（GeneralMotorsCompany，GM）的汽车生产线中使用的AGV数量占整个公司所有的部件生产线的90%，欧洲各国将57%的AGV车辆（机器人）用于汽车组装线。要求对各加工环节之间的FMS物流效率高，AGV车辆（机器人）灵活的物流运输系统具有较好的鲁棒性可以供应的方案,根据对实际生产需求,AGV车辆（机器人）的轨道路径,通过编程系统途径改变分配执行运输任务的整个运输系统能够更好地达到预期目标。目前，国内部分汽车零部件组装流水线和发动机安装流水线专门适应AGV车辆（机器人）系统，汽车总装以及发动机、变速器等重要零部件的组装，取代了传统的流水线或流水带。AGV系统还可以通过调度方式，改变AGV车辆（机器人）路径轨道等，实现汽车组装过程中的混流作业以及定制生产等。AGV车辆（机器人）系统在其他领域也有广泛的应用。在军事领域，以AGV车辆（机器人）的自动驾驶为基础进行进一步改造，使其能够执行设置高放射性物质、拆除爆炸物等高风险任务。在胶片的生产过程中，AGV能在黑暗环境中正常地运送材料。AGV车辆（机器人）系统将从接收区接收的邮件运送到处理区，再由处理区运送到投递区。如图1-1即为AGV在不同行业中的应用。图1-1AGV车辆在各种工业环境中的应用1.5研究内容本次设计的AGV车辆（机器人）调度系统主要包括一下内容：（1）清晰的描述AGV车辆及其调度系统的定义、调度系统对AGV运行路径的规划方法；（2）了解AGV技术的发展历史、工作特点和AGV技术的应用范围；（3）研究AGV车辆的调度工作原理与其方法；（4）结合实际运行情况分析，绘制出仓储车间环境的模拟地图，在模拟地图的基础上使用算法求出AGV车辆的运行路径；（5）使用MicrosoftVisio软件绘制调度系统工作原理流程图，描述调度流程；（6）根据数据结构中，图的最短路径算法，对比每种解决方案的优缺点，结合实际应用中对此类问题已经存在的较为成熟的解决方案，选择A*算法作为本课题的核心研究内容；（7）建立假设模型，将课题描述和研究的问题简化，并以“路径最短原则”利用经典A*算法求出AGV小车的最优运行路径；（8）使用C++语言，针对设计已经好的路径规划算法进行代码编写并模拟运行。为了更好地实现对整个系统中每个AGV车辆（机器人）的自动化调度,例如在在仓储物流环境中铺设AGV车辆（机器人）行驶路径和轨道、搭建AGV车辆与上位操作系统之间的通讯和联接、处理在小车行驶过程中可能遇到的各类矛盾和冲突等一些问题的应用和解决，主要分为以下几种途径：1、规划路径路径设计规划主要是指在既定AGV车辆（机器人）的整个任务过程开始阶段到达任务起点以及任务结束到达终点后,在既定AGV车辆（机器人）的任务路径中按照一定的任务目标（包括例如行车时间最优、路径最优等）时间来对其车辆进行路径规划,进而为您量身选择一个相对合理的AGV车辆（机器人）行驶线路。2、任务调度所有的调度任务都是由作为主控制器的单元负责来进行调度。系统根据每一个综合生产工作车间的具体情况实际生产结构合理布局、生产的实际需要以及进行处理的生产工作现场环境等多种情况因素来对其进行科学决策和综合判断，然后将任务分配给合适的AGV车辆（机器人）。制定好合理可行的调度方案，调度系统可以对每个AGV车辆（机器人）的运行负载进行均衡来提高AGV车辆（机器人）的利用率并提高AGV车辆（机器人）系统完成物流的效率。3、处理冲突在实际的仓储物流搬运过程中，常常会出现一些突发状况，这些状况可能会导致AGV车辆（机器人）之间出现冲突，常见情况有以下三种：eq\o\ac(○,1)面向相撞图1-2小车面向相撞示意图此类情况可对小车运行的方向做出限制，例如设置单行道，或者在小车的核心代码中加入避障程序等措施以避免或消除此类冲突；eq\o\ac(○,2)追尾图1-3小车追尾示意图此类情况大多是因为AGV车辆在共用路径时，车辆间的速度没有协调好，可以在算法中加入“速度墙”以限制小车运行速度，在检测到路径中有运行中的AGV时，两台AGV（或多台）之间进行通讯交流，做出速度平衡，以此来避免或消除此类冲突；eq\o\ac(○,3)侧方相撞图1-4侧方相撞示意图这种冲突在包含多辆AGV车辆（机器人）的调度系统中出现的最多，我们可以设定“先到先行”原则，使通过历经相交节点的AGV车辆（机器人）遵循这个原则，形成类似于“交通管制”的红绿灯路口，这种方法是解决类似冲突比较常用的方法。1.6研究方法本文采用的研究方法主要是：1.6.1文献分析法。文献资料分析法是一种依照一定的国家科学技术研究发展目标或科研课题,通过对相关文献资料进行深入调查和分析搜集相关数据资料来进行整理和分析获取各种相关文献资料，从而全面、正确地深入认识和准确掌握必须深入研究的科学问题。查阅关于AGV车辆调度问题的算法解决方案，主要可以归结为图（graph）的最短路径算法。全面分析和总结AGV车辆（机器人）调度问题的解决方法以及现有市场上成熟的商用案例后，做出对本文所使用的算法的决定。1.6.2信息研究法信息研究法是广泛利用信息来研究系统功能的一种科学研究方法。美国数学家、通讯工程师、生理学家诺伯特·维纳（NorbertWiener）认为，客观世界有一种普遍的联系，即信息联系。当前，正处在“信息革命”的新时代，有大量的信息资源，可以开发利用。信息方法就是根据信息论、系统论、控制论的原理，通过对信息的收集、传递、加工和整理获得知识，并应用于实践，以实现新的目标。2相关算法理论2.1Dijkstra算法迪杰斯特拉算法（Dijkstra）是在1959年由荷兰计算机科学家艾兹格·W·迪杰斯特拉（EdsgerWybeDijkstra）提出的，因此我们用他的名字来命名这种算法。这是一种从一个顶点顺序遍历到目标顶点的最短路径算法，这种算法是求取有权图中最短路径的一种比较常用的算法。迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的相邻的顶点，知道搜索到最后一个顶点为止。采用迪杰斯特拉算法可以降低代码的空间复杂度，时代码轻量化，在这种前提下为系统中的每一辆AGV车辆（机器人）适配最优运行路径。在算法运行前先对工作环境建立地图模型，在地图中选取若干的节点作为算法模型中的“顶点”，而连接每一个顶点的“弧”即是一条路径，顶点之间的“弧”组成“弧集”，将这些弧组合起来，便是一条完整的路径，以供AGV车辆行驶。2.2经典A*算法A*（AStar）算法是一种商业应用中被用到最多的路径查找算法，也可以用来实现图的遍历，这种算法的性能很优越，准确度也非常高，常用于游戏中的地图寻路等场景。A*算法斯坦福大学研究院的彼得·哈特（PeterE.Hart），尼尔斯·约翰·尼尔森（NilsJohnNilsson）以及贝尔特拉姆·拉斐尔（BertramRaphael）于1968年发明的，A*算法的问世，在人工智能领域产生了非常重大的影响，它可以被认为是迪杰斯特拉（Dijkstra）算法的扩展。由于借助启发函数的引导，A*算法通常拥有更好的性能。A*（AStar）算法的的灵活性和适应性非常优越，是一种启发式搜索算法，经常被用于全局路径规划和寻找最短路径这样的实际问题中。A*算法功能实现的基本原理是：在路径搜索过程中，对当前节点的每个相邻节点，根据和算法互相配合的估价启发函数计算代价并估值，将代价估值最小的节点选定为下一个待搜索的源节点，再重新开始新的循环搜索，直至搜索到目标节点。3系统设计3.1AGV车辆（机器人）调度系统工作流程在对AGV车辆（机器人）的调度系统进行设计之前，我们需要先对调度系统对于车辆的调度管理流程进行初步的了解和设计。AGV车辆（机器人）在仓储车间环境中的运行过程一般设定为局域化（区域化），可以参考现实生活中公路上的交通运作方式，限制车辆单向通行，以及设置合理的“交通规则”，分别对线路和节点独立管理以实现“交通管制”。在对冲突处理方面，对于追尾、侧方相撞等冲突，可以在算法中加入“速度墙”以限制小车运行速度，在检测到路径中有运行中的AGV时，两台AGV（或多台）之间进行通讯交流，做出速度平衡，以此来避免或消除此类冲突；设定“先到先行”原则，使通过历经相交节点的AGV车辆（机器人）遵循这个原则，形成类似于“交通管制”的红绿灯路口，这种方法是解决类似冲突比较常用的方法。综合以上描述，我们可以开始设立AGV车辆（机器人）调度流程，我们使用MicrosoftVisio对调度流程建立树状流程图进行描述如图3-1所示：图3-1AGV车辆调度流程图3.2路径规划方法路径规划是AGV车辆（机器人）控制系统的基本能力之一，也是AGV车辆（机器人）调度控制所需要进一步改造和升级的核心问题。路径规划是指，在并非空旷，存在有不规则分布的障碍物的仓储环境中，根据某种评估标准，找到一条从起始位置到达预定目标位置的，全程不与环境或随机障碍物发生冲突的最优且最短的路径。根据AGV车辆（机器人）在实际应用过程中目的的不同，路径规划的评估标准也有所不同。常见的几种评估标准有：最短时间，最短距离，最少能耗等。本文中涉及的AGV车辆（机器人）路径规划是基于二维平面的求解问题，其路径规划过程可以概括为以下三个方面，首先为AGV车辆（机器人）建立合理的环境模型，即将AGV执行任务的环境状态转换为地图特征信息；其次利用某种或某些算法加以研究、设计，为AGV车辆（机器人）寻找到从起始位置到达目标位置的合理路径；最后是选择一条能避开环境中障碍物的最优路径。路径规划的原理图如下：图3-2路径规划原理3.2.1采用迪杰斯特拉（dijkstra）算法构造的AGV调度系统迪杰斯特拉（Dijkstra）算法是以标号作为计算依据和基础的一种标签式算法。我们在这里解释一下迪杰斯特拉算法的运算原理：设存在一个有向图包含了n个顶点和e条弧，用数集表示为G=(V,E)，节点集用字母V表示，弧集用字母E表示，我们设用集合C(A,B)表示两点A和B之间弧的长度，如果搜索全图发现A点和B点间没有一条互通的路径，则用无穷大（65535）或者远大于集合C(A,B)的整数（如99999）来表示。我们建立一个用来表示任一节点X与原点V0之间距离（权值之和）的数组DIST(X)，S和V-S分别表示目前搜索到的最小权值的路径节点的集合与暂未搜索到最小权值的最短路径（最小权值之和）节点集合，在算法刚开始计算时，集合S中只有一个源点V0，算法结束时，集合S中应包含整个图中的所有节点。迪杰斯特拉（Dijkstra）算法的的实现流程为：步骤一：算法初始化，将源点V0加入集合S，并对其做标记；步骤二：在V-S集合中搜索所有源点V0连接的顶点，选择距离最短（权值最小）的顶点i做标记，并将其加入集合S中；步骤三：以顶点i作为源点，在V-S中继续搜索与i直接连接且距离最短（权值最小）的点j，若DIST[j]>DIST[i]+C(i,j)，意味着目前来看从源点到j的距离经过i点比直接从V0到j要短，所以将DIST[j]更新为DIST[i]+C(i,j)，并将j点加入集合S；步骤四：重复步骤二、三运算n-1次，可找到源点V0到所有点的最短距离；步骤五：将初始顶点、中间过渡点、最终的目标点依次输出，并将其连成一条路径。最短路径四个字的含义，我们其实可以字面理解，带有边/权值的图中从其中一个顶点到另外一个目标顶点的权值最小的通路。数据结构中对最短路径的定义是：对于内网图而言，最短路径是指两顶点之间经过的边上权值之和最小的路径。并且我们称路径上的第一个顶点为源点，最后一个顶点为终点。由于非内网图没有边上的权值，所谓的最短路径其实是指两顶点之间经过的边数最少的路径。图3-3求解最短路径举例举例说明使用迪杰斯特拉算法求图2-1中由源点V0到终点V8的最短路径，过程如下：定义几个数组用来存放运算过程中需要记录的数值final[m]=1;标记V0→Vm顶点是否已找到最短路径。1表示已找到，0表示尚未找到或不可到达。Dist[m];表示V0→Vm顶点的最短路径权值和，即最短路径长度。Path[m];表示V0→Vm顶点的前驱节点顶点下标值。开始调用算法前，我们建立一个带权图的邻接矩阵，如下所示：图3-4带权图的邻接矩阵程序开始运行，

int

v,m,

k,

min;int

final[MAXVEX];

//final[m]=1表示求得顶点V0→Vm的最短路径final数组的作用是标记从顶点V0到目标点是否已经求得最短路径。如果从V0到Vｍ已经有搜索出的数值，那么final[m]=1;（2）

for

(v

=

0;

v

<

G.numVertexes;

v++)

//初始化数组

{

final

[v]

=

0;

//将所有顶点初始化

(*D)[v]

=

G.matirx[v0][v];

//将与v点有连线的顶点加上权值

(*P)[v]

=

0;

//初始化路径数组P为0

}以上代码完成了对数据初始化。此时final数组均赋值为0，表示所有点均未求得最短路径。节点V0→V1的边权值为1，V0→V2的边权值为5。D数组为{0,1,5,65515,65535,65535,65535,65535,65535}。P数组全为0，表示目前没有路径。（3）(*D)[v0]

=

0;

//V0到V0路径为0

final[v0]=1;

//V0至V0不需要求路径V0至V0路径为0，说明第一个顶点第一次搜索时会先从自身开始，而自身到自身的距离始终时0。表示V0点到V0点已经求得最短路径，因此final[0]=1。这个时候final数组中的数值用数组表示为：{1,0,0,0,0,0,0,0,0}，此时对于内存的初始化工作完成。（4）开始主循环，每次循环求得V0与一个顶点的最短路径。除去V0，因此索引从V1开始。（5）先令min为无穷大65535，通过m控制循环，与D[ｍ]比较找到最小值为min=1，同时确定k=1。代码如下：min=INFINITY;

//当前所知离V0顶点的最近距离

for(m

=

0;

m

<

G.numVertexes;

m++)

//寻找离V0最近的顶点

{

if(!final

[m]

&&(*D)[m]

<

min)

{

k

=

m;

min

=

(*D)[m];

//ｍ顶点离V0顶点更近

}

}（6）final[k]

=

1;//将目前找到的最近的顶点置为1算到这一步k=1即表示与V0最近的顶点是V1，这里的D[1]=1表示此时V0到V1的最短路径数值（权值）是1。所以在这里将final[1]设置为1。此时final数组为{1,1,0,0,0,0,0,0,0}；（7）for(ｍ

=

0;

ｍ

<

G.numVertexes;

ｍ++)//修正当前最短路径及距离

{

//如果经过v顶点的路径比现在这条路径的长度短的话

if(

!final[m]

&&

(min

+

G.matirx[k][m]

<

(*D)[m]))

{

//说明找到了更短的路径，修改D[m]和P[m]

(*D)[m]

=

min

+

G.matirx[k][m];//修改当前路径长度

(*P)[m]

=

k;

}

}以上代码实现的功能是在刚才已经找到V0与V1的最短路径基础之上，对V1与其它顶点的边进行计算，得到V0与它们的当前最短距离，如图所示：图3-5以顶点V1为原点搜索新的最短路径因为在这里min的值为1，出现了更小值的边，所以D[2]=5不再是从V0到V2过程中所有边值的和最小的了，现在D[2]=V0→V1→V2=min+3=4，D[3]=V0→V1→V3=min+7=8，D[4]=V0→V1→V4=min+5=6，于是D数组当前值为{0,1,4,8,6,65535,65535,65535,65535}。而P[2]=1，P[3]=1，P[4]=1，其表示V0到V2，V3，V4点的最短路径它们的前驱节点均是V1。此时P数组为{0,0,1,1,1,0,0,0,0}。（8）来到下一顶点，重新开始函数循环，此时i=2。第15~23行，对m循环，注意因为final[0]=1和final[1]=1，由第18行的！final[m]可知：V0与V1并不参与最小值的获取。通过循环比较，找到最小值min=4，k=2。（9）算法继续，这时k的值为2，表示V0到V2的最短路径（暂时）已经计算出结果，此时数组D[2]=4即V0到V2的最小距离为4。因此将V2对应的final[2]设置为1，表示路径已找到，此时final数组中的值为{1,1,1,0,0,0,0,0,0}。（10）运算继续，在上一步的运算结果已经找到V0→V2的路径，继续V2为源点运算搜索与之相邻的最小权值边，得到V0与它们的最短距离。如图所示：图3-6以顶点V2为原点搜索新的最短路径因为min=4，所以D[4]=6不再是V0到V4的最短距离，现在D[4]=V0→V2→V4=min+1=5，D[5]=V0→V2→V5=min+7=11。因此D数组当前值为{0,1,4,8,5,11,65535,65535,65535,65535}。而原本P[4]=1，此时P[4]=2，P[5]=2，它表示的意思是V0到V4和V5的最短路径前驱节点均为V2。此时P数组为{0,0,1,1,2,2,0,0,0}。（11）重新再开始一轮循环，此时i=3。第15~23行，通过对m循环比较找到最小值min=5，k=4。（12）第24行，由k=4表示已经求出V0到V4的最短路径，并且由D[4]=5知道最短路径距离为5。因此将V4对应的final[4]设置为1。此时final数组为{1,1,1,0,1,0,0,0,0}。（13）第25~32行，对V4与其它顶点的边值进行计算，得到V0与它们的当前最短距离，如图所示：图3-7以顶点V4为原点搜索新的最短路径有了新的最小值min为5，所以D[3]=8不再是V0→V3的最小权值，新的计算结果数组D[3]=V0→V4→V3=min+2=7，同理：D[5]=V0→V4→V5=min+3=8，D[6]=V0→V4→V6=min+6=11，D[7]=V0→V4→V7=min+9=14，因此，D数组当前值为{0,1,4,7,5,8,11,14,65535}。数据更新P[3]=1，→P[3]=4，旧数值P[5]=2，→P[5]=4。此时的数组P[6]，P[7]=4，表示V0→V3，V0→V5，V0→V6，V0→V7点目前计算出的路径中，它们的前驱节点是V4。此时P数组值为{0,0,1,4,2,4,4,4,0}。（14）后面的计算就是将之前的运算过程不断重复。在计算到最后一个节点时，得到我们所求的最短路径，即最优路径，如图所示：图3-8最终搜索到顶点V8得到最终的最短路径这时计算已经全部完成，final数组的数值全部更新为已计算完毕，数值为{1,1,1,1,1,1,1,1,1}，表示所有的顶点均完成了最短路径的查找工作。此时D数组为{0,1,4,7,5,8,10,12,16}，它表示V0到每一个顶点的最短路径的距离（权值的和），比如D[8]=1+3+1+2+3+2+4=16。此时P数组中数值为{0,0,1,4,2,4,3,6,7}。这个P数组的值可以理解为：以数组中第8个数值为例，P[8]=7，它表示要查看V0→V8的最短路径时，顶点V8的前驱节点是V7；再由P[7]=6表示要查看V0→V7的最短路径时，顶点V7的前驱节点是V6，同理，P[6]=3表示V6的前驱节点是V3。通过以上过程，我们就得到了：从起点V0到目的地V8最短路径为V8←V7←V6←V3←V4←V2←V1←V0，即就是：v0→V1→V2→V4→V3→V6→V7→V8。3.2.2采用A*算法构造的AGV调度系统A*算法是通过下面这个启发函数来计算每个节点的优先级。QUOTEfn=gn+h(n)f其中：f(n)代表节点n的综合优先级。当我们选择下一个要遍历的节点时，我们总会选取综合优先级最高（值最小）的节点。g(n)代表节点n距离起点的代价。h(n)代表节点n距离终点的预计代价，这也就是A*算法的启发函数。A*算法在运算过程中，每次从优先队列中选取f(n)值最小（优先级最高）的节点作为下一个待遍历的节点。A*算法的表示方法通常使用集合“open表”存放待遍历的节点数据，集合“close表”存放已经遍历过的节点数据。经典A*算法使用伪代码描述如下：初始化open表和close表；将起点加入open表中，并设置优先级为0（优先级最高）；如果open表不为空，则从open表中选取优先级最高的节点n：如果节点n为终点，则：从终点开始逐步追踪parent节点，一直达到起点；返回找到的结果路径，算法结束；如果节点n不是终点，则：将节点n从open表中删除，并加入close表中；遍历节点n所有的邻近节点：如果邻近节点m在close表中，则：跳过，选取下一个邻近节点如果邻近节点m也不在open表中，则：设置节点m的parent为节点n计算节点m的优先级将节点m加入open表中3.2两种算法的比较A*算法和迪杰斯特拉（dijkstra）算法都是启发式搜索，迪杰斯特拉（dijkstra）算法可以看成是广度优先搜索（BFS），而A*可以认为是深度优先搜索（DFS）。迪杰斯特拉（dijkstra）算法是按照节点顺序，从当前节点开始，想周边发出搜索，找出当前阶段的最有结果并记录，这样搜索出的结果一定是最优的，不用考虑之前的结果，如此一步一步搜索到最后一个节点，可以在到达终点时，每一次搜索得到一个最优结果，这样计算出的最短路径结果一定时最优解。A*算法在计算过程中使用了两个数组用来才存储已遍历和未遍历的节点，我们将这两个数组分别命名为“OPEN表”和“CLOSE表”。运行过程可以如下表示：（1）将源点数据存入OPEN表；（2）①遍历OPEN表，根据公式（3-1）找出F（F=G+H）值最小的节点，将这个节点设为新的源点，发散式搜索当前节点周围的节点；②搜索完毕，将这个节点标记为已搜索并将这个节点存入CLOSE表中；③将当前搜索的节点周围紧邻的节点放到OPEN表中（除了墙、禁行区域、障碍物等）；④重复上述操作，每一次循环开始，选择F值最小的节点作为当前操作节点。（3）当最后一个节点数据存入到CLOSE表中的时候，算法结束。（4）将最终的到的路径存入内存中，从终点开始，每个节点沿着父节点移动到起点，就是最终路径。上面的公式我们在上一小节已经做出了解释，在这里我命在做出简单的描述：F=G+H中：H是启发函数，是当前点到终点距离的估计，一般采用曼哈顿距离（当前点和终点横纵坐标差之和）；G就是起点到当前点的距离，这里G值的度量方式一般是上下左右取一个值比如10，对角线的四个点取一个值比如14（一般比上下左右的值要大），而在A*中表示障碍点一般会给对应点一个特别大的G值，所以在筛选的时候就会放掉。3.3工作空间模型建立方法在解决路径规划问题之前，我们首先要考虑如何对工作环境建立模型。工作环境空间建立模拟地图是对AGV车辆进行路径规划的前提，这是我们所设计和开发的AGV车辆调度系统所需要解决的最基本的问题。在建立模拟地图的时候，我们需要先将AGV车辆（机器人）的工作空间进行模拟数值化，图形化，然后将我们测量和计算得到的这些信息转换成可以在电脑种存储的数字信息，将这些信息输入到AGV车辆调度控制系统的内存里，然后调度系统调用代码中的核心算法，一句模拟地图给出的信息从而对AGV车辆进行路径规划，已确保AGV车辆平稳顺利运行到目标地点。本文介绍一种名为“格栅建模法”的建立地图的方法。栅格地图建模法是由卡内基梅隆大学的汉斯·莫拉维克（HansMoravec）等人在“占据栅格地图”（Occupancygridmapping）算法的基础上开发出来的新型地图建模方法，是一种在解决AGV车辆路径规划问题上的比较成熟的应用技术，在目前市场上出现的比较成熟的商业AGV调度系统种已经有了比较广泛的应用。栅格地图法是的原理是：将AGV车辆（机器人）的实际工作空间的地图信息离散化，再把地图分割成若干个大小均匀，彼此互相紧邻的单元格，建立好栅格后，我们需要在每一个单元格上做出标记（一般使用序号标记法）。在算法开始进行路径规划时，我们首先建立一个数组矩阵，用来表示AGV车辆（机器人）的工作空间环境。在建立好的模拟栅格地图中，我们将障碍栅格标记为1，这说明在这个标记为１的栅格所代表的实际位置存在障碍物，AGV车辆无法在此处通行；我们将自由栅格标记为0，这说明在这个标记为０的栅格所代表的实际位置是不存在障碍物的，可以自由通行。栅格地图建模法建立地图模型的性能始于地图划分栅格大小、多少、精细程度等因素息息相关的。栅格分割的越小，分辨率越高，其表示的工作环境空间信息将会非常精细和清晰，但这样精细的信息往往是以运行速度降低为代价的，栅格划分越精细，占用内存越大，运算时间过长，反应越慢，这样反而会降低整个系统的工作效率；反之，我们对栅格划分的大小略微放宽要求，虽然会降低模拟地图的精度，但计算速度会大幅度提升，效率也就变高了。所以我们在建立模拟栅格地图时，需要综合考量各方面因素，包括实际运行空间的大小、计算机的运算性能等因素，合理的规划处最适合当前车间环境的模拟山歌地图，使系统的运行效率达到最高。AGV工作空间的环境建模使用栅格地图建模法，其创建地图的难度较低，维护方便，且可以在空间中出现临时仿制的障碍物时能轻松做出调整，因此我在这篇文章里选择栅格地图建模法来建立AGV车辆（机器人）的工作空间环境的模拟地图。在建模过程中，先不考虑AGV车辆（机器人）和障碍物（墙壁、机床等）的高度，使用栅格地图建模法将AGV的工作空间环境转化为数字化的二维数组。理想状态下，设定环境中的障碍物永远保持静止状态。假定工作空间环境信息已知，即AGV车辆（机器人）的起始点位置及环境中的障碍物位置。我们将AGV车辆（机器人）的工作空间环境切割成大小、形状完全一致的栅格，并对栅格使用二进制数字进行标识。常用的栅格标识方法有两种：直角坐标法和序号法。直角坐标法是以栅格地图的左下角为坐标原点，可以近似理解为平面直角坐标系。设定以每个栅格的几何中心点坐标记为AGV停留此处时的坐标，如图3-9所示。序号法就是从栅格地图的左下角的栅格开始，按照从左到右，从下到上的顺序给每一个栅格标上序号，如图3-9所示:图3-9栅格地图法建立地图示意直角坐标法和序号法可以通过映射关系来进行转换，其计算方法为：QUOTE(3-2)公式中：N：当前栅格的编号；L：栅格地图的行数；D：栅格地图的列数；Δx和Δy：栅格与横纵坐标的对应关系；Mod：取余函数；Int：取整函数。为了避免AGV车辆经过障碍物附近时与障碍物发生碰撞，在运用栅格地图法建模的过程中，将障碍物的边界进行一定比例的扩展。具体扩展比例示AGV的尺寸大小来定，本文为了方便计算，取AGV车辆（机器人）的长度和宽度的一半，分别对障碍物的长和宽进行扩展。AGV的工作空间环境分为两种状态，即存在障碍物的障碍栅格和不存在障碍物的自由栅格。如图3-9所示，图中黑色色块表示障碍栅格，白色色块表示自由栅格。3.4使用经典A*算法求取最短路径使用经典A*算法进行AGV车辆（机器人）全局路径规划的具体步骤如下：（1）从起点S开始搜索，将S节点周边的节点存入“OPEN表”中。这点已经在前文中做出了解释，在此我们再介绍一下这两个表的作用，其中“OPEN表”的作用是：存储源点周边的待搜索节点，在表格内部将这些节点按每个节点自身的代价值大小进行排序；“CLOSE表”用来存放已经被搜索过的节点，即在上一步计算中在OPEN表中对比得到的最小代价节点。在搜索过程开始时，OPEN表存储源点S，CLOSE表存储已经被标记为障碍物节点。（2）根据公式（3-1）计算OPEN表中节点的代价估值，即当前节点的扩展节点（周围紧邻的节点）的代价估值，从表中选择估值最小的节点V当作下一步待搜索的源点，将其他的估值大于节点V的节点全部放入CLOSE表中。（3）判断节点V书不是我们需要寻找的目标，如果这个节点V是我们档期那这轮算法计算最终要搜索到的目标节点，那么结束搜索，根据它指向父节点的前向指针，得到最佳路径；如果节点V不是目标节点，则将节点V从OPEN表移动到CLOSE表中。（4）运行到此步时，我们把当前的节点V作为新的搜索源点，将节点V的周边的未被搜索过的节点添加到OPEN表中，然后循环步骤（2）。（5）当CLOSE表中已经将目标节点G存入时，说明已经搜索到最短路径，跳出循环，算法结束。最后一步，通过指针反向跟踪，确定出规划的路径。综合以上描述，我们总结出经典A*算法全局路径规划流程图，如图3-10所示：图3-10使用A*算法进行路径规划的流程4算法设计与编写本设计系统使用编程语言为C++，使用的编译环境为QTCreator。4.1软件及开发环境介绍QtCreator是Qt被

Nokia

收购后推出的一款全新的轻量级集成开发环境（IDE）。此IDE能够跨平台运行，支持的系统包括Linux（32位及64位）、MacOSX以及Windows。根据官方描述，QtCreator开发的初衷是为了使开发人员能够利用Qt这个应用程序框架更加快速及轻易的完成开发任务。QtCreator包括项目生成向导、高级的C++代码编辑器、浏览文件及类的工具、集成了QtDesigner、QtAssistant、QtLinguist、图形化的GDB调试前端，集成qmake构建工具等。4.2C++语言介绍4.2.1C++语言的起源C++是一种非常流行的程序设计语言。它是一种静态数据类型检查的，支持多范型的通用程序设计语言。C++支持过程化程序设计、数据抽象化、面向对象程序设计、泛型程序设计、基于原则设计等多种程序设计风格。C++是C语言的继承，它既可以进行C语言的过程化程序设计，又可以进行以抽象数据类型为特点的基于对象的程序设计，还可以进行以继承和多态为特点的面向对象的程序设计。C++擅长面向对象程序设计的同时，还可以进行基于过程的程序设计，因而C++就适应的问题规模而论，大小由之。不过，虽然C语言非常流行，但并非是完美无缺的。C语言虽然是一种高级编程语言，但又同时具备一些低级语言的特点。于是这就造成了C语言的存在在高级编程语言和低级编程语言之间，所以就造成了它的优点和缺点都很突出。与低级语言（如汇编语言）相似的点在于，C语言程序可以直接操纵计算机的内存。这这因素使得C语言成为系统程序编写时的首选。但是在编写其他程序时，C语言不像其他高级语言那样容易理解。另外，它不像其他高级语言那样具有完善的自动检查功能。为了解决上述问题以及C语言的另一些缺陷，AT&T贝尔实验室的本贾尼·斯特劳斯特卢普（BjarneStroustrup）在20世纪80年代初发明了C++。他将C++设计成一种更好的C语言。C语言的很大一部分都成了C++的一个子集，所以大多数C语言程序其实也是C++程序（反之则不成立，许多C++程序都绝非C语言程序）。与C语言不同的是，C++具备了“面向对象编程”（OOP）的能力。C++不仅拥有计算机高效运行的实用性特征，同时还致力于提高大规模程序的编程质量与程序设计语言的问题描述能力。4.2.2C++的特点（1）支持数据封装和数据隐藏在C++中，“类”是支持数据封装的工具，“对象”则是数据封装的实现。C++通过建立用户定义类支持数据封装和数据隐藏。在面向对象的软件编译器应用程序系统设计中，将该类数据和对该类的相关数据执行信息分别进行合法转换运算后将操作的两个函数分别进行封装组合到一起，并以此函数作为其中一个函数类的自动执行定义。其中的函数对象类型说明了其是否具有某一个属于给定函数范畴的对象类型。每一个对象给定的此类的集体对象都可能包括了此类所对象指定的若干个受到私人、公共、保护的集体成员。完好地重新定义的系统类一旦被重新建立,就可能会把它们用来看作不只是一个完全不被封装的系统实体,可以直接用来把它作为一个系统整体的组成单元。类的真正内部管理工作已经被人们隐藏了很多起来，使用他们完善自己重新定义的这个类的工具人们不必再那么需要再去认识和看到任何类的真正内部管理工作，只要他们已经能够完全知道他们怎样才能正确地看和使用它。（2）支持继承和重用在C++现有类的基础上可以声明新类型，这就是继承和重用的思想。通过继承和重用可以更有效地组织程序结构，明确类间关系，并且充分利用已有的类来完成更复杂、深入的开发。新定义的类为子类，成为派生类。它可以从父类那里继承所有非私有的属性和方法，作为自己的成员。（3）支持多态性采用多态性为每个类指定表现行为。多态性形成由父类和它们的子类组成的一个树型结构。在这个树中的每个子类可以接收一个或多个具有相同名字的消息。当一个消息被这个树中一个类的一个对象接收时，这个对象动态地决定给予子类对象的消息的某种用法。多态性的这一特性允许使用高级抽象。继承性和多态性的组合，可以轻易地生成一系列虽然类似但独一无二的对象。由于继承性，这些对象共享许多相似的特征。由于多态性，一个对象可有独特的表现方式，而另一个对象有另一种表现方式。4.3使用C++进行系统设计4.3.1运行C++程序的步骤（1）搭建编译环境；（2）启动编译器；（3）编辑程序文档；（4）编译程序；（5）对代码进行封装；（6）执行程序；4.3.2代码说明首先进行地图生成，在此使用第三节所提到的栅格地图建模法，在代码中以二维数组来存储数据，代码描述为：int_MAP[31][31]={0};生成31*31的地图如图4-1所示：图4-1建立31*31模拟场景地图在图4-1程序运行界面右侧，是实现各种功能的操作按键，交互方式为：使用鼠标点击按钮，按钮调用所链接的函数段，以此来实现按钮上文字所描述的功能。代码描述为：MainWindow::MainWindow(QWidget*parent):QMainWindow(parent),ui(newUi::MainWindow){ui→setupUi(this);this→setWindowTitle("AGV自动寻路模拟");this→resize((N+9)*25,(M+9)*25);this→setFocus(Qt::MouseFocusReason);b_set=newQPushButton(this);b_set→setText("设置禁行区域");b_set→setGeometry((N+2)*25,30,150,20);b_set→setEnabled(true);agv_set=newQPushButton(this);agv_set→setText("部署agv");agv_set→setGeometry((N+2)*25,60,150,20);agv_set→setEnabled(true);tg_set=newQPushButton(this);tg_set→setText("设定目标");tg_set→setGeometry((N+2)*25,90,150,20);tg_set→setEnabled(true);findpath=newQPushButton(this);findpath→setText("自动寻路");findpath→setGeometry((N+2)*25,120,150,20);findpath→setEnabled(true);refresh1=newQPushButton(this);refresh1→setText("重置");refresh1→setGeometry((N+2)*25,150,150,20);refresh1→setEnabled(true);control=newQPushButton(this);control→setText("模拟设备对接");control→setGeometry((N+2)*25,180,150,20);control→setEnabled(true);yslj=newQPushButton(this);yslj→setText("预设路径");yslj→setGeometry((N+2)*25,210,150,20);yslj→setEnabled(true);yslj_move=newQPushButton(this);yslj_move→setText("按预设路径移动");yslj_move→setGeometry((N+2)*25,240,150,20);yslj_move→setEnabled(true);save_lj=newQPushButton(this);save_lj→setText("使用记忆路线");save_lj→setGeometry((N+2)*25,270,150,20);save_lj→setEnabled(true);a=newAstar();last_way=NULL;connect(b_set,SIGNAL(clicked()),this,SLOT(shift_to_b_set_mode()));connect(agv_set,SIGNAL(clicked()),this,SLOT(shift_to_agv_set_mode()));connect(tg_set,SIGNAL(clicked()),this,SLOT(shift_to_tg_set_mode()));connect(findpath,SIGNAL(clicked()),this,SLOT(_findpath()));connect(refresh1,SIGNAL(clicked()),this,SLOT(ref1()));connect(control,SIGNAL(clicked()),this,SLOT(control_sim()));connect(yslj,SIGNAL(clicked()),this,SLOT(set_lj()));connect(yslj_move,SIGNAL(clicked()),this,SLOT(move_yslj()));connect(save_lj,SIGNAL(clicked()),this,SLOT(lj_save()));}每条功能语句会引用其所对应的槽函数，具体如下：（1）功能“部署AGV”，其对应按钮的代码为：agv_set=newQPushButton(this);agv_set→setText("部署agv");agv_set→setGeometry((N+2)*25,60,150,20);agv_set→setEnabled(true);按钮后链接的槽函数为：if(setstar)//放置AGV{painter.setBrush(QBrush(Qt::red,Qt::SolidPattern));painter.drawRect(QRect(_starx*25,(_stary+1)*25,25,25));}此段代码实现了在地图上放置一个AGV小车，并将其标记为红色，效果如图4-2所示：图4-2在模拟地图中部署AGV小车我们给代码加一个for循环for(autoit=m_starts.begin();it!=m_starts.end();it++)则可实现在地图上布置多个AGV小车，效果如图4-3：图4-3在模拟地图中部署多个AGV小车（2）功能“设定目标”，其对应按钮代码为tg_set=newQPushButton(this);tg_set→setText("设定目标");tg_set→setGeometry((N+2)*25,90,150,20);tg_set→setEnabled(true);按钮后链接的槽函数为：if(settg)//放置目标{painter.setBrush(QBrush(Qt::blue,Qt::SolidPattern));painter.drawRect(QRect(_endx*25,(_endy+1)*25,25,25));}此段代码实现了在地图上放置一个目标，并将其标记为蓝色，效果如图4-4所示：图4-4在模拟地图中放置一个目标（3）功能“设置禁行区域”，其对应代码为：b_set=newQPushButton(this);b_set→setText("设置禁行区域");b_set→setGeometry((N+2)*25,30,150,20);b_set→setEnabled(true);findpath=newQPushButton(this);findpath→setText("自动寻路");findpath→setGeometry((N+2)*25,120,150,20);findpath→setEnabled(true);yslj_move=newQPushButton(this);yslj_move→setText("按预设路径移动");yslj_move→setGeometry((N+2)*25,240,150,20);yslj_move→setEnabled(true);switch(_MAP[i][j]){case1://画墙壁painter.setBrush(QBrush(Qt::gray,Qt::SolidPattern));painter.drawRect(QRect(i*25,(j+1)*25,25,25));break;case0://画通路painter.setBrush(QBrush(Qt::white,Qt::SolidPattern));painter.drawRect(QRect(i*25,(j+1)*25,25,25));break;case2://生成路径painter.setBrush(QBrush(Qt::yellow,Qt::SolidPattern));painter.drawRect(QRect(i*25,(j+1)*25,25,25));break;case3://画预设路径painter.setBrush(QBrush(Qt::green,Qt::SolidPattern));painter.drawRect(QRect(i*25,(j+1)*25,25,25));break;}此段代码包含了所有关于路径在地图上显示的功能，绘制禁行区域如图4-5示，在图中以灰色显示：图4-5在地图上绘制禁行区域在设定好“墙”，并且分别放置了AGV小车以及目标地点后，选择“自动寻路”，即可生成以A*算法实现的寻找最短路径功能。寻路成功后在地图上使用黄色来显示以求得的路径，具体效果如图4-6、4-7所示：图4-6在地图上显示求得一条的路径图4-7在地图上显示求得多条路径“预设路径”是在不是用自动寻路的情况下，按用户的需求在地图上预设一条路径，用户可以根据不同的运输情况，自由的在地图上绘制运行路径，此功能在地图上以绿色显示自定义的路径，具体效果如图4-8所示：图4-8在地图