仓储物流机器人集群的智能调度和路径规划

　　仓储物流机器人集群的智能调度和路径规划沈博闻i2‘3，于宁波i2，刘景泰1>2（1.南开大学机器人与信息自动化研究所，天津300071；2.南开大学天津市智能机器人技术重点。主要考虑停放位置（空闲或货架占用）、入货口、出货□、纵向道路和横向道路。每个被2条纵向道路和2条横向道路围起来的区域内，有2排停放位置。的长度宽度、货架和道路的数量和密度、入货口出货口的数量和位置、订单的数量和密度等参数，都可以根据具体需要灵活设定。

　　在此仓储空间中，多个移动机器人同时运行，为了避免碰撞冲突、简化机器人的运行规则、提高系统安全运行的鲁棒性，设定货架区域间的横向、纵向道路均为单行道。

　　对于建立的仓储空间模型，物流任务的形式是运送某一货架从停放位置A到某个入货口/出货口位置，待入货/出货任务完成后，再搬运回货架区域位置如所示。

　　其中，第1个和第3个步骤可以通过任务的分配调度进行优化，减少所花费的时间；第2个步骤可以采用路径规划方法对机器人的路径进行优化。

　　2机器人的智能调度和路径规划2.1机器人的智能调度算法针对前述物流任务的第1个步骤进行优化，应使承担任务的机器人能尽早地运行到对应货架处。因此根据一个评价函数对所有可能执行任务的机器人进行评价，从中选取*合适的机器人。

　　A11总的评价函数为1994-2网格为节点扩展路径修改成以道路为节点扩展路>use.Allrightsreserved.*近的一个空闲位置停放。使用曼哈顿距离估计代价：表示当前点的纵坐标。n.x表示第n个存放位置的横坐标，n.y表示第n个存放位置的纵坐标。abs表示求绝对值的函数。

　　2.2特殊规则约束下基于A算法的路径规划在设计的仓储空间结构中，目前，应用于多机器人系统运动规划的方法有人工势场法、神经网络况、模糊逻辑78、A等算法。其中，A算法已经得到了广泛地应用，而且能够保证找到*优的求解路径910.考虑仓储空间结构中道路单向运行的约束，在A算法的基础上进行修正和改进。

　　A算法的基本流程是从起始点开始，根据估计代价选择性地扩展节点，直到将目标点扩展进来。关键是选择合适的评价函数：预估代价。g（n）代表从起始点到节点n的真实代价。/U）代表从节点n到目标点的估计代价。

　　考虑到仓库环境中所有的道路均为单行线，在单行线上扩展节点是单向且有序的，如所示，沿纵向道路L1从扩展的后继节点依次是、、n、几纟、几6、几了。

　　而其中n2、几3以及n5、n6是顺次扩展的固定流程，关键只在于在n4、节点处是否转向到横向道路褚、。为简化步骤，将A算法中以道路札、。以道路为节点减少了扩展次数，节省了时间。但是，路径的起点和终点不定是道路，还有可能是货架所在的存放空间。所以，需要加入特殊情况处理，将节点扩展分为3种情况：道路扩展道路、起点扩展道路、道路扩展终点。

　　当前节点是货架（起点），则可扩展的节点为相邻道路上的相邻位置。如（a）所示，黑色方块为货架浅色方块为可扩展的后续节点，节点n2即纵向道路L1，节点即横向道路H1.当前节点是道路，则可扩展的节点为与此道路交叉的且在道路前方的所有道路。如（b）所示，黑色方块为节点即纵向道路L1.浅色方块为可以扩展的节点，包括节点n2，横向道路褚；节点，横向道路H3；节点%，横向道路凡。

　　当前节点所在的道路与目标点相邻，则扩展当前点时可以加入目标点。如所示，当前点扩展后继节点即纵向道路心。纵向道路A与黑色方块目标点相邻。因此，可以扩展目标点。

　　以道路为基本节点，评价函数需要相应的调整。

　　除了基本的曼哈顿距离，还需要根据道路的方向加上相应的转向代价，如所示。

　　2.3加入时序A算法的路径规划如果预先知道每个时刻各机器人的具体位置，就可以在路径规划时预测并避免可能发生的道路冲突。为此，可以设置“时空运行地图”记录下每个机器人随时间运行的轨迹，把规划出的机器人轨迹记录下来形成一张“横-纵-时间”的三维地图，作为轨迹规划的。仍然基于A算法进行规划，但是将F、G、H的路径代价替换为时间代价。同时，在考虑运动到某个位置的路程的基础上，进一步加入因防止碰撞而增加的等待时间代价。由此，在路径规划中考虑了冲突延时，可以减少规划出的路径产生冲突。

　　由于道路的单向性，规划的先后顺序并不能够保证运行时的优先级。如果后规划的任务插入到先规划的任务道路前方，那么也只能由在道路后方的先规划的任务等待。这样就导致实际的轨迹跟原有的规划不完全符合。在这种情况下，任务仍然能够根据规划出来的路径完成，只是时间可能不合拍。如果继续根据有时间偏差的时空运行地图去规划新非规划的避让发生之后及时修正时空运行地图，使得地图与实际相符。

　　2.4碰撞预防已经为了避免可能发生的碰撞，设置独占点。

　　在某个时刻某个位置只能由一个移动机器人独自占用。同一时刻的其他机器人想要进入此位置必须等待。在实际系统中，这可以由安装在机器人上的超声波或红外传感器实现。在检测到与其他机器人距离小于警戒值的情况下，紧急刹车，防止碰撞。

　　3仿真。

　　□特殊规则约束下基于，算法的路径规划1=1加入时序A，：法的路径规划机器人数S/个0运行中发生的抢路冲突随机器人数量的增加而增加由和可以直观看出，在特殊道路规则的约束下，基于修正的A算法和加入时序的A算法这2种路径规划方法在完成任务运行总路程和耗费时间2个方面，表现接近。加入了时序的路径规划算法，降低了运行中发生的抢路次数，如0所示。但是，在仓储空间中道路单向运行设定的约束4结束语电子商务的迅猛发展为仓储物流带来了新的需求和挑战，本文对应用移动机器人技术发展新一代的智能仓储物流进行了探索。建立了个灵活可重构的仓储空间模型，制订了执行物流任务的移动机器人集群的运行规则，对智能调度和路径规划进行了方法研究和仿真验证。由此表明，基于移动机器人集群的自动化仓储技术有望在电子商务物流中起到颠覆性的关键作用。

　　本文中，订单是按照时间顺序发送给机器人中心控制系统的。将来，可以对订单分批优化之后再释放，能够更加有效地对机器人进行调度和规划。