[發明專利]一種細粒度的多機器人協作系統任務分配算法

有效

• 申請號: 201210309048.1
• 申請日: 2012-08-27
• 公開（公告）號: CN102831319A
• 公開（公告）日: 2012-12-19
• 發明（設計）人: 石志國;涂俊;張巧;張曉萌;胡開航
• 申請（專利權）人: 北京科技大學
• 主分類號: G06F19/00
• 分類號: G06F19/00
• 代理公司: 北京金智普華知識產權代理有限公司 11401
• 代理人: 皋吉甫

技術領域

本發明屬于多機器人協作系統領域，涉及一種基于機器人自身聲望和依賴于細粒度時間模型的多機器人任務分配機制。

背景技術

任務規劃問題包括任務分解和任務分配兩個方面，而任務分解又可以分為可分解任務和不可分解任務兩種類型。目前，多機器人系統的任務規劃問題的研究主要集中在任務分配問題，而對任務分解問題的研究工作則相對較少。多機器人任務分配問題早期的很多研究都是基于合同網協議的，通過一個中央節點對其它智能體能力信息的了解來實現任務的分配。后來的基于市場經濟任務分配方法來源于早期的合同網方法，已經被用于協調多機器人系統完成環境探索、機器人足球、救援等很多應用問題.隨后有人改進了聯合拍賣方法，提出一種聯合競價的任務分配方法。對于異構多機器人系統，有人則提出了一種ASyMTRe任務解決方法：各個機器人之間通過傳感器、執行器和行為的組合來完成搬運和推箱子等任務.McLurkin總結了4種機器人任務分配的分布式算法：隨機分配，根據任務的權重隨機算法將任務分配給機器人；順序分配，按照一定的順序給機器人分配任務；同時分配，同時產生網絡中所有機器人的任務列表；基于樹的分配算法介于順序分配和同時分配之間。

這些算法很好地解決了任務分配的問題，但是在任務撤銷、銷毀方面還有所欠缺，比如某個機器人失效了，如何才能及時收回分配的任務？

發明內容

任務分配一般分為直接分配和委托分配兩種類別，直接分配是指直接將任務分配給合作的機器人，但是當機器人不能完成所分配的任務時，可以將任務委托給其他有能力的機器人，即為委托分配。為了能夠有效的控制和管理任務，加入了周期性約束機制，當任務在規定的時間沒有完成的話，這個任務分配會被撤銷，從而提高系統的整體性能。同時本文提出的任務分配方法加入了聲望系統，任務的分配是根據機器人的聲望來完成的，主要包括三個模塊：周期時間機制，系統協作框架和基于聲望的協作策略。

1周期時間機制

將周期時間包括兩個部分：有效時間段和周期表達式，其中有效時間段表示周期時間的范圍。

定義1周期時間是一個2元組（[t_begin，t_end],P），其中P是一個周期表達式其中C_d是日歷，O₁=O_all，O_all表示從起始點到O₁的總時間段，O_i∈2^IN∪{O_all}，[t_begin,t_end]是一個時間段，表示作用于P時間點的上、下界。

定義2?(函數F_Sol()）令t為一個時間點，P_t=（[t_begin，t_end],P），其中[t_begin，t_end]是一個時間段，P為一個周期表達式。則t∈F_Sol(P_t)，當且僅當存在t∈∏(P)，且t∈[t_begin，t_end]。在周期表達式中，前的部分表示該表達式表示的時間段的起點集合，而后面部分表示每個時間段的長度。

2協作系統框架

定義3?（機器人主體）機器人R或者M是由一個四元組<κ，τ,ε,Res>組成，其中κ表示有限的本體集；τ表示有限的屬性集合；ε表示一個可以合法頒發證書的有限集；Res表示的是資源的有限集，指可用的文件資源或者是計算能力。

定義4?（委托協作模型框架）F_coop表示為6元組(s,x,o,g,l,k_own)，其中，s∈R是任務的接受者，x∈P是被授予的執行任務的權限，o∈O是被訪問的機器人的目標任務集合，g∈R是任務的授予者，l∈{1,0}表示接受者s能(1)/否(0)對所獲得的任務再進行傳播與分配，k_own∈{1,0}表示任務授予者g是否為任務o的所有者。由任務分配組成的集合稱為分配集，記為S_DS。函數F_xo(F_coop)和F_sxo(F_coop)分別返回(x,o)元組和(s,x,o)元組。