多搜救机器人系统任务分配方法

摘要

本发明公开了一种多搜救机器人系统任务分配方法，目的是提供一种在可通信机器人数少于任务数的情况下仍能进行任务分配的方法。技术方案是先构建一个多搜救机器人系统并初始化，各个搜救机器人都有任务分配子系统；调整搜救机器人之间的通信关系，采用通信代理策略解决中心节点机器人可通信的机器人数少于任务数的问题；多搜救机器人系统计算执行任务的综合能力，中心节点机器人计算最佳任务分配方案，得到任务分配表；根据任务分配表将任务发送给负责执行的搜救机器人。采用本发明可解决负责任务分配的搜救机器人可通信机器人数少于任务数的问题；且本发明充分考虑机器人的综合能力对完成任务的效能的影响，提高了任务分配成功率。

主权项

一种多搜救机器人系统任务分配方法，其特征在于包括以下步骤：第一步：构建一个多搜救机器人系统，多搜救机器人系统由N个搜救机器人组成，N为正整数；搜救机器人之间以无线方式进行通信，各个搜救机器人有相同的任务分配子系统；搜救机器人R_f的任务分配子系统由四部分组成，1≤f≤N，f为整数：基础数据模块、通信模块、任务综合能力计算模块和任务分配模块；基础数据模块保存通信表、基本能力表、基本能力权重表、潜在能力表、潜在能力权重表、候选表、任务表、已参加任务分配表、冲突表和最大等待时间；通信表用于保存可以与R_f通信的搜救机器人，该表是一个一维表，有s行，0≤s≤N‑1，s为整数，每行记录与R₁通信的搜救机器人的通信地址；任务表保存需要分配的任务以及完成任务需要的基本能力，该表是一个二维表，有M行，表示有M个任务参加分配，M≥1；每行有K个域，K表示多搜救机器人系统具有的基本能力的数量，K≥1；表中每个元素为一个三元组(t_m,c_k,tc_mk)，其中t_m表示第m个任务，c_k表示第k种基本能力，tc_mk取值为0或1，0表示任务t_m不需要能力c_k，1表示任务t_m需要能力c_k，，1≤m≤M，1≤k≤K；基本能力表保存R_f的各个基本能力即完成任务必须的能力的大小，该表是一个二维表，有M'行，M'表示多搜救机器人系统能够完成的任务类型总数，每行有K个域，分别是完成不同任务的基本能力大小；基本能力权重表保存R_f的各个基本能力的权重，该表是一个二维表，有K行，每行有两个域，一个是基本能力名，一个是该能力的权重；潜在能力表保存R_f的各个潜在能力的大小，该表是一个二维表，有M'行，每行有K'个域，分别是完成不同任务的潜在能力大小，K'表示多搜救机器人系统具有的潜在能力的数量，K'≥1；潜在能力权重表保存R_f的各个潜在能力的权重，该表是一个二维表，有K'行，每行有两个域，一个是潜在能力名，一个是该能力的权重；候选表保存参加任务分配的搜救机器人的通信地址，该表是一个一维表，有s”行，0≤s"≤N‑1，s”为整数，每行记录参加任务分配的搜救机器人的通信地址；已参加任务分配表记录了R_f参加的任务分配，该表是一个一维表，记录了R_f参加的任务分配的总任务名；最大等待时间T表示搜救机器人R_f发出任务分配请求消息后等待反馈消息的时间；通信模块保存有消息表和已通信表；消息表保存R_f收到的消息，该表是一个一维表，每行记录R₁收到的消息；消息由五部分内容组成：标识、消息发送者、消息接收者、消息类型和消息内容；标识由消息来源机器人通信地址、总任务名和消息顺序依次组合而成；消息发送者记录发送消息的机器人的通信地址；消息接收者记录接收消息的机器人的通信地址；消息类型有六种取值：Request、Accept、Refuse、Taskrequirement、Taskutility和Taskallocated，Request表示消息用于请求建立通信网络；Accept表示消息发送者同意参加任务分配；Refuse表示消息发送者拒绝参加任务分配；Taskrequirement表示消息内容是任务需求描述；Taskutility表示消息内容是消息发送者执行任务的效用；Taskallocated表示消息内容是任务分配方案；消息内容是以字符串的形式记录的消息的内容；已通信表保存向R_f发送消息的搜救机器人的通信地址，该表是一个一维表，有s”'行，0≤s"'≤N‑1，s”'为整数，每行记录向R_f发送消息的搜救机器人的通信地址；如果通信模块从操作系统收到类型为Request的消息，通信模块修改消息表、已通信表、基础数据模块的通信表；如果通信模块从操作系统收到类型为Accept的消息，通信模块修改消息表、已通信表，并根据消息的发送者修改基础数据模块的候选表和通信表；如果通信模块从操作系统收到类型为Refuse的消息，通信模块修改消息表、已通信表，并根据消息的发送者修改基础数据模块的通信表。如果通信模块从操作系统收到类型为Taskrequirement的消息，通信模块修改消息表、已通信表，并修改基础数据模块的任务表。如果通信模块从操作系统收到类型为Taskutility的消息，通信模块修改消息表、已通信表，并修改任务综合能力计算模块的任务综合能力表。如果通信模块从操作系统收到类型为Taskallocated的消息，通信模块修改消息表、已通信表，并修改任务分配模块的任务分配表；如果通信模块从任务综合能力计算模块和任务分配模块收到消息，那么通信模块先修改消息表，然后通过操作系统将收到的消息发送出去；任务综合能力计算模块保存有任务综合能力表；任务综合能力表保存R_f完成不同任务的综合能力，该表是一个二维表，有s”行，每行有M域，是与任务名对应的完成任务的综合能力大小；任务综合能力计算模块根据从基础数据模块中获得的任务表、基本能力表、基本能力权重表、潜在能力表、潜在能力权重表计算R_f执行任务的综合能力，将R_f执行任务的综合能力保存在任务综合能力表中；如果R_f被分配任务，那么R_f的任务综合能力计算模块生成类型为Taskutility的消息发送给通信模块；任务分配模块保存有任务分配表，任务分配表是一个一维表，有M行，每行记录执行任务的机器人标识；任务分配模块根据任务综合能力计算模块的任务综合能力表计算最佳的任务分配方案，生成任务分配表，并生成标识为Taskallocated的消息，并将该消息发送给通信模块；在一次任务分配过程中，发起任务分配的机器人被称为中心节点机器人，设为R₁，系统中其他机器人为R_i,2≤i≤N，中心节点机器人R₁发起任务分配向R_i发送消息类型是Request的消息，R_i接收到Request类型的消息后对消息进行处理；第二步，多搜救机器人系统初始化：从用户提供的配置文件读入通信表、基本能力表、基本能力权重表、潜在能力表、潜在能力权重表和最大等待时间；第三步：调整搜救机器人之间的通信关系，采用通信代理策略来解决中心节点机器人可通信的机器人数少于任务数的问题：3.1R₁向R₁的通信表中的搜救机器人发送类型为Request消息，消息内容为总任务名的任务分配请求消息，并将任务分配请求消息加入R₁的消息表，然后R₁开始等待反馈消息并计时，所述总任务名是对所有待分配任务的代表；3.2在R₁等待反馈消息期间，R₁每过1秒判断一次等待时间是否大于T，如果大于则转到3.13，否则转3.2，仍然等待；如果R₁收到从R_i来的反馈消息，则转到3.10；同时，在R₁等待期间，如果R_i收到从R_j来的消息，1≤j≤N,j≠i，，转到3.3；3.3R_i遍历R_i的消息表，判断R_i的消息表中是否有与R₃收到的消息具有相同标识的消息，如果有，则转到3.2，否则将R_i收到的消息加入R_i的消息表，并将消息发送者R_j的通信地址加入已通信表，转3.4；3.4R_i向R_i的通信表中的所有搜救机器人R_i发送收到的消息；3.5R_i判断消息的类型，如果类型是Request，则转3.6，否则转3.2；3.6如果R_i的已参加任务分配表为空，则转到3.7；否则转到3.9；3.7R_i向R_j发送类型为Accept的消息，消息的内容是R_i的通信地址，R_i将总任务名填入R_i的已参加任务分配表；3.8R_i将R_i的任务综合能力表清空，并转3.2；3.9R_i向R_j发送类型为Refuse的消息，消息的内容是R_i的通信地址，并转3.2；3.10R₁遍历R₁的消息表，判断R₁的消息表是否有与R₁收到的反馈消息具有相同标识的消息，如果有，则转到3.2；否则，将R₁收到的消息加入到R₁的消息表，并将消息发送者的通信地址加入R₁的已通信表，转3.11；3.11如果R₁收到的反馈消息的类型是Request，则转到3.2，否则转到3.123.12如果R₁收到的反馈消息的类型是Accept，则将同意参加任务分配的搜救机器人通信地址加入R₁的候选表，转3.2；否则转3.2；3.13R₁用R₁的已通信表替换R₁的通信表，清空R₁的已通信表和任务综合能力表；3.14如果R₁的已参加任务分配表为空，则将R₁的通信地址加入R₁的候选表，将总任务名填入R₁的已参加任务分配表，转第四步；否则直接转第四步；第四步：多搜救机器人系统计算执行任务的综合能力，并将任务综合能力表发送给R₁：4.1R₁判断任务数是否大于R₁的候选表的行数，如果任务数大于R₁的候选表的行数，则转4.18，否则转到4.2；4.2R₁向R₁的通信表中的所有机器人发送类型为Taskrequirement、内容为任务表和总任务名的任务能力需求消息，并将任务能力需求消息加入R₁的消息表；4.3R₁开始等待R_i的反馈消息，在R₁等待期间，如果R_i收到消息，转4.7；如果R₁收到R_i的反馈消息，则转4.4；4.4R₁遍历R₁的消息表，判断R₁的消息表中是否有与R₁收到的消息具有相同标识的消息，有则转4.3，否则R₁将消息中的R_i的任务综合能力值填入R₁的任务综合能力表，并将R₁收到的消息加入R₁的消息表；4.5判断R₁的候选表中的所有搜救机器人是否都返回了消息类型是Taskutility的消息，如果是，转4.6，否则转4.3；4.6R₁检查R₁的已参加任务分配表，如果R₁的已参加任务分配表中有当前的总任务名，则转4.12，否则转第五步；4.7R_i遍历R_i的消息表，判断R_i收到的消息是否与R_i的消息表中的消息具有相同的标识，如果有，则转4.3，否则将R_i收到的消息加入到R_i的消息表；4.8R_i向R_i的通信表中所有搜救机器人发送R_i的收到的消息；4.9R_i判断消息的类型，如果类型是Taskrequirement，则转到4.10，否则转到4.3；4.10R_i根据R_i的已参加任务分配表判断R_i是否参加任务分配，如果是，则转4.12，否则转4.3；4.11R_i向发送Taskrequirement类型消息的发送者R_j发送类型为Taskutility的消息，消息内容是任务综合能力表，转4.3；4.12由于R₁与R_i计算综合任务能力的算法相同，以R_h代表R₁和R_i，R_h从类型为Taskrequirement的消息中获得任务表，1≤h≤N；4.13R_h遍历R_h的任务表，从表中取出第m个任务，1≤m≤M；4.14R_h根据公式(1)和(2)计算完成第m个任务的基本能力K_mh；$a_{mh}=\left\{\begin{array}{c}1,\underset{k=1}{\overset{K}{\Pi }}{\mathrm{tc}}_{mk}*{\mathrm{ec}}_{mhk}>0,{\mathrm{tc}}_{mk}\ne 0\\ 0,\underset{k=1}{\overset{K}{\Pi }}{\mathrm{tc}}_{mk}*{\mathrm{ec}}_{mhk}=0,{\mathrm{tc}}_{mk}\ne 0\\ 1,\underset{k=1}{\overset{K}{\Pi }}{\mathrm{tc}}_{mk}=0\end{array}\right.---\left(1\right)$$K_{mh}=\left(\underset{k=1}{\overset{K}{\Sigma }}{\omega }_{hk}{\mathrm{ec}}_{mhk}\right)*a_{mh}---\left(2\right)$其中a_mh＝1表示第h个搜救机器人能完成第m个任务，a_mh＝0表示不能完成第m个任务；ec_mhk表示第h个搜救机器人、完成第m个任务时具有的第k种基本能力的大小；ω_hk表示第h个搜救机器人的第k种基本能力的权重；4.15R_h根据公式(3)计算完成第m个任务的潜在能力G_mh$G_{mh}=\underset{k^{\prime }=1}{\overset{K^{\prime }}{\Sigma }}{{\omega }^{\prime }}_{{\mathrm{hk}}^{\prime }}{\mathrm{egc}}_{{\mathrm{mhk}}^{\prime }}---\left(3\right)$ω'_hk表示第h个搜救机器人第k种潜在能力的权重；egc_mhk表示第h个搜救机器人完成第m个任务具有的第k种潜在能力的大小；4.16R_h根据公式(4)计算完成第m个任务的综合能力Acap_mh，并将计算结果存入R_h的任务综合能力表；Acap_mh＝(ω"_h1*K_mh+ω"_h2*G_mh)*a_mh              (4)其中Acap_mh表示第h个机器人完成第m个任务的综合能力，ω"_h1表示第h个机器人的基本能力的权重，ω"_h2表示第h个机器人的潜在能力的权重；4.17如果R_h代表R₁，则转第五步；如果R_h代表R_i转4.11。4.18R₁终止任务分配；第五步：R₁计算最佳任务分配方案，算法的输入是R₁的任务综合能力表，算法输出是R₁的任务分配表；第六步：R₁根据R₁的任务分配表将任务发送给负责执行的搜救机器人：6.1R₁向R₁的通信表中的所有机器人发送类型为Taskallocated、内容为任务分配表的消息，并将R₁发送的类型为Taskallocated的消息加入R₁的消息表；6.2R₁检查R₁的任务分配表，如果R₁被分配了任务，则执行分配的任务，否则转6.7，同时如果R_i收到任务分配消息，则转到6.3：6.3R_i遍历R_i的消息表，判断R_i的消息表中是否有与R_i收到的消息具有相同标识的消息，如果有，则转6.8，否则将R_i收到的消息加入到R_i的消息表，转6.4；6.4R_i向R_i的通信表中所有搜救机器人发送R_i的收到的消息；6.5R_i判断R_i收到的消息的类型，如果类型是Taskallocated，则转到6.6，否则转6.7；6.6R_i根据R_i的已参加任务分配表判断R_i是否参加任务分配，如果R_i参加任务分配，则从R_i收到的类型为Taskallocated的消息中读出任务分配表，并执行分配的任务；6.7R₁退出任务分配子系统。6.8R_i不对收到的消息进行响应。