[發明專利]一種面向多機器人充電策略的分布式求解方法

在審

• 申請號: 202010723028.3
• 申請日: 2020-07-24
• 公開（公告）號: CN112070341A
• 公開（公告）日: 2020-12-11
• 發明（設計）人: 侯士偉;林志赟;王博;韓志敏
• 申請（專利權）人: 杭州電子科技大學
• 主分類號: G06Q10/06
• 分類號: G06Q10/06;G06Q10/04;G06Q50/06
• 代理公司: 杭州君度專利代理事務所(特殊普通合伙) 33240
• 代理人: 楊舟濤

本發明公開了一種面向多機器人充電策略的分布式求解方法，該方法以極小化所有要充電的機器人總耗時為目標，總耗時包括行駛時間、排隊時間和充電時間。每個機器人在全局信息未知的情況下，利用自己獲取到的通信范圍內鄰居機器人的位置、剩余電量信息，以及比自己優先級高的鄰居機器人的充電策略等信息，基于自己充電耗時最少的原則，選擇剩余電量容許可達的充電站，來實現近似最優解。本發明解決了多機器人在充電站擁堵充電的問題，有效縮短了整個多機器人充電系統的充電時間，大大的提高了機器人的充電效率。

技術領域

本發明屬于分布式系統多機器人資源調度技術領域，尤其涉及一種面向多機器人充電策略的分布式求解方法。

背景技術

自動導引運輸車是以電力驅動，能夠按照要求行駛到指定地點，并在與其他設備完成交互后離開。由于機器人具有自動化程度高、可靠性好、適應性強等特點，使其在自動化倉儲領域得到廣泛應用。為提高自動化倉儲領域機器人的有限充電站的使用效率，多機器人如何分配有限充電站是十分關鍵的技術問題。

從機器人的本質來講，其為電動汽車，必須在工作過程中進行充電，但自動化倉儲的面積有限且十分寶貴，而機器人充電站及其配套設施需要較大的占地面積，因此為每一個機器人配備一個充電站顯然是浪費資源和成本的，機器人在充電過程會增加額外行駛時間，并且機器人為無人駕駛，假設有一臺機器人由于電池電量耗盡在路面停工就會影響整個系統中所有機器人的路徑規劃，堵塞越來越多的機器人，造成整個倉儲的交通癱瘓，所以一旦出現機器人電量不足而停工的情況，倉儲將需要投入大量的人力成本和時間成本，因此在有限充電站的倉儲中要保持每一輛機器人都必須有電而且維持在一個相對穩定的水平是重要的，并且在整個充電過程中，該機器人無法被調度，直至充電完成后才能再次投入使用。

發明內容

本發明主要優化了多機器人充電調度問題，提高了機器人的充電效率，降低了整個多機器人充電系統的充電時間，以便盡早的恢復機器人的工作。針對多機器人的充電調度問題，本發明讓機器人在時間的約束下，使每一個要充電機器人都能分配一個最優的充電站，從而整個系統的充電時間最短。考慮到有n個需要充電的移動機器人R＝{r₁，r₂，…，r_n}，其中r_i是第i個機器人的編號；有m個充電站S＝{s₁，s₂，…，s_m}，其中s_j是第j個充電站的編號；假設充電站是固定的，系統中的所有的機器人都知道充電站的位置；用t_ij表示機器人r_i到充電站s_j的行駛時間，用表示充機器人r_i在充電站s_j的充電時間，用q_ij表示機器人r_i在充電站s_j的排隊時間。

本發明的目的是找到一個充電站的分配方案A，使得系統中所有要充電的機器人的充電時間最短，分配方案A是R到S的一個映射：{r₁，r₂，…，r_n}→{s₁，s₂，…，s_m}。A的解空間是所有機器人所選擇的充電站構成的集合，用表示，其中U_i是機器人r_i的可達充電站集合。U的元素對應一個分配方案A＝[A(1)，…，A(n)]，其中A(i)＝j，i＝1，…，n，表示機器人r_i選擇充電站s_j。對于每一個分配方案A都有一個成本函數定義如下：

本發明的目標是找到一個最優的分配方案A^*滿足下式：