使用多個機器人對環境的發現和監視的製作方法

2023-05-08 17:58:16

使用多個機器人對環境的發現和監視的製作方法
【專利摘要】提供了使用多個機器人發現和監視環境的技術。多個機器人通過以下方式來導航環境：為每個機器人確定導航緩衝區；允許每個機器人在與其他機器人保持基本上最小的距離的同時在環境內導航，其中基本上最小的距離對應於導航緩衝區，以及其中導航緩衝區中的每一個的大小隨著時間基於仍然有待導航的環境的百分比被減小。機器人還可以通過以下方式來導航環境：獲取將環境劃分為多個離散區域的離散化；以及使用廣度優先搜索為多個機器人中的一個確定下一未被訪問的離散區域，以探索示例性環境。多個離散區域可以例如是多個真實或虛擬瓦片。
【專利說明】使用多個機器人對環境的發現和監視
【技術領域】
[0001]本發明涉及協調多個移動機器人對給定環境或區域進行探索和監視的自動化技術。
【背景技術】
[0002]數據中心正在消耗更多的能量。認識到冷卻是能耗的重要貢獻因素，數據中心操作員開始容忍更高的運行溫度。儘管該實踐節省了相當多的能量，但是以更接近容許的運行溫度極限的溫度運行會增加溫度問題導致設備故障的風險，而設備故障會衝銷節能的財務收益。需要警戒，並且該警戒正越來越多地由數據中心能量管理軟體提供，所述數據中心能量管理軟體監視數據中心環境狀況例如溫度，並在麻煩的熱點發展時警告操作員。
[0003]已經提出或建議了許多技術來使用一個或多個機器人自動地對數據中心進行導航、構建地圖和監視。例如，通過引用結合在本文中的J.Lenchner等人的「TowardsData Center Self-Diagnosis Using a Mobile Robot，， (ACM Int』 I Conf.0n AutonomicComputing(ICACj 11) (2011))公開了一種機器人，其用作物理自主元件來自動地對數據中心進行導航、構建地圖和監視。所公開的機器人導航數據中心、對其布局構建地圖並監視其溫度或感興趣的其他量，而只有很少的人工輔助(如果有的話)。此外，通過引用結合在本文中的於 2010 年 9 月 28 日提交的標題為「Detecting Energy and Environmental Leaks inIndoor Environments Using a Mobile Robot」的美國專利申請序列號 12/892，532 公開了使用一個或多個移動機器人在室內環境中進行能量和環境洩露檢測的技術。
[0004]儘管機器人的使用已經極大改進了自動監視室內環境的能力，但是它們也受到許多限制，如果能克服這些限制，則可以進一步擴展監視室內環境的機器人的有用性和效率。例如，有挑戰的是，使多個機器人高效地導航室內環境而不會互相阻礙，特別是在接近探索結束時。許多現有導航技術使用眾所周知的基於邊界的A*增量導航方法，這首先在Peter Hart 等人的 「A Formal Basis for the Heuristic Determination of Minimum CostPaths」 (SIGART Newsletter, 37:28-29 (1972))中針對單個機器人進行描述，更近期地由Yamauchi 的 「Frontier-Based Exploration Using Multiple Robots，，(Proc.0f the IntJ IConf.0n Autonomous Agents (1998))在多個機器人的背景中進行描述。此外，許多現有導航技術還集成了每個機器人攜帶「勢場」使得機器人被強制互相隔開某個人工調諧的距離這一構思。例如參見 Yong K.Hwang 和 Narandra Ahuja 的「A Potential Field Approach toPath Planning，，(IEEE Trans.0n Robotics and Automation Actions, Vol.8, Issuel (IEEE, I992))。
[0005]對於自動地對環境(特別是結構良好的室內環境諸如數據中心)進行導航、構建地圖和監視的機器人而言，仍然需要更高效的導航方法。

【發明內容】

[0006]通常，本發明的各方面提供了使用多個機器人對環境的發現和監視。根據本發明的一個方面，多個機器人通過以下方式導航環境:為每個機器人確定導航緩衝區；以及允許每個機器人在環境內導航，同時與其他機器人保持基本上最小的距離，其中基本上最小的距離對應於導航緩衝區的大小，以及其中，每個導航緩衝區的大小基於仍然有待導航的環境的百分比隨著時間而減小。
[0007]導航緩衝區的大小可以例如與仍然有待導航的環境的百分比成正比地減小。環境可以是已知或未知的環境。導航緩衝區可以例如被初始化為用於把k個均一的導航緩衝區裝配在環境內的初始區域。示例性導航緩衝區包括圓形、橢圓形、正方形、長方形、其他多邊形等。如果機器人能夠在三維中導航，則區域也可以是三維的，其中類似的樣本導航緩衝區是球體、橢圓體、正方體或長方體。
[0008]根據本發明的另一方面，多個機器人通過以下方式導航環境:獲取把環境劃分為多個離散區域的離散化；以及使用廣度優先搜索為在示例性環境中探索的多個機器人中的一個確定下一未被訪問的離散區域。多個離散區域例如可以是多個真實或虛擬瓦片。
[0009]通過參考以下詳細描述和附圖，將會獲得本發明的更完整的理解以及本發明的更多特徵和優點。
【專利附圖】

【附圖說明】
[0010]圖1示出可以在其中使用本發明的示例性室內環境；
[0011]圖2是包含本發明的方面的勢場半徑確定過程的示例性流程圖；
[0012]圖3和4示出示例性機器人R1和R2使用所公開的可變勢場導航技術導航經過圖1的示例性室內環境；
[0013]圖5是包含本發明的方面的廣度優先搜索路徑確定過程的示例性流程圖；
[0014]圖6至13示出示例性機器人R1和R2使用圖5的廣度優先搜索路徑確定過程確定下一未被訪問的瓦片，而導航經過圖1的示例性室內環境；並且
[0015]圖14是可以實現本發明的過程的機器人導航系統的框圖。
【具體實施方式】
[0016]本發明提供了在先前已知的環境以及先前未知的環境中的改進的多機器人導航。根據本發明的可變勢場方面，通過基於已知環境中仍然有待探索的區域的百分比、或者未知環境中仍然有待探索的區域的估算百分比而改變勢場的半徑，來改進已知和未知環境的多機器人導航。勢場在這裡也被稱為「導航緩衝區」。通常，示例性勢場的半徑隨著保持未被探索的室內環境的百分比(或估算百分比)的降低而減小。儘管使用圍繞每個機器人具有基本均一半徑的圓形來舉例說明本發明的可變勢場方面，但是對於本領域普通技術人員而言很明顯的是，可以圍繞每個機器人建立任意形狀以及可變大小的導航緩衝區。
[0017]根據本發明的廣度優先搜索方面，通過使用廣度優先搜索(BFS)為多個機器人確定經過已知環境的路徑，來改進已知環境的多機器人導航。所公開的廣度優先搜索技術使用多項式時間遞歸啟發，其防止兩個或多個機器人嘗試訪問環境的相同部分。通常，每個機器人增量地創建廣度優先搜索樹，並且它們共同嘗試找到環境內的下一未被訪問的位置。每個機器人更新其各自的BFS樹以適應首先成功找到未被訪問的位置的機器人。
[0018]通常，廣度優先搜索(BFS)是圖形搜索算法，其在根節點開始並探索所有相鄰節點。然後，對於每個最接近的節點，圖形搜索算法探索其所有未被探索的相鄰節點，等等，直到找到期望的節點(即之前未被訪問的瓦片)。
[0019]這裡所使用的術語「建築物」旨在指代各種設施，包括但不限於含有大量信息技術(IT)設備的數據中心，以及工業辦公室空間和住宅建築物。
[0020]圖1示出可以在其中使用本發明的示例性室內環境100。給定機器人集合(R1,..., RkI並假設在示例性室內環境100內將被探索的空間已被離散化為正方形「瓦片」的集合。在某些實際的環境例如計算機數據中心中，自然的離散化單元是實際的物理地板或天花板瓦片。在其他環境中，離散化單元可以是虛擬瓦片。圖1的示例性室內環境100包括6乘6瓦片的示例性陣列，由兩個示例性機器人R1和R2探索。在示例性室內環境100中用X標記的瓦片保持未被訪問。用交叉陰影圖案填充的瓦片表示障礙物的存在。如下面結合圖2至4進一步討論，示例性機器人R1和R2使用本發明的可變勢場方面來導航經過示例性室內環境100的路徑。如下面結合圖5至13進一步討論，示例性機器人R1和R2使用本發明的廣度優先搜索方面來導航經過示例性室內環境100的路徑。
[0021]對於適合的示例性機器人的詳細討論，參見例如通過引用結合在本文中的於2010 年 9 月 28 日提交的標題為 「Detecting Energy and Environmental Leaks in IndoorEnvironments Using a Mobile Robot」的美國專利申請序列號12/892,532。這裡所使用的術語「機器人」一般表示可以通過電子或計算機編程來控制的任意形式的移動電子機械設備。如下面將詳細描述，在該基本形式下，示例性機器人在建築物100的整個指定部分中移動，並且取得溫度、氣流和/或懸浮物測量值以及時間和定位數據(以便允許溫度、氣流和/或懸浮物數據與特定時間建築物100中的給定位置相關聯)。機器人應該能夠沿著建築物的地板在各個方向上移動，以便導航機器人需要去的地方並在障礙物例如建築物100中的設備、家具、牆壁等附近進行調遣。
[0022]優選的是，機器人(例如100中的R1和R2)具有採集並存儲數據即溫度、氣流和/或懸浮物測量值以及時間/定位數據的能力，以允許後續進行分析，儘管還有可能使數據以流的形式傳送給控制或伺服器計算機，所述數據可以在那兒被處理和/或存儲。
[0023]如下面所討論，示例性室內環境100可以是已知或未知環境。如上所示，本發明的可變勢場方面可以用於導航已知和未知環境。同樣地，本發明的廣度優先搜索方面可以用於導航已知環境。本發明的可變勢場和廣度優先搜索方面可以在已知環境的情形下進行組合，特別是很多機器人的情形，在這種情形中廣度優先搜索的計算時間和空間成本可能會過高。在例如已知的網格空間中，可變勢場方法可以被使用，直到例如5R個網格點保持未被訪問，其中R是機器人的數量。
[0024]基於未探索區域的百分比的導航緩衝區
[0025]圖2是包含本發明的方面的勢場半徑確定過程200的示例性流程圖，其中導航緩衝區全是具有均一半徑的圓。如圖2所示，勢場半徑確定過程200最初開始於在步驟210期間確定多邊形P，其描述待導航的環境的周邊。接下來，在步驟220期間勢場半徑確定過程200計算待導航的區域的面積A、並將其自身初始化為存在k個機器人(R1,..., RJ的事實。
[0026]勢場半徑確定過程200然後在步驟230期間通過使用對似乎可能的半徑的二分查找以不同半徑嘗試圓盤填裝、並且例如使用標準的網格偏移方法(參見例如D.Hochbaum和 W.Maas 的「Approximation Schemes for Covering and Packing Problems in ImageProcessing and VLSI 」，32 (I): 130-136，1985)實現每個填裝，來獲取用於在P內填裝k個均一半徑的圓盤的近似最大(初始)半徑。然後在步驟240期間使所確定的最大半徑減小可配置的量例如10-20%，以確保機器人有要移動的空間、並且所確定的最大半徑是低估值。再次注意，對於本領域普通技術人員來說很明顯的是，可以在每個機器人周圍建立任意形狀和可變大小的導航緩衝區。
[0027]在步驟250中，機器人共同嘗試尋找下一個尚未訪問的區域，並且在步驟260期間隨著已被探索的區域的百分比的增加，例如與未探索區域的當前百分比成線性比例地減小勢場半徑。在事先不知道待探索的區域的情形下，當然必須利用邊界多邊形的面積以及到目前為止已探索的區域中的已經證明包含障礙物的部分，來估算在任意時間點未被探索的區域的精確百分比。當不存在下一未被訪問區域時，換句話說當區域已被完全探索時，過程在步驟270中完成。
[0028]圖3和4示出使用本發明的可變勢場方面由示例性機器人R1和R2導航經過示例性室內環境100。圖3示出示例性機器人R1和R2在第一時間的導航，且圖4示出示例性機器人R1和R2在特定部分的瓦片已被探索之後的隨後時間tn的導航。標記為X2的瓦片表示機器人R2已經探索過該瓦片，而標記為X1的瓦片表示機器人R1已經探索過該瓦片。應注意的是，在時間h的半徑rtl大於在時間tn的半徑rtn，因為保持未被探索的示例性室內環境100的百分比已經隨時間減小。圖3中在時間A保持未被探索的瓦片的數量是27塊瓦片，而圖4中在時間、保持未被探索的瓦片的數量是15塊瓦片。與各個機器人相關聯的勢場或導航緩衝區由在給定時間圍繞它們的相關聯的圓形或圓盤給出，換句話說，圖3中在時間h的半徑為rtl的圓盤、以及圖4中在隨後的時間tn的半徑為rtn的圓盤。在任意給定時間ti;這些圓盤用於將機器人保持分開至少2rti的距離。在另一變型中，勢場或導航緩衝區可以用於將機器人保持分開至少rti的距離(即只要另一機器人自身不在給定機器人的導航區域內，給定機器人就可以繼續移動)。在又一變型中，半徑或形狀面積可以與每個機器人的速度成比例(並且與剩餘/未被訪問的空間的量成比例)。
[0029]廣度優先搜索導航
[0030]圖5是包含本發明的方面的廣度優先搜索路徑確定過程500的示例性流程圖。如下面結合圖6至13進一步討論，每個示例性機器人R1和R2執行廣度優先搜索路徑確定過程500以確定導航經過示例性室內環境100的路徑的過程中的下一未被訪問的瓦片。
[0031]如圖5所示，在步驟510中，每個機器人在所有方向上(在軟體中)採取一個假想的步驟，保持其路徑完整集合的廣度優先搜索(BFS)樹。下面結合圖6A進一步討論BFS樹。在步驟520中，機器人將其BFS樹發展至一個額外的深度級別，並且發現到那時為止尚未訪問的瓦片的任意機器人向其他機器人聲明該事實以及藉以找到該瓦片的路徑。將找到之前尚未訪問的瓦片的任意機器人稱為「聲明」機器人。使用適當的任意類型的機器人到機器人或機器人到伺服器到機器人的通信來做出該聲明。在步驟530中，到達決策/控制點。如果任何機器人都沒有發現新的瓦片，則重複步驟510，並且所有機器人將其BFS樹發展到額外的深度級別。另一方面，如果一個或多個機器人遇到未被訪問的瓦片，則由未找到未被訪問的瓦片的機器人執行步驟540和550，並由找到瓦片的機器人執行步驟560。
[0032]這些步驟集合可以由兩組機器人並行執行。如果兩個機器人找到同一瓦片，則任意方法可以用於決定哪個機器人成為聲明機器人且因此遵循步驟560，以及哪個機器人成為非聲明機器人。例如，機器人可以被預先編號(索引化)為&，…，Rk，如前面在勢場半徑確定過程200中所實現的，使較小編號的機器人成為「聲明」機器人。在步驟540中，非聲明機器人檢查其各自的BFS樹以查看是否與聲明機器人的任意路徑存在衝突。當非聲明機器人與聲明機器人在相同時間處於給定的瓦片T中的任意時間，這被認為是衝突，此外，如果非聲明機器人在聲明機器人從瓦片T』移動到瓦片T的相同時間從瓦片T移動到瓦片T』，這被認為是衝突。在步驟540中發現衝突的任意機器人必須在步驟550中重新生成其BFS樹從而避免任意衝突。與非聲明機器人的這些活動並行，聲明機器人各自在步驟560中將其BFS樹摺疊(collapse)為到達其剛才找到的之前未被訪問的瓦片而採取的單條路徑。在所有非聲明機器人完成步驟540和550以及所有聲明機器人完成步驟560時，控制返回到步驟510，在該步驟中，機器人再次將其BFS樹發展到額外的深度級別。當所有瓦片都已被探索並且從而各個BFS樹無法進一步被發展時，過程在步驟580中終止。
[0033]對於R個機器人和總共N個具有恆定連接的瓦片(4-連接使得機器人被約束為在長方形瓦片之間正交地移動，以及8-連接使得機器人自由地沿對角線跨越長方形瓦片)，廣度優先搜索路徑確定過程500的運行時間是O (KN2)，因為任意機器人要花費O(N)時間來生成任意節點處的BFS樹，並且在每個節點，需要時間N+0(N) = O(N)來首先檢查路徑衝突然後重新生成在給定深度開始的BFS。給定總共N個節點和K個機器人，可以預期總的運行時間0(ΚΝ2)，其可以被完全並行化為每個機器人花費的0(N2)時間。預期的運行時間可能要小得多，因為兩個機器人只有在其BFS樹在同一時間增量發現同一瓦片時才會有衝突。
[0034]廣度優先搜索路徑確定過程500的總空間複雜度也是O(KN2)，因為機器人在多達O(N)個瓦片的每個瓦片上保持大小為O(N)的信息，且該空間需求再次被並行化為O (N2)。
[0035]廣度優先搜索 路徑確定過程500可以可選地通過任意一個機器人(或所有機器人)計算，且因此被執行而無需機器人之間或機器人與伺服器之間的通信，除了啟動的時候(儘管在計算時間和空間方面有更大的成本)。
[0036]圖6至13示出隨時間執行廣度優先搜索路徑確定過程500，以便為被約束為在正方形瓦片之間正交地移動的機器人在導航經過示例性室內環境100的路徑的過程中確定下一未被訪問的瓦片，該過程開始於圖6，只有4個尚未訪問的瓦片，其中未被訪問的瓦片被表示為X。
[0037]圖6示出在繼續擴展BFS樹時由機器人R1執行的廣度優先搜索路徑確定過程500的兩次迭代。在圖6至13中使用的示例性標記中，「n，Direct1n (方向)」表示與機器人移動相關聯的迭代次數(η)以及機器人從起始瓦片到達給定瓦片所需的移動的串聯方向。例如，「1，U」表不向上方向的第一次移動。類似地,D表不向下方向的移動,R表不向右方向的移動，且L表示向左方向的移動。因此，標記「2，RU」表示機器人可以在兩次迭代中向右移動、緊接著向上移動從而移動到指示的瓦片。類似地，標記「2，DR」表示機器人可以在兩次迭代中向下移動、緊接著向右移動從而移動到指示的瓦片。
[0038]圖6Α示出如上面結合圖6討論的由機器人札實現的BFS樹600的相同兩次迭代，但以更為傳統的「樹形結構」呈現出假想路徑的軌跡。應注意的是，例如，機器人R1可以已經通過向下⑶運動、緊接著向左(L)運動、以及給定的向左(L)運動、緊接著向下⑶運動而到達對角線上位於其下面的瓦片。[0039]圖7示出在繼續擴展其BFS樹時由機器人R2執行的廣度優先搜索路徑確定過程500的第二次迭代。如圖7所示，機器人R2在第二次迭代期間使用首先向下移動、緊接著向右移動以命中未被訪問的瓦片710。聲明機器人R2將已經發現未被訪問的瓦片710的事實與路徑(DR) —起向其他機器人廣播。機器人R1接收到之前未被訪問的瓦片710的通知，並且機器人R1將瓦片指示符從未被訪問(X)變更為被R2訪問(V R2)。
[0040]圖8示出在檢測到之前未被訪問的瓦片710之後由機器人R2繼續執行廣度優先搜索路徑確定過程500。如圖8所示，機器人R2將其搜索樹摺疊為與之前未被訪問的瓦片710相關聯的單個點，使得在下一次迭代中，機器人R2的BFS可以在該點重新開始。
[0041]圖9示出在R1擴展其BFS以發現新的未被訪問的瓦片910時在第四次迭代期間由機器人R1繼續執行廣度優先搜索路徑確定過程500。如圖9所示，機器人R1在第四次迭代期間使用向右移動、緊接著向上移動、緊接著兩次連續的向右移動(RURR)而命中未被訪問的瓦片910。聲明機器人R1將已經發現未被訪問的瓦片910的事實與路徑(RURR) —起向其他機器人廣播。機器人R2接收到之前未被訪問的瓦片910的通知，並且機器人R2將瓦片指示符從未被訪問(X)變更為被R1訪問(V札)。
[0042]圖10示出在檢測到之前未被訪問的瓦片910之後由機器人R1繼續執行廣度優先搜索路徑確定過程500。如圖10所示，機器人&將其搜索樹摺疊為與之前未被訪問的瓦片910相關聯的單個點，使得在下一次迭代中，機器人R1的BFS可以在該點重新開始。
[0043]圖11示出在R1擴展其BFS以發現新的未被訪問的瓦片1110時在第五次迭代期間由機器人R1繼續執行廣度優先搜索路徑確定過程500。如圖11所示，機器人&在第五次迭代期間使用移動序列(RURRR)而命中未被訪問的瓦片1110。聲明機器人R1將已經發現未被訪問的瓦片1110的事實與路徑(RURRR) —起向其他機器人廣播。機器人R2接收到之前未被訪問的瓦片1110的通知，並且機器人R2將瓦片指示符從未被訪問(X)變更為被R1訪問(V R1)。
[0044]圖12示出在第五次迭代期間由機器人R2繼續執行廣度優先搜索路徑確定過程500。如圖12所示，機器人R2已經將之前未被訪問的瓦片1110的指示符從未被訪問(X)變更為被R1訪問(V R1) ο
[0045]圖13示出在完成廣度優先搜索路徑確定過程500之後機器人R1和R2的最終路徑，其中所有瓦片現在被標記為被訪問。
[0046]根據示例性實施例，每個機器人還具有視覺組件例如安裝的相機。在規則網格(例如鋪有瓦片)的房間例如數據中心的上下文中，機器人的視覺組件負責檢測機器人相對於瓦片中心的「姿勢」，並負責確定機器人期望調查的下一瓦片是可訪問的還是阻隔的(例如，因為該瓦片被設備佔用或者被阻塞)。機器人的姿勢是機器人相對於在瓦片中心指向前方的「正交」方向的位置和方向。指向前方的正交方向是與機器人的預期推算精確對齊的方向(從一個瓦片的中心到第二相鄰瓦片的中心)，使得如果機器人直接向前移動，它將沿著與瓦片邊界垂直(正交)的路徑跨越瓦片之間的邊界，併到達它期望去往或者它期望檢查的第二瓦片的中心，目的是確定第二瓦片是否是可訪問的。這假設連接兩個相鄰瓦片的中心的(理論)直線與兩個瓦片之間的邊界垂直(正交)，在數據中心中這是典型的情況。
[0047]在數據中心的上下文中，視覺組件專門檢測瓦片邊界，確定機器人離瓦片邊界的距離(且由此確定機器人離瓦片中心的距離)，確定機器人當前與和下一瓦片邊界正交的線所成的角度，並確定機器人所朝向的方向上的下一瓦片是否被佔用或可訪問。根據示例性實施例，機器人自動地確定例如瓦片邊界以及瓦片是否可訪問或被阻塞。對機器人編程以執行該任務對於本領域技術人員來說是明顯的，且因此不會在這裡進一步描述。為了定向的目的，機器人具有視覺組件(例如相機)面向的方向所確定的指向前方的方向。該指向前方的方向還與機器人被指示向前移動時的前輪方向對齊(即在機器人旋轉時，不只是輪子而是整個裝置在旋轉)。
[0048]在不能確保瓦片的網格布局的更一般的設施中，一種選擇是放置alpha或beta發射粒子的良好的長方形網格(例如具有6英寸乘6英寸的單元大小的網格)以模擬瓦片、並隨後(在回溯時)使機器人使用與使用安裝的網絡攝像頭的方法類似的方法來檢測alpha或beta發射粒子的網格。儘管網絡攝像頭自身不能夠檢測alpha或beta粒子，但是一旦知道alpha或beta粒子的位置(例如使用alpha或beta檢測器例如薄膜Geiger-Muller計數器)，網絡攝像頭就可以在alpha或beta粒子附近拍攝快照，並且機器人可以保存由alpha或beta粒子以及周圍環境所確定的正方形的記錄，使得下一次機器人可以合理地導航回來。
[0049]該人工放置的網格即虛擬瓦片可以用於標記機器人已經處於哪裡、以及記錄例如虛擬瓦片上的最佳優先A*搜索(見Peter Hart等人的「A Formal Basis for the HeuristicDetermination of Minimum Cost Paths，，，SIGART Newsletter, 37:28-29 (1972))或深度優先搜索樹以確保環境的完整導航，如果這是合乎期望的話。深度優先搜索樹是記錄圖形的所嘗試的完整探索的軟體數據結構。在這些虛擬瓦片的情形下，圖形的節點是虛擬瓦片，並且在深度優先搜索樹的一種實現中，如果兩個瓦片在瓦片布局中是鄰居(換句話說，如果機器人可以從瓦片I行進到瓦片2而不用經過額外的瓦片)，則這兩個瓦片通過圖形的邊緣來連接。
[0050]為了提供整個建築物中的自由移動，在一個示例性實施例中，機器人以電池電源來運行。優選地，電池是可再充電的並且系統還包括一個或多個充電站(未示出)。那樣，如果機器人在掃描期間電源不足，則機器人可以進入充電站、重新充電、且然後在最後訪問的位置恢復掃描(見下面)。將移動機器人配置成返回到充電站以重新充電的技術對於本領域技術人員來說是已知的，且因此不在這裡進一步描述。
[0051]現在將描述可以根據本教導使用的協調機器人在建築物中到處移動、同時執行必要的傳感器測量的技術。在數據中心中，例如，對機器人移動的協調在某種程度上通過以下事實而得到促進:典型的數據中心地板完全由工業標準的兩英尺乘兩英尺的瓦片構成。在該情形下，只要可以準確地分析(地板的由機器人(見上面)提供的)靜態照片且由此確定瓦片邊界，就可以使用視頻裝置來實現機器人的定位。僅通過示例，計算機或其人類操作員可以分析機器人拍攝的靜態圖像，並且可以確定給定瓦片的外邊界所在的位置。
[0052]根據以下描述將會很明顯的是，系統可以利用對工業標準直線瓦片的邊界的識別來準確地生成之前對它來說未知的地板平面圖。
[0053]根據示例性實施例，系統利用現有的位置感知技術，其使用機載聲吶、雷射和視頻中的一個或多個，使用即時定位和地圖構建(SLAM)的方法。SLAM過程的核心是使用環境來更新機器人的位置。由於機器人的測程(其可以被用於給出機器人的位置的估算)通常會隨時間累積誤差或「漂移」，所以不能僅僅依賴它來獲取機器人的位置。除了測程之外，雷射、聲吶和/或視頻也可以被用於校正機器人的位置。這是通過使用擴展Kalman濾波器提取環境的特徵、然後在機器人到處移動時重新觀察這些特徵來實現的。在SLAM的文獻中，特徵一般被稱為「陸標」。擴展Kalman濾波器記錄機器人的位置的不確定性以及它在環境中看到的陸標的不確定性的估算。機器人使用網絡攝像頭來導航以及由瓦片邊界引導的在數據中心(或其他建築物/設施)裝備附近進行導航的情形僅僅是更一般的SLAM框架的特殊情形。
[0054]一旦在特定位置取得讀數，機器人就使用本發明的導航技術移動到下一位置。
[0055]這裡描述的技術自然地擴展到迄今為止在文獻中還未詳細考慮但具有實踐意義的情形，即:
[0056](i)機器人具有可變的速度；
[0057](ii)機器人具有可變的質量因子一即，機器人民比某些固定標準的機器人R以因子A進行更有效的工作、或者在其監視過程中更為徹底。所有監視位置必須用最小總體質量因子來覆蓋；以及
[0058](iii)環境的子區域具有可變的優先級。
[0059]儘管圖2和5示出示例性步驟序列，但是本發明的實施例中這些序列也可以變化。可以預期到算法的各種變更作為本發明的替代實施例。
[0060]儘管針對軟體程序的處理步驟描述了本發明的示例性實施例，但是對於本領域技術人員來說很明顯的是，各個功能可以作為軟體程序中的處理步驟的數字領域中實現、通過編程的通用計算機以硬體形式實現、通過電路元件或狀態機實現、或者以軟體和硬體兩者的組合來實現。這樣的軟體例如可以在硬體設備諸如數位訊號處理器、專用集成電路、微控制器或通用計算機中使用。這樣的硬體和軟體可以在集成電路內實現的電路內實施。
[0061]所屬領域的技術人員將理解的是，本發明的各個方面可以實施為系統、方法或電腦程式產品。因此，本發明的各個方面可以採取以下形式，即:完全的硬體實施方式、完全的軟體實施方式(包括固件、駐留軟體、微代碼等)，或軟體和硬體方面結合的實施方式，這裡可以統稱為「電路」、「模塊」或「系統」。此外，本發明的各個方面還可以採取用一個或多個計算機可讀介質實施的電腦程式產品的形式，該計算機可讀介質上包含有計算機可讀程序代碼。
[0062]可以採用一個或多個計算機可讀介質的任意組合。計算機可讀介質可以是計算機可讀信號介質或者計算機可讀存儲介質。計算機可讀存儲介質例如可以是一但不限於——電、磁、光、電磁、紅外線或半導體的系統、裝置或器件，或者任意以上的適當組合。計算機可讀存儲介質的更具體的例子(非窮舉的列表)包括:具有一個或多個導線的電連接、可攜式計算機軟盤、硬碟、隨機存取存儲器(RAM)、只讀存儲器(ROM)、可擦式可編程只讀存儲器(EPR0M或快閃記憶體)、光纖、可攜式緊湊盤只讀存儲器(CD-ROM)、光存儲器件、磁存儲器件、或者上述的任意合適的組合。在本文件的上下文中，計算機可讀存儲介質可以是任何包含或存儲程序的有形介質，該程序可以被指令執行系統、裝置或者器件使用或者與其結合使用。
[0063]計算機可讀信號介質可以包括例如在基帶中或者作為載波一部分傳播的數據信號，其中承載了計算機可讀程序代碼。這種傳播的信號可以採用各種形式，包括但不限於電磁信號、光信號或上述的任意合適的組合。計算機可讀信號介質還可以是計算機可讀存儲介質以外的任何計算機可讀介質，該計算機可讀介質可以發送、傳播或者傳輸用於由指令執行系統、裝置或者器件使用或者與其結合使用的程序。
[0064]計算機可讀介質上包含的程序代碼可以用任何適當的介質傳輸，包括但不限於無線、有線、光纜、RF等等，或者上述的任意合適的組合。
[0065]可以以一種或多種程序設計語言的任意組合來編寫用於執行本發明各方面的操作的電腦程式代碼，所述程序設計語言包括面向對象的程序設計語言(諸如Java、Smalltalk^++等)，還包括常規的過程式程序設計語言(諸如「C」程序設計語言或類似的程序設計語言)。程序代碼可以完全地在用戶計算機上執行、部分地在用戶計算機上執行、作為獨立的軟體包執行、部分在用戶計算機上部分在遠程計算機上執行、或者完全在遠程計算機或伺服器上執行。在涉及遠程計算機的情形中，遠程計算機可以通過任意種類的網絡一包括區域網(LAN)或廣域網(WAN)—連接到用戶計算機，或者，可以連接到外部計算機(例如利用網際網路服務提供商來通過網際網路連接)。
[0066]下面參照根據本發明實施例的方法、裝置(系統)和電腦程式產品的流程圖和/或框圖描述了本發明的各方面。應當理解的是，流程圖和/或框圖的每個方框以及流程圖和/或框圖中各方框的組合，都可以由電腦程式指令實現。這些電腦程式指令可以提供給通用計算機、專用計算機或其它可編程數據處理裝置的處理器，從而生產出一種機器，使得這些電腦程式指令在通過計算機或其它可編程數據處理裝置的處理器執行時，產生實現流程圖和/或 框圖中的一個或多個方框中規定的功能/動作的裝置。
[0067]也可以把這些電腦程式指令存儲在計算機可讀介質中，這些指令可以使得計算機、其它可編程數據處理裝置、或其他設備以特定方式工作，使得存儲在計算機可讀介質中的指令產生包括實現流程圖和/或框圖中的一個或多個方框中規定的功能/動作的指令的製造品°
[0068]電腦程式指令還可以加載到計算機、其它可編程數據處理裝置或其他設備上，以使一系列操作步驟在計算機、其它可編程裝置或其他設備上被執行以產生計算機實現的過程，使得在計算機或其它可編程裝置上執行的指令提供用於實現流程圖和/或框圖中的一個或多個方框中規定的功能/動作的處理。
[0069]圖14是可以實現本發明的過程的機器人導航系統1400的框圖。如圖14所示，存儲器1430將處理器1420配置成(共同地，如圖14中的1480所示)實現這裡公開的機器人導航方法、步驟和功能。存儲器1430可以是分布的或本地的，並且處理器1420可以是分布的或單獨的。存儲器1430可以被實現為電、磁或光存儲器，或者這些或其他類型的存儲設備的任意組合。應該注意的是，構成處理器1420的每個分布式處理器一般包含其自身的可尋址存儲器空間。還應注意的是，某些或所有計算機系統200可以被包含在個人計算機、膝上計算機、手持計算設備、專用電路或通用集成電路中。
[0070]附圖中的流程圖和框圖示出根據本發明的各種實施例的系統、方法和電腦程式產品的可能實現的架構、功能和操作。在這點上，流程圖或框圖中的每個方框可以代表模塊、程序段或代碼的一部分，所述模塊、程序段或代碼的一部分包含一個或多個用於實現規定的邏輯功能的可執行指令。也應當注意的是，在有些替代性實現中，方框中所標註的功能也可以以不同於附圖中所標註的順序發生。例如，兩個連續的方框實際上可以基本並行地執行，它們有時也可以按相反的順序執行，這依所涉及的功能而定。也要注意的是，框圖和/或流程圖中的每個方框、以及框圖和/或流程圖中的方框的組合，可以用執行規定的功能或動作的專用的基於硬體的系統來實現，或者可以用專用硬體與計算機指令的組合來實現。
[0071]應理解的是，這裡示出和描述的實施例和變型僅是本發明的原理的舉例說明，並且本領域技術人員可以實現各種改型而不偏離本發明的範圍和精神。
【權利要求】
1.一種用於在環境中導航多個機器人的方法，包括: 為所述機器人中的每一個確定導航緩衝區；以及 使所述多個機器人中的每一個能夠在與其他機器人保持基本上最小的距離的同時在所述環境內導航，其中所述基本上最小的距離對應於所述導航緩衝區的大小，其中基於所述環境的仍然有待導航的百分比，隨著時間減小所述導航緩衝區中的每一個的大小。
2.如權利要求1所述的方法，其中與所述環境的所述仍然有待導航的百分比成正比地減小所述導航緩衝區。
3.如權利要求1所述的方法，其中所述多個即k個導航緩衝區被初始化為初始導航緩衝區，以便將k個基本均一的導航緩衝區裝配在所述環境內。
4.如權利要求1所述的方法，其中所述環境的所述仍然有待導航的百分比是估算的值。
5.如權利要求1所述的方法，其中所述導航緩衝區中的至少一個的所述大小是基於所述對應機器人的速度確定的。
6.如權利要求1所述的方法，其中所述導航緩衝區中的每一個包括圍繞所述對應機器人的給定半徑的圓。
7.一種用於在環境中導航多個機器人的方法，包括: 獲取將所述環境劃分為多個離散區域的離散化；以及 使用廣度優先搜索為所述多個機器人中的一個確定要在所述示例性環境中探索的下一未被訪問的離散區域。
8.如權利要求7所述的方法，其中所述確定步驟由所述多個機器人中的每一個執行。
9.如權利要求7所述的方法，其中所述確定步驟由至少一個處理器執行，並且將所述確定步驟的結果提供給所述多個機器人中的每一個。
10.如權利要求7所述的方法，其中所述多個離散區域包括多個真實或虛擬瓦片。
11.如權利要求7所述的方法，其中所述環境包括已知的環境。
12.如權利要求7所述的方法，其中所述確定步驟還包括以下步驟:每個機器人每次在所有可能的方向上採取進入所述離散區域中的一個的假想步驟，以及保持路徑的廣度優先搜索樹直到一個機器人到達所述下一未被訪問的離散區域。
13.如權利要求12所述的方法，其中所述確定步驟還包括以下步驟:所述一個機器人向所述多個機器人中的其他機器人聲明:所述一個機器人已經在所述廣度優先搜索樹中到達所述下一未被訪問的離散區域；所述多個機器人中的所述其他機器人確定是否與所述一個機器人存在衝突；以及所述一個機器人使所述廣度優先搜索樹摺疊為所述下一未被訪問的離散區域的單個點。
14.一種用於在環境中導航多個機器人的裝置，所述裝置包括: 存儲器；以及 至少一個硬體設備，其耦合到所述存儲器，並可操作地: 為所述機器人中的每一個確定導航緩衝區；以及 使所述多個機器人中的每一個能夠在與其他機器人保持基本上最小的距離的同時在所述環境內導航，其中所述基本上最小的距離對應於所述導航緩衝區的大小，其中基於所述環境的仍然有待導航的百分比，隨著時間減小所述導航緩衝區中的每一個的大小。
15.如權利要求14所述的裝置，其中與所述環境的所述仍然有待導航的百分比成正比地減小所述導航緩衝區。
16.如權利要求14所述的裝置，其中所述機器人採用一個或多個傳感器來執行所述環境中的一個或多個測量。
17.如權利要求14所述的裝置，其中所述多個即k個導航緩衝區被初始化為初始導航緩衝區，以便將k個基本均一的導航緩衝區裝配在所述環境內。
18.如權利要求14所述的裝置，其中所述環境的所述仍然有待導航的百分比是估算的值。
19.如權利要求14所述的裝置，其中所述導航緩衝區中的至少一個的大小是基於所述對應機器人的速度確定的。
20.如權利要求14所述的裝置，其中所述導航緩衝區中的每一個包括圍繞所述對應機器人的給定半徑的圓。
21.一種用於在環境中導航多個機器人的裝置，包括: 存儲器；以及 至少一個硬體設備，其耦合到所述存儲器，並可操作地: 獲取將所述環境劃分為多個離散區域的離散化；以及 使用廣度優先搜索為所述多個機器人中的一個確定要在所述示例性環境中探索的下一未被訪問的離散區域。
22.如權利要求21所述的裝置，其中所述確定由所述多個機器人中的每一個執行。
23.如權利要求21所述的裝置，其中所述確定由至少一個處理器執行，並且將所述確定的結果提供給所述多個機器人中的每一個。
24.如權利要求21所述的裝置，其中所述環境包括已知的環境。
25.如權利要求21所述的裝置，其中所述確定步驟還包括以下步驟:每個機器人每次在所有可能的方向上採取進入所述離散區域中的一個的假想步驟，以及保持路徑的廣度優先搜索樹直到一個機器人到達所述下一未被訪問的離散區域。
【文檔編號】G06G7/78GK104040560SQ201280066718
【公開日】2014年9月10日 申請日期:2012年11月27日 優先權日:2012年1月12日
【發明者】郭尚青, C·伊什奇, J·倫克納, M·慕克爾吉 申請人:國際商業機器公司