Logistics robot dynamic task allocation method and system

具体实施方式

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

智能仓储系统包括中央控制机构、货架、物流机器人、拣选站台和存储区，所述中央控制机构用于控制所述物流机器人，所述货架用于存放货物，所述货架之间分布有拣选通道，方便所述物流机器人移动，所述物流机器人用于接收所述中央控制机构的指令将所述货架上待出库货物搬运到所述拣选站台，搬运任务的执行载体，所述物流机器人自身装有传感器来获得必要的环境和自身位姿信息，所述物流机器人之间可以相互通信，所述物流机器人在智能仓储系统中只能沿前、后、左、右四个方向移动，所述物流机器人进行匀速移动；所述存储区用于存放所述物流机器人，当中央控制机构中没有任务可执行时，物流机器人才会返回存储区，否则物流机器人执行完当前任务之后继续执行下一个任务，直到中央控制机构中任务全部被完成。

如图1所示，本发明实施例的物流机器人动态任务分配方法，包括以下步骤：

S1：获取任务点和物流机器人的信息。

在本发明的一个实施例中，所述任务点的信息包括任务点区域地理信息和任务点初始位置信息；所述物流机器人的信息包括物流机器人初始位置信息。

S2：根据获取的任务点信息和物流机器人信息采用就近分配原则对物流机器人进行任务初始分配。

在本发明的一个实施例中，采用就近分配原则对物流机器人进行任务初始分配方法为：

步骤1：创建整形二维数组C和布尔型二维数组B。

步骤2：通过栅格图法创建智能仓储环境模型。

将物流机器人的作业环境用形状大小相同的栅格为单位来进行建模，作业环境中的障碍物以不同标记的栅格来作为区分描述。如图2所示，图中0表示自由栅格，即物流机器人允许通过的路径；1表示障碍栅格，即物流机器人不能通过的障碍物。

步骤3：计算每个物流机器人和各个任务点的距离，物流机器人用i表示，任务点用j表示，每个物流机器人i和各个任务点j的距离用C_ij表示，C_ij放入到整形二维数组C中的相应位置，物流机器人i的位置在栅格图中的坐标为(x_i，y_i)，任务点位置在栅格图中的坐标为(x_j，y_j)，物流机器人i和任务点j之间的距离采用曼哈顿距离计算，曼哈顿距离为两点之间横向距离加上纵向之间的距离，即：

C_ij＝D(i,j)＝x_i-x_j+y_i-y_j

设定直线走一个栅格的距离的代价用K来表示，则初始物流机器人与任务点之间的距离为：

h(cur)＝K×(abs(curx-goal.x)+abs(cury-goal.y))

式中，cur代表物流机器人的当前位置，goal代表任务点位置。

步骤4：从计算得到的每个物流机器人i和各个任务点j的距离中找到最小的c_ij，并将任务点j分配给对应的物流机器人i，并将数组B中第i行和第j列布尔值置B_ij为TRUE；

步骤4：继续寻找整形二维数组C中最小值。

在本发明实施例中，每次比较大小之前，都要判断相应B位置是否为TRUE，如果为TRUE则不进行比较判断。若所有的物流机器人都得到相应的任务则结束，否则继续寻找整形二维数组C中最小值。

S3：根据任务密度对物流机器人进行任务再分配。

在本发明实施例中，当物流机器人到达任务点时为物流机器人分配下一个任务点，同时该当前物流机器人加入到待分配机器人列表中。

在本发明的一个实施例中，根据任务密度对物流机器人进行任务再分配方法为：如果待分配机器人列表中只有当前物流机器人一个，且无任务分配时，则当前物流机器人的下一个任务点设置为空，当前物流机器人完成当前任务后从任务点返回存储区等待任务分配；如果待分配机器人列表中物流机器人数量不为零且无任务分配时，同时待分配机器人列表中的其它物流机器人的下一任务点也为空时，则当前物流机器人的任务点也为空，否则寻找距离当前物流机器人最近的已被分配但可被再分配的任务点，采用A*算法计算当前物流机器人到该任务点的距离，如果当前物流机器人距离该任务点的距离更短，则将该任务点与原有物流机器人解除绑定，并将该任务点再分配给当前物流机器人进行绑定，并为原有物流机器人重新分配新的任务点；如果有任务可分配时，根据当前任务两边的任务密度进行分配。

在本发明实施例中，物流机器人正在执行的任务点是不变的，也就是不能再分配给其它物流机器人。

在本发明的一个实施例中，根据当前任务两边的任务密度进行分配的方法为：

计算物流机器人当前正在执行的任务点左右两边的任务密度，其中，任务密度＝未分配任务数量/物流机器人数量。具体地，通过比较分别得到两边未分配任务数量和物流机器人数量，然后用任务数量除以物流机器人数量。

如果物流机器人数量为0，任务数量不为0，则任务密度为无穷大，从密度无穷大的一边选择最近未完成任务点作为相应物流机器人的下一任务点；如果物流机器人数量不为0，任务数量为0，待分配机器人列表中物流机器人有任务分配时，则任务密度为0，通过A*算法计算其他物流机器人到已分配给原有物流机器人尚未执行的任务点的距离，如果其他物流机器人距离任务点的距离更短，则将该任务点与原有物流机器人解除绑定，并将该任务点再分配给距离该任务点最近的物流机器人；如果物流机器人和任务数量均不为0，计算两边任务密度的比值，如果比值大于设定的阈值时，通过A*算法计算其他物流机器人到已分配给原有物流机器人尚未执行的任务点的距离，如果其他物流机器人距离任务点的距离更短，则将该任务点与原有物流机器人解除绑定，并将该任务点再分配给距离该任务点最近的物流机器人。

在本发明的一个实施例中，如果任务点被标记为加急任务时，优先分配给无任务的物流机器人进行处理，如果物流机器人均有任务执行时，通过A*算法计算分配给距离加急的任务点最近的待分配任务机器人列表中的物流机器人执行。

综上所述，根据本发明实施例的物流机器人动态任务分配方法，通过栅格图法创建智能仓储环境模型，结合A*算法对多机器人进行路径规划，根据任务密度对动态任务进行再分配，能够提高任务完成效率。

如图3所示，基于上述实施例的物流机器人动态任务分配方法，本发明还提出一种物流机器人动态任务分配系统。

本发明实施例的物流机器人动态任务分配系统，包括获取模块，获取模块用于获取任务点信息和物流机器人信息；任务初始分配模块，所述任务初始分配模块用于多物流机器人任务初始分配；任务再分配模块，任务再分配模块用于根据任务密度对物流机器人进行任务再分配。

在本发明的一个实施例中，所述任务点的信息包括任务点区域地理信息和任务点初始位置信息；所述物流机器人的信息包括物流机器人初始位置信息。

在本发明的一个实施例中，采用就近分配原则对物流机器人进行任务初始分配方法为：

步骤1：创建整形二维数组C和布尔型二维数组B。

步骤2：通过栅格图法创建智能仓储环境模型。

将物流机器人的作业环境用形状大小相同的栅格为单位来进行建模，作业环境中的障碍物以不同标记的栅格来作为区分描述。如图2所示，图中0表示自由栅格，即物流机器人允许通过的路径；1表示障碍栅格，即物流机器人不能通过的障碍物。

步骤3：计算每个物流机器人和各个任务点的距离，物流机器人用i表示，任务点用j表示，每个物流机器人i和各个任务点j的距离用C_ij表示，C_ij放入到整形二维数组C中的相应位置，物流机器人i的位置在栅格图中的坐标为(x_i，y_i)，任务点位置在栅格图中的坐标为(x_j，y_j)，物流机器人i和任务点j之间的距离采用曼哈顿距离计算，曼哈顿距离为两点之间横向距离加上纵向之间的距离，即：

C_ij＝D(i,j)＝x_i-x_j+y_i-y_j

设定直线走一个栅格的距离的代价用K来表示，则初始物流机器人与任务点之间的距离为：

h(cur)＝K×(abs(curx-goal.x)+abs(cury-goal.y))

式中，cur代表物流机器人的当前位置，goal代表任务点位置。

步骤4：从计算得到的每个物流机器人i和各个任务点j的距离中找到最小的c_ij，并将任务点j分配给对应的物流机器人i，并将数组B中第i行和第j列布尔值置B_ij为TRUE；

步骤4：继续寻找整形二维数组C中最小值。

在本发明实施例中，每次比较大小之前，都要判断相应B位置是否为TRUE，如果为TRUE则不进行比较判断。若所有的物流机器人都得到相应的任务则结束，否则继续寻找整形二维数组C中最小值。

在本发明实施例中，当物流机器人到达任务点时为物流机器人分配下一个任务点，同时该当前物流机器人加入到待分配机器人列表中。

在本发明的一个实施例中，根据任务密度对物流机器人进行任务再分配方法为：如果待分配机器人列表中只有当前物流机器人一个，且无任务分配时，则当前物流机器人的下一个任务点设置为空，当前物流机器人完成当前任务后从任务点返回存储区等待任务分配；如果待分配机器人列表中物流机器人数量不为零且无任务分配时，同时待分配机器人列表中的其它物流机器人的下一任务点也为空时，则当前物流机器人的任务点也为空，否则寻找距离当前物流机器人最近的已被分配但可被再分配的任务点，采用A*算法计算当前物流机器人到该任务点的距离，如果当前物流机器人距离该任务点的距离更短，则将该任务点与原有物流机器人解除绑定，并将该任务点再分配给当前物流机器人进行绑定，并为原有物流机器人重新分配新的任务点；如果有任务可分配时，根据当前任务两边的任务密度进行分配。

在本发明实施例中，物流机器人正在执行的任务点是不变的，也就是不能再分配给其它物流机器人。

在本发明的一个实施例中，根据当前任务两边的任务密度进行分配的方法为：

计算物流机器人当前正在执行的任务点左右两边的任务密度，其中，任务密度＝未分配任务数量/物流机器人数量。具体地，通过比较分别得到两边未分配任务数量和物流机器人数量，然后用任务数量除以物流机器人数量。

如果物流机器人数量为0，任务数量不为0，则任务密度为无穷大，从密度无穷大的一边选择最近未完成任务点作为相应物流机器人的下一任务点；如果物流机器人数量不为0，任务数量为0，待分配机器人列表中物流机器人有任务分配时，则任务密度为0，通过A*算法计算其他物流机器人到已分配给原有物流机器人尚未执行的任务点的距离，如果其他物流机器人距离任务点的距离更短，则将该任务点与原有物流机器人解除绑定，并将该任务点再分配给距离该任务点最近的物流机器人；如果物流机器人和任务数量均不为0，计算两边任务密度的比值，如果比值大于设定的阈值时，通过A*算法计算其他物流机器人到已分配给原有物流机器人尚未执行的任务点的距离，如果其他物流机器人距离任务点的距离更短，则将该任务点与原有物流机器人解除绑定，并将该任务点再分配给距离该任务点最近的物流机器人。

在本发明的一个实施例中，如果任务点被标记为加急任务时，优先分配给无任务的物流机器人进行处理，如果物流机器人均有任务执行时，通过A*算法计算分配给距离加急的任务点最近的待分配任务机器人列表中的物流机器人执行。

综上所述，根据本发明实施例的物流机器人动态任务分配系统，通过栅格图法创建智能仓储环境模型，结合A*算法对多机器人进行路径规划，根据任务密度对动态任务进行再分配，能够提高任务完成效率。

在本发明的描述中，术语“第一”、“第二”仅用于描述目的，而不能理解为指示或暗示相对重要性或者隐含指明所指示的技术特征的数量。由此，限定有“第一”、“第二”的特征可以明示或者隐含地包括一个或者更多个该特征。“多个”的含义是两个或两个以上，除非另有明确具体的限定。

在本发明中，除非另有明确的规定和限定，术语“安装”、“相连”、“连接”、“固定”等术语应做广义理解，例如，可以是固定连接，也可以是可拆卸连接，或成一体；可以是机械连接，也可以是电连接；可以是直接相连，也可以通过中间媒介间接相连，可以是两个元件内部的连通或两个元件的相互作用关系。对于本领域的普通技术人员而言，可以根据具体情况理解上述术语在本发明中的具体含义。

在本发明中，除非另有明确的规定和限定，第一特征在第二特征“上”或“下”可以是第一和第二特征直接接触，或第一和第二特征通过中间媒介间接接触。而且，第一特征在第二特征“之上”、“上方”和“上面”可是第一特征在第二特征正上方或斜上方，或仅仅表示第一特征水平高度高于第二特征。第一特征在第二特征“之下”、“下方”和“下面”可以是第一特征在第二特征正下方或斜下方，或仅仅表示第一特征水平高度小于第二特征。

在本说明书的描述中，参考术语“一个实施例”、“一些实施例”、“示例”、“具体示例”、或“一些示例”等的描述意指结合该实施例或示例描述的具体特征、结构、材料或者特点包含于本发明的至少一个实施例或示例中。在本说明书中，对上述术语的示意性表述不必针对相同的实施例或示例。而且，描述的具体特征、结构、材料或者特点可以在任一个或多个实施例或示例中以合适的方式结合。此外，在不相互矛盾的情况下，本领域的技术人员可以将本说明书中描述的不同实施例或示例以及不同实施例或示例的特征进行结合和组合。

流程图中或在此以其他方式描述的任何过程或方法描述可以被理解为，表示包括一个或更多个用于实现特定逻辑功能或过程的步骤的可执行指令的代码的模块、片段或部分，并且本发明的优选实施方式的范围包括另外的实现，其中可以不按所示出或讨论的顺序，包括根据所涉及的功能按基本同时的方式或按相反的顺序，来执行功能，这应被本发明的实施例所属技术领域的技术人员所理解。

在流程图中表示或在此以其他方式描述的逻辑和/或步骤，例如，可以被认为是用于实现逻辑功能的可执行指令的定序列表，可以具体实现在任何计算机可读介质中，以供指令执行系统、装置或设备(如基于计算机的系统、包括处理器的系统或其他可以从指令执行系统、装置或设备取指令并执行指令的系统)使用，或结合这些指令执行系统、装置或设备而使用。就本说明书而言，“计算机可读介质”可以是任何可以包含、存储、通信、传播或传输程序以供指令执行系统、装置或设备或结合这些指令执行系统、装置或设备而使用的装置。计算机可读介质的更具体的示例(非穷尽性列表)包括以下：具有一个或多个布线的电连接部(电子装置)，便携式计算机盘盒(磁装置)，随机存取存储器(RAM)，只读存储器(ROM)，可擦除可编辑只读存储器(EPROM或闪速存储器)，光纤装置，以及便携式光盘只读存储器(CDROM)。另外，计算机可读介质甚至可以是可在其上打印所述程序的纸或其他合适的介质，因为可以例如通过对纸或其他介质进行光学扫描，接着进行编辑、解译或必要时以其他合适方式进行处理来以电子方式获得所述程序，然后将其存储在计算机存储器中。

应当理解，本发明的各部分可以用硬件、软件、固件或它们的组合来实现。在上述实施方式中，多个步骤或方法可以用存储在存储器中且由合适的指令执行系统执行的软件或固件来实现。例如，如果用硬件来实现，和在另一实施方式中一样，可用本领域公知的下列技术中的任一项或他们的组合来实现：具有用于对数据信号实现逻辑功能的逻辑门电路的离散逻辑电路，具有合适的组合逻辑门电路的专用集成电路，可编程门阵列(PGA)，现场可编程门阵列(FPGA)等。

本技术领域的普通技术人员可以理解实现上述实施例方法携带的全部或部分步骤是可以通过程序来指令相关的硬件完成，所述的程序可以存储于一种计算机可读存储介质中，该程序在执行时，包括方法实施例的步骤之一或其组合。

此外，在本发明各个实施例中的各功能单元可以集成在一个处理模块中，也可以是各个单元单独物理存在，也可以两个或两个以上单元集成在一个模块中。上述集成的模块既可以采用硬件的形式实现，也可以采用软件功能模块的形式实现。所述集成的模块如果以软件功能模块的形式实现并作为独立的产品销售或使用时，也可以存储在一个计算机可读取存储介质中。

尽管上面已经示出和描述了本发明的实施例，可以理解的是，上述实施例是示例性的，不能理解为对本发明的限制，本领域的普通技术人员在本发明的范围内可以对上述实施例进行变化、修改、替换和变型。