电商仓库拣货机器人路径规划与实现

随着电子商务行业的迅速发展, 网络购物成为一种潮流, 很大一部分人热衷于通过网络购买需要的东西。在这样的发展趋势下, 人们对物流服务也越来越重视, 而运转效率就是物流服务的一个重要指标。对于普通客户来讲, 速度是评价服务的重要标准之一。

仓库作为货物运转的节点, 对货物运转有着至关重要的影响。现如今大多数的仓库自动化水平还比较低, 订单的拣选基本依靠劳动力完成, 这样一来效率低, 二来错误率高, 用户体验较差。并且现今人力成本上升, 传统的工作方式早已不能满足社会需求^[1]。

为解决这样的窘境, 各大运营商纷纷在机器人方面加大投入研发, 比较典型的如亚马逊的Kiva机器人、阿里巴巴的“曹操”机器人、京东的六轴机械臂等, 目前已有部分仓库将机器人运用到现实的作业中。在电商仓库配送中心的搬运成本中, 拣货的搬运成本约占90%, 与拣货直接相关的人力占50%。拣货时间约占整个配送中心操作时间的30%-40%。在配送过程中, 拣货是整个配送中心操作系统的核心, 合理规划与管理拣货过程, 对配送中心工作效率的提高具有决定性的影响。

本文就提高电商仓库配送中心工作效率提出拣货机器人路径优化方法, 就路径优化中的最短路径及多机器人之间的避障进行研究并建模得出结果。

合理的仓库地图设计有利于仓库存储物资的合理安排, 能够降低仓库工作人员的工作量, 减少不必要的重复劳动。仓库路径、货架的合理布局有利于通道的畅通, 确保仓库工作人员和机器人的通行安全。地图的设计应根据货物种类、障碍物位置、仓库规模等因素做一些合理的规划。

图文件使用Tiled Map辅助绘制, 实验根据货架位置及障碍物位置做一个简单的路径设计, 具体仓库地图结构如图1所示, 其中包括货架位置、障碍物、路径以及路径的交叉点。为方便机器人与服务器的信息沟通, 每个交叉点处会设置二维码以表示该交叉点在地图上的坐标位置, 由于交叉点为一个正方形, 这里以正方形左上角位置为交叉点坐标并设置相应序号。图文件完成同时生成tmx文件, JAVA语言读取文件生成有效信息。这里的有效信息主要是路径和路径交叉点的相关描述, 包括序号、长度、坐标等^[2]。如:

以上是交叉点描述信息以及交叉点信息的二维码描述方式, 其中id表示的信息包含该点的所在图层、序号及其坐标。二维码信息表示该点坐标。

以上是路径描述信息, id表示该路径起点与终点坐标, point表示起点与终点信息。

下面根据路径与交叉点的关系生成矩阵, 矩阵的行和列分别为两个点的序号。当图中两点可通过某条路径相连接, 则在矩阵相对应的位置输出1, 不能连接的输出0。这样最后输出一个m×m的矩阵, 矩阵可直观的表示出图信息。第二个矩阵与第一个矩阵类似, 两点不能连接的输出0, 可通过某条路径连接的输出该路径的长度。至此地图信息对应的矩阵初步形成。

机器人每到一个节点扫描到二维码信息, 同时向服务器发送实时位置, 服务器根据此信息确定机器人接下来的路径同时向机器人发送行动指令。为避免多机器人路径冲突, 当机器人向服务器发送定点位置时, 将下一步运行的路径置∞, 即断开该路径, 这样避免同时工作的机器人路过此路径, 实现多机器人之间的避障。

常见的数据库类型有Oracle、SQL Server、My SQL等。综合数据容量、价格以及操作难易程度等因素, 本次实验选择了My SQL数据库。

JSP通过Connection接口访问数据库, java.sql.Satatement接口用来执行静态的SQL语句, java.sql.Prepared Satatement接口执行动态的SQL语句。

实验中数据库新建两个表。表1存储各类商品的拣货点等信息。当订单产生时得到一个订单中所有商品的名称, 服务器根据商品名称从数据库获得对应取货点, 将这些取货点加入到一个工作进程中, 并发布给机器人开始工作。表2存储机器人序号、机器人所在位置的坐标以及该坐标对应交叉点的序号。当机器人运行到某交叉点扫描到二维码, 将自身序号以及二维码包含的信息输入到数据库, 当二维码显示的点序号与取货点的序号一致, 则机器人执行取货行为。

求最短路径的算法有很多, 常用的方法有人工势场法^[3]、A*算法^[4]等, 都是针对简单的点到点的路径规划任务。本次设计选用Dijkstra算法与最邻近算法相结合, 以整体时间最优为目标。

Dijkstra算法首先是得到起点V₀到其他各顶点距离, V₀->V₀的权值为0, 当V₀与V_i可连接, 其权值为V₀->V_i的长度, 当V₀与V_i不可连接, V₀->V_i权值为∞, 这样可得到一个描绘路径权值的矩阵。Dijkstra算法适合运用于求解单源最短路径的问题, 可得到到其他各顶点的最短路径, 而订单需求的节点可能是多个, 所以单纯使用Dijkstra算法不能满足需求^[5]。最邻近算法, 即优先选择前往与当前所在点最接近的点, 然后以该点为起点前往下一个点, 最后得到一个最接近于最短路径的答案。

针对电商仓库的特点, 单个机器人无法满足工作的需求, 所以还有一个重点问题, 多机器人同时工作时要如何分配才能不发生冲突。本文采取的避障方式有两种:一种是当某条路径正在被占用时, 更改其对应权值为∞, 下一个订单对应的路径规划就会避开这两条路径, 直至被占用路径任务完成, 释放被占用路径, 更改权值为原来的长度数值。第二种是等待, 当路径被占用, 下一个需要经过该路径的机器人可选择等待, 等前一个机器人离开本路径后再进入该路径。如有多个机器人同时等待同一个路径, 以订单产生时间设置优先级, 先产生的订单优先级较高。当冲突发生时, 通过预估前一个任务完成释放路径的时间及下一个任务的等待时间, 计算绕行耗费时间即绕行比原路径多花的时间, 并对等待时间与绕行时间进行比较, 选择时间较短的方式。

整个运行过程为:首先服务器获得需要拣取的商品名称, 然后从数据库获取各商品对应拣货点, 即需要到达的各顶点, 将各顶点带入算法中得到经过多点的最短路径, 到此一个订单的初步路径规划工作完成。运行过程中, 如规划的某条路径正在被占用, 则重新规划接下来的路径, 不断更新, 确保不会产生碰撞或者堵塞。

首先读取地图信息, 生成矩阵。然后将矩阵带入算法, 同时输入任务点, 获得多点之间的最短路径。最后向机器人发送任务要求, 机器人执行任务过程中经过交叉点时读取对应二维码信息, 与服务器的信息交互, 实现避障, 即多个任务同时进行, 路径之间无交叉点。

本文的地图文件是针对电商仓库设计的。目的在于确定机器人位置与离拣货货架最近的路径上的点, 得到机器人到拣货点最短线路的计算。确定了仓库中的多个点后, 根据仓库地图描述文件计算多点之间的最短线路, 并能够实现避障, 机器人之间不会碰撞且不会导致道路堵塞。任务起点为机器人休息区或者存放点, 终点为订单打包区, 这个根据需求进行设计, 存入地图信息。其它节点根据订单所需货物, 通过数据库信息获取货物所在货架信息。根据多点信息及描述文件计算最短线路的步骤如下:

(1) 确定起点、取货点及仓库地图描述文件。

(2) 定义图的邻接矩阵、图的点集合以及路径集合。

(3) 解析仓库描述文件, 初始化图的点集和边集。

(4) 根据订单确定访问点, 带入算法得到最短路径。

(5) 服务器向机器人发送指令, 机器人路过顶点扫描到二维码, 向服务器发送实时位置。

(6) 服务器根据机器人实时位置信息实时更新道路实现避障, 在某条路径被访问时, 下一个任务避开该路径, 以及规划下一条路径, 找到另一条最短路径。

实验初步设置两个任务实现避障。即实现图1中点到点之间的最短路径的获取, 当两个任务同时进行时, 后一个任务不会同时与前一个任务在同一路径重合, 避免碰撞的情况发生。

实验过程首先根据Tiled Map获得的描述文件, 使用My Eclipse软件读取描述文件信息获得路径及交叉点关系的矩阵。然后使用软件进行仿真, 将矩阵带入得到带权图 (Graph) ^[6]。最后输入任务, 通过Dijkstra算法获得最短路径, 经过对算法的改进实现避障。

任务一, 2->50, 任务二, 2->49。独自运行时, 实验得出结果, 任务一生成路径如图2所示, 经过节点2、9、50, 由于有1个转弯, 这里设置速度, 一个单位长度需1s, 转弯需多增加2s, 总任务时间为90s。任务二生成路径如图3所示, 经过节点2、9、49, 也有1个转弯, 总任务时间为90s。同时运行时, 由于任务一优先级高, 路径不发生改变, 任务二为了避免与任务一产生冲突, 可选择绕行或者等待。这里可以预估任务一到达节点9的时间, 2->9距离56, 则需要56s, 所以预估56s到达节点9, 即任务二需等待56s。如果绕行经过的路径节点修改为2、45、1、8、49, 有2个转弯, 总任务时间变为156s, 比之前规划多了66s。相较于绕行, 等待反而快了10s, 所以这里选择了等待, 生成路径如图4所示, 这样的规划避免了两个机器人工作途中碰撞的可能性。

从实验结果可直观的看到最短路径, 多个任务时会避免碰撞或者拥堵。

本文实现了对订单路径规划的方案制定, 规划了整个流程, 并模拟完成了过程中最短路径的获取及机器人之间的避障。但是对路径规划算法的优化还不够完善, 还有其他约束条件以及可能产生碰撞的情况没有考虑完全, 后期还需考虑, 以达到更加高效、实时、准确的实现路径规划及避障。并且本文实现的仅仅是路径方面的优化避障, 并未涉及机器人设计, 后期会涉及到机器人主芯片的设计, 初步考虑使用Android系统的嵌入式电路板实现机器人与服务器信息交流。至于机器人取货等行为有待进一步开发设计。

相信随着电商行业的不断发展, 电商仓库工作量会越来越大, 如何简化工作流程, 节约工作时间愈加变成一个重点问题, 未来机器人的使用也会越来越普及。