AGV调度方法入门
目的
首先介绍AGV调度中的基本概念和主要问题，然后分析现有调度方法的特点。
上图由Mathematica制作1AGV及其调度问题
1.1AGV是什么？
国家标准[1]^{[1]}[1]对AGV的定义是：
AGV（AutomatedGuidedVehicle自动导引车）：装备有电磁或光学等自动导引装置，由计算机控制，以轮式移动为特征，自带动力或动力转换装置，并且能够沿规定的导引路径自动行驶的运输工具，一般具有安全防护、移载等多种功能。
通俗的讲，AGV就是一个用来运输的移动机器人，它是一个搬运工，把货物从A处运到B处，因此AGV的大部分研究也是包含在移动机器人领域内的。
1.2AGV调度系统是什么？
国家标准[1]^{[1]}[1]对AGV调度系统的定义是：
调度系统（Dispatchingsystem）：上位控制系统中用于任务调度、车辆管理及交通管理的控制软件。
在深入之前，为了便于理解，先阐明基本概念的含义。●Dispatch（派遣）：指派一个AGV去执行一个运输任务。DispatchingistheprocessofassigningatransportationjobtoanAGV[2]^{[2]}[2].●Schedule（狭义上的“调度”）：分配一批运输任务给一组AGV去执行。SchedulingistheprocessofdispatchingasetofAGVstoabatchoftransportationjobs[2]^{[2]}[2].TheaimofAGVschedulingistodispatchasetofAGVstoachievethegoalsforabatchofpickup/drop-off(orP/Dforshort)jobs[3]^{[3]}[3].●Route（路径规划）：生成所有被指定AGV的路径使其能完成各自被指派的任务。在机器人领域，路径翻译为path；而在AGV领域通常使用route表示相似的概念，翻译为“路线、轨道”，它一般表示固定的不经常变动的路径。path只能用作名词，route还可以作为动词，表示“为…指派路径”。本文我们不纠结这些微妙的细节，统一称其为路径。RoutingistheprocessofdeterminingroutesforasetofAGVstofulfilltheirrespectivetransportationjobs[2]^{[2]}[2].Oncetheschedulingdecisionismade,themissionofroutingistofindasuitablerouteforeveryAGVfromitsorigintodestinationbasedonthecurrenttrafficsituation[3]^{[3]}[3].单独看一个AGV的工作并不复杂。例如机床要加工零件时通过更上层的MES控制系统给AGV的调度系统发出请求命令，后者派遣（dispatch）一台AGV负责把原料从仓库运送到机床。这个过程可以被称为一个任务（job），一个任务就是在一对工作地点之间移动。在这个例子中，机床只提出需求（我要在什么时间加工什么零件），至于选择哪个AGV运送零件原料，AGV该沿哪条路线运动，这些都是调度系统的工作。调度系统一旦为AGV指定好路径后，AGV上的车载控制器会根据指令完成具体的运动控制任务，例如速度保持在多少，遇到路口转向时轮子怎么转动等等。所以在一个完整的大系统中，AGV调度系统位于上层控制系统和底层控制系统的中间，其到管家的作用。但是对于多个AGV，调度问题就会变得非常困难，而且AGV数量越多，难度越大。因此，调度系统成为AGV行业的一个关键技术[4]^{[4]}[4]。而能够调度的AGV数量也成为评判一个调度系统强大与否的重要指标。根据笔者的判断，虽然目前从事AGV行业的企业很多，但是具有自主调度系统的企业并不多，而能够真正把调度系统优化的很好、能够最高效率地利用AGV系统的企业更是屈指可数。当然，如果站在AGV厂家的立场，他们并没有太大的动力把调度系统做的很高效。因为提高调度效率会减少AGV的投入量，这意味着卖出的AGV就少了。对实际应用的AGV调度系统软件，它的功能通常是非常丰富的，一般包括：任务管理、车辆状态监控、路径规划、地图编辑、数据库查询等。
1.3AGV调度问题
大多数人虽然未必了解调度的方法和细节，但对它或多或少都有一些直觉上的感性认识。如果你在火车站或者飞机场用电脑看本文，那么你同时正在经历两种调度过程：大量的火车和飞机需要调度，与此同时你电脑里的操作系统也在对大量的任务进行调度。当很多事件同时发生，而且存在竞争时就需要调度了。如果只有一个事件发生，那么所有资源都由这个事件支配（火车可以在任何一条铁轨上跑），我们不需要调度；如果多个事件同时发生，但是没有竞争关系（美国的一列火车和中国的一列火车），我们也不需要调度，因为它们不会发生冲突。首先，我们应该能分辨一个问题是不是调度问题。假设工厂中只有一台AGV在工作，此时调度问题就退化成简单的路径规划问题了。因为不需要考虑该将任务分配给哪台AGV的问题，也不需要考虑在一个路口谁先走谁后走的问题。所以调度问题的前提是多个AGV共享路径网络，换句话说AGV之间存在资源争夺。就像马路上的车辆一样，谁都想怎么快怎么开车，如果每个司机都只考虑自己而不考虑对方，那么后果很可能是谁都别想走（拥堵在一起）。于是，个人追求自己局部的最优解却变成了全局的最差解，所以调度是有存在的必要的，而且有时很重要（红绿灯、交警都起到某种“调度”的作用）。多数情况下，调度系统需要统筹所有AGV的行为（上帝视角），它追求的不是某几个AGV的最优解（当然它有能力这么做），而是整体的最优。我们可以设想一下，能不能做一款调度软件来调度一个城市里所有的车辆，让整体解是最优的（例如所有人耗费的汽油加起来最少）。这个最优解一定存在，但是实际上却几乎不可能解出来，因为有两个难点。首先，调度系统要掌握海量的信息，比如张三八点从家里开车到单位，赵四九点开车送孩子，王五的车油量不够，需要中途加油等等。更困难的是这些信息是变动的，例如张三的车开着开着抛锚了把路堵死了。第二个问题是，调度问题的复杂度随着参与者的数量呈指数增加。如果只有几十辆车，现在的算法和计算机硬件还能勉强解决，如果要处理成千上万辆车，那恐怕只有上帝才能做到了。信息缺乏和维度诅咒是调度问题面临的主要困难。扯远一点，其实计划经济也面临同样的问题，要对经济进行计划需要决策者掌握海量的信息，并拥有超级大脑，在那个多数人连电脑是什么都不知道的落后年代搞计划经济必然不会太好。正因为调度问题是极其复杂的，所以大多数时候我们只能退而求其次找一个说的过去的近似最优解，这也是实际生活中每个路口的交通信号灯闪烁背后的逻辑。
相向碰撞追击碰撞节点碰撞2路径规划
多个AGV的调度需要规划不同AGV的路径，所以我们先了解下现有的路径规划方法。AGV是个听话的笨蛋，如果调度系统想让一个AGV从A走到B，它不能简单地将A和B站点的信息给AGV，而是要将A到B之间的完整路径告诉AGV[5]^{[5]}[5]。目前普遍用“图”（graph数学概念）对AGV的行驶空间进行建模，“图”由节点和边组成。所以AGV的行驶路径可以表示为一系列相邻的节点。
2.1Dijkstra方法
Dijkstra方法是一种经典的搜索路径的方法，它的逻辑不是特别复杂，有很多介绍它的文章。但是如果照本宣科的讲它的步骤，你可以复现但未必能真正理解，因为它背后隐藏着深厚的数学背景。为此，笔者写了一篇博客讲解它的原理：Dijkstra方法入门。
3调度方法
因为AGV调度问题很有理论深度，所以吸引了大批的学者，他们不同的角度讨论这个问题，提出了各种花哨的方法。不过很多理论难以转化成实际可行的方法，所以实际和理论有很大的差异。
3.1多机器人协调问题
AGV调度问题可以看成多机器人协调问题（Multi-RobotCoordination）的特例。多机器人共享一个环境，如何协调它们的运动使所有机器人都能能达到目标。讨论多机器人协调问题是为了对调度问题有更好的理解。最早的方法也是最简单的方法之一，就是为不同的机器人设置不同的优先级（Priority）。优先级高的机器人先规划自己的路径，优先级低的机器人将比它高的机器人的路径视为障碍物，进而再进行规划。当然这种方法有个明显的缺点：优先级高的机器人过于霸道，它把所有的路都堵死了，以至于优先级低的机器人怎么也找不到路。这时我们就要调整优先级了。
引用文献[1]《GBT30030-2013国家标准自动导引车(AGV)——术语》.[2]ComparisonofRoutingStrategiesforAGVSystemsusingSimulation,MarkB.Duinkerken,2006.[3]SchedulingandRoutingAlgorithmsforAGVs:ASurvey,QiuLing,2002.[4]全面解读科尔摩根NDC中国市场策略.[5]AGV调度系统的设计，戴志存，物流技术与应用,2015.[6]openTCS-4.2.0.
智能机器人技术与工程项目介绍 【2024年版】
一、项目背景
机器人被誉为“制造业皇冠顶端的明珠”，其研发、制造及应用无疑是衡量一个国家科技创新和高端制造业水平的重要标志。智能机器人融合智能感知、计算机视觉、模式识别、深度学习、“互联网+”信息技术、知识图谱等新一代人工智能技术，在工业机器人、移动机器人、服务机器人、特种机器人、AGV与无人机等方向内进一步提升机器人技术的智能化、信息化和柔性化水平，在智能制造、现代工业、自动化、商业、民生、社会服务等领域得到广泛应用。
智能机器人技术与工程是人工智能2.0与机器人技术的深度融合，我们认为，通过机械工程、电气工程、控制工程、计算机技术、传感与信息技术、人工智能和仿生工程学等多学科交叉培养，将有助于同学们更好地成长为可迎接未来领域挑战的高层次人才。因此，浙江大学工程师学院设立跨学科的智能机器人技术与工程项目制人才培养机制，探索专业知识复合型高层次工程科技人才培养的新方法、新模式，并付诸实践检验，是培养智能机器人技术与工程领域高层次人才的重要实践。
二、项目特点
本项目面向机器人与智能装备行业（企业）实际需求，聚焦机器人、人工智能、智能装备及智能制造等行业，以智能化、信息化和柔性化发展为主线，重点培养掌握智能机器人技术与人工智能2.0深度融合的关键技术人才。以项目制的新模式开展多学科复合交叉专业学位研究生培养，面向机器人、高端装备、智能制造、互联网+、人工智能等现代新兴产业，培养智能机器人设计、控制、规划、编程、仿真、传感、检测、运维等方面的应用型、复合型的高层次的机械、电气、控制、计算机、信息工程领域的研发创新、工程技术与管理人才。
构建起“产学研教”深度融合的人才协同培育与科研实践平台，以浙江大学机器人研究院为纽带，联合之江实验室、浙江省机器人与智能装备重点实验室、中国（浙江）机器人及智能装备制造业创新中心、浙江智能机器人研究院、杭州新松机器人自动化有限公司、余姚市机器人研究中心等高能级机器人研究平台和龙头企业，通过共建研发实验室、共建专业课程、共建师资队伍、共同推进技术创新等方式进一步加强与行业、企业的紧密合作，形成人才共育、过程共管、成果共享、责任共担的校企合作办学体制。
三、项目培养特色
1. 课程培养：专业课程体现机器人、人工智能、智能制造、工业互联网等交叉，每门专业课程邀请至少一位行(企)业专家参与共建；重视智能机器人技术前沿专题（技术前沿类）、智能制智能机器人典型工程应用实例（案例教学）、智能机器人技术综合实践（实践实验类）等三类课程。
2. 项目实践：课程学习完成后，每位研究生将进入浙江大学机器人研究院/余姚市机器人研究中心、高能级机器人研究科研院所或合作企业进行为期六个月以上的专业实践训练，开展高水平的智能机器人与智能装备关键技术和工程化技术研究，联合攻关工业/服务/特种机器人、智能终端与高端装备相关项目。由企业导师和校内导师共同指导完成专业实践训练，并得到企业认可，方可完成专业实践训练环节，提升研究生的综合科研创新、技术研发和工程实践能力。
3. 企业实习：半年。可由导师指派到合作企业，也可由学生自主落实实习单位。
四、项目合作企业简介
立足工程类专业学位卓越人才培养目标，通过与行业内知名企业和龙头企业共建研发实验室、共建实训基地、校企项目合作、校企联合培养等方式，构建多方位、全过程的校企深度合作人才培养模式。
目前开展合作的单位和企业包括：之江实验室、北航杭州创新研究院、中科院宁波材料所（浙江省机器人与智能装备重点实验室）、中国（浙江）机器人及智能装备制造业创新中心、余姚市机器人研究中心、浙江智能机器人研究院、杭州新松机器人自动化有限公司、杭州申昊科技股份有限公司、杭州景业智能科技有限公司、杭州海康机器人技术有限公司、浙江国自机器人技术股份有限公司、浙江华睿科技股份有限公司、浙江双环传动机械股份有限公司、浙江浙能数字科技有限公司、浙江云联智能制造研究院有限公司、宁波江丰生物信息技术有限公司、宁波中亿自动化装备有限公司、余姚市永创电磁阀有限公司等。
五、项目研究方向及导师团队简介
研究方向一：工业机器人及集成应用
研究方向二：服务机器人
研究方向三：特种机器人
研究方向四：移动机器人
研究方向五：无人机
研究方向六：人工智能
研究方向七：机器视觉与图像处理
导师团队：浙江大学机械工程学院、电气工程学院、控制科学与工程学院、海洋学院、信息与电子工程学院导师和产业界高级专家组成。
六、项目招生人数及说明
新工科、新实践！本项目欢迎机械工程、控制工程、电气工程、新一代电子信息技术等专业同学报考！
本项目学生住宿：在学院本部住宿资源有盈余的情况下，第一学年可以申请由学院协助安排住宿，住宿收费按学校统一标准执行；第二学年起在研究院所在地安排住宿(浙江省余姚市)，住宿收费按住宿所在地相关标准或相关合同执行。
本项目为每位研究生提供每月3000元研究津贴（二年级到研究院后开始发放），2人60平米一套拎包入住的公寓（免费）。
本项目招收全日制专业学位研究生2024年计划如下，最终按研究生院下达为准。
专业类别
专业类别代码
领域名称
领域代码
招生方向名称
招生计划
电子信息
0854
控制工程
085406
控制工程（机器人研究院智能机器人技术与工程项目）
4
电子信息
0854
新一代电子信息技术
085401
新一代电子信息技术（机器人研究院智能机器人技术与工程项目）
2
机械
0855
机械工程
085501
机械工程（机器人研究院智能机器人技术与工程项目）
6
能源动力
0858
电气工程
085801
电气工程（机器人研究院智能机器人技术与工程项目）
3
咨询方式：gcsxyzs@zju.edu.cn 0571-88281621
机器人研究院 ：zzzhengzhen@zju.edu.cn 0574-62550815
浙江大学机器人研究院简介
浙江大学机器人研究院是浙江大学与余姚市政府于2017年合作共建的综合性、应用型校设研究机构，是推动余姚产业优化升级的重要科创平台。余姚市给研究院提供了充足的建设运行经费和科研经费，也向研究院提出了大量的技术需求。截止2022年6月，研究院引进孵化企业35家，服务企业7000家次以上。自2008年开始招收和联合培养全日制硕士研究生以来，截止2022年6月，研究院已联合学校相关学院累计培养硕士研究生215名，涉及机械工程、电气工程、控制工程、计算机技术、动力工程等多个专业。经过多年的探索与实践，研究院坚持以智能机器人技术研发与工程创新能力为核心，围绕机器人与智能装备领域，以推动创新创业为目标，以产学研紧密合作为特色，以用人机制改革和人才培养模式创新为动力，汇聚一流专家，培养一流专业人才，培育相关新兴产业念，研究生培养工作不断走向成熟、形成特色。
研究院拥有雄厚的研究基础，同时拥有一支高水平研究领导团队，由中国工程院院士谭建荣担任名誉院长，由浙江大学党委副书记朱世强担任院长，由中国工程院院士杨华勇担任学术委员会主任，由国家教学名师陆国栋担任常务副院长。建有关键共性技术实验室5个，中试基地6个，产业化基地4个，加工中心2个，拥有包括3名院士、3名国家高层次人才，1 名外籍教授在内的30多位导师队伍。目前研究院在读研究生80多位，其中绝大多数研究生已承担相关研究团队的研究工作，成为研究院的新生力量。建有省市级创新平台15个；实现科技转移转化35余项；以研究院为核心的机器人与智能装备行业的创新创业生态体已显雏形。
浙江大学机器人研究院
浙江大学工程师学院
2023.06