(19)國家知識產(chǎn)權(quán)局62/883,4382019.08.06US地址美國馬薩諸塞州提供了計算機實現(xiàn)的方法、機器人和系統(tǒng)。從圖像傳感器接收與所述機器人的環(huán)境相關(guān)聯(lián)數(shù)據(jù)確定從所述第一路徑點到所述第二路徑點2在機器人的數(shù)據(jù)處理硬件處接收導(dǎo)航路線，所述導(dǎo)航路線包括第一路徑點和第二路徑在所述數(shù)據(jù)處理硬件處，從圖像傳感器接收與所述機器人的環(huán)境相關(guān)聯(lián)的圖像數(shù)據(jù)；由所述數(shù)據(jù)處理硬件基于所述圖像數(shù)據(jù)確定從所述第一路徑點到所述第二路徑點的由所述數(shù)據(jù)處理硬件從所述多條路徑中選擇路徑，所述路徑包括至少一個中間路徑由所述數(shù)據(jù)處理硬件命令所述機器人經(jīng)由所述第一路徑點、所述至少一個中間路徑點和所述第二路徑點、從所述環(huán)境中的起始位置到目的地位置的導(dǎo)航。2.根據(jù)權(quán)利要求1所述的計算機實現(xiàn)的方法，其中所述導(dǎo)航路線基于所述環(huán)境中的一個或多個第一障礙物，其中所述多條路徑基于所述環(huán)境中的一個或多個第二障礙物。3.根據(jù)權(quán)利要求1所述的計算機實現(xiàn)的方法，其中所述導(dǎo)航路線基于所述環(huán)境中的一個或多個障礙物的一個或多個第一位置，其中所述圖像數(shù)據(jù)指示所述一個或多個障礙物的一個或多個第二位置。4.根據(jù)權(quán)利要求1所述的計算機實現(xiàn)的方法，其中，所述多條路徑包括繞過障礙物的多條路徑。5.根據(jù)權(quán)利要求1所述的計算機實現(xiàn)的方法，其中，所述導(dǎo)航路線包括從所述起始位置到所述目的地位置的導(dǎo)航路線。6.根據(jù)權(quán)利要求1所述的計算機實現(xiàn)的方法，進一步包括：基于所述第一路徑點、所述至少一個中間路徑點和所述第二路徑點，生成指示用于放置所述機器人的一只或多只腳的一個或多個位置的腳步規(guī)劃。7.根據(jù)權(quán)利要求6所述的計算機實現(xiàn)的方法，其中所述命令機器人的導(dǎo)航包括：使用所述腳步規(guī)劃來命令所述機器人經(jīng)由所述第一路徑點、所述至少一個中間路徑點和所述第二路徑點、從所述起始位置到所述目的地位置的導(dǎo)航。8.根據(jù)權(quán)利要求6所述的計算機實現(xiàn)的方法，其中所述至少一個中間路徑點包括中間路徑點，其中所述命令機器人的導(dǎo)航包括：使用所述腳步規(guī)劃命令所述機器人從所述開始位置到使用所述腳步規(guī)劃的所述第一路徑點的導(dǎo)航；使用所述腳步規(guī)劃命令所述機器人從所述第一路徑點到所述中間路徑點的導(dǎo)航；和使用所述腳步規(guī)劃命令所述機器人從所述中間路徑點到所述第二路徑點的導(dǎo)航。9.根據(jù)權(quán)利要求6所述的計算機實現(xiàn)的方法，其中所述命令機器人的導(dǎo)航包括：根據(jù)所述腳步規(guī)劃命令所述機器人的一只或多只腳的放置。10.根據(jù)權(quán)利要求1所述的計算機實現(xiàn)的方法，進一步包括：將所述至少一個中間路徑點添加到所述導(dǎo)航路線。11.根據(jù)權(quán)利要求1所述的計算機實現(xiàn)的方法，其中所述接收圖像數(shù)據(jù)包括：基于所述機器人根據(jù)所述導(dǎo)航路線的至少一部分對所述環(huán)境的至少一部分的導(dǎo)航，來接收所述圖像數(shù)據(jù)。12.根據(jù)權(quán)利要求1所述的計算機實現(xiàn)的方法，進一步包括：3將所述多條路徑中的第一路徑與所述多條路徑中的第二路徑進行比較，其中所述選擇路徑是基于將所述第一路徑與所述第二路徑進行比較。13.根據(jù)權(quán)利要求12所述的計算機實現(xiàn)的方法，進一步包括：確定與所述第一路徑相關(guān)聯(lián)的第一成本；和確定與所述第二路徑相關(guān)聯(lián)的第二成本，其中將所述第一路徑與所述第二路徑進行比較包括將所述第一成本與所述第二成本進行比較。14.根據(jù)權(quán)利要求1所述的計算機實現(xiàn)的方法，其中所述確定多條路徑包括：基于所述圖像數(shù)據(jù)確定所述多條路徑，以避免所述機器人與所述一個或多個障礙物接15.根據(jù)權(quán)利要求1所述的計算機實現(xiàn)的方法，其中所述確定多條路徑包括：基于所述導(dǎo)航路線確定所述多條路徑。16.根據(jù)權(quán)利要求1所述的計算機實現(xiàn)的方法，進一步包括：基于由所述圖像數(shù)據(jù)指示的一個或多個障礙物，來生成所述多條路徑。17.根據(jù)權(quán)利要求1所述的計算機實現(xiàn)的方法，進一步包括：基于所述圖像數(shù)據(jù)確定用于放置所述至少一個中間路徑點的位置。18.根據(jù)權(quán)利要求1所述的計算機實現(xiàn)的方法，其中第一組數(shù)據(jù)用于生成所述第一路徑點和所述第二路徑點，其中第二組數(shù)據(jù)用于生成所述至少一個中間路徑點，并且其中所述第一組數(shù)據(jù)不同于所述第二組數(shù)據(jù)。19.根據(jù)權(quán)利要求1所述的計算機實現(xiàn)的方法，其中，所述第一路徑點、所述第二路徑點和所述至少一個中間路徑點中的每一個都與地面上的相應(yīng)位置、相應(yīng)偏航值、或相應(yīng)時間值中的至少一個相關(guān)聯(lián)。20.根據(jù)權(quán)利要求1所述的計算機實現(xiàn)的方法，其中，所述多條路徑中的每一條都偏離所述導(dǎo)航路線。與所述數(shù)據(jù)處理硬件通信的存儲器，所述存儲器存儲指令，其中所述指令由所述數(shù)據(jù)處理硬件執(zhí)行促使所述數(shù)據(jù)處理硬件：接收導(dǎo)航路線，所述導(dǎo)航路線包括第一路徑點和第二路徑點；從圖像傳感器接收與機器人的環(huán)境相關(guān)聯(lián)的圖像數(shù)據(jù)；基于所述圖像數(shù)據(jù)確定從所述第一路徑點到所述第二路徑點的多條路徑；從所述多條路徑中選擇路徑，所述路徑包括至少一個中間路徑點；和命令所述機器人經(jīng)由所述第一路徑點、所述至少一個中間路徑點和所述第二路徑點、從所述環(huán)境中的起始位置到目的地位置的導(dǎo)航。圖像傳感器；至少兩條腿；與所述圖像傳感器通信的數(shù)據(jù)處理硬件；和與所述數(shù)據(jù)處理硬件通信的存儲器，所述存儲器存儲指令，其中所述指令由所述數(shù)據(jù)處理硬件執(zhí)行促使所述數(shù)據(jù)處理硬件：4接收導(dǎo)航路線，所述導(dǎo)航路線包括第一路徑點和第二路徑點；從所述圖像傳感器接收與所述機器人的環(huán)境相關(guān)聯(lián)的圖像數(shù)據(jù)；基于所述圖像數(shù)據(jù)確定從所述第一路徑點到所述第二路徑點的多條路徑；從所述多條路徑中選擇路徑，所述路徑包括至少一個中間路徑點；和命令所述機器人經(jīng)由所述第一路徑點、所述至少一個中間路徑點和所述第二路徑點、從所述環(huán)境中的起始位置到目的地位置的導(dǎo)航。23.一種計算機實現(xiàn)的方法，當由機器人的數(shù)據(jù)處理硬件執(zhí)行時，促使所述數(shù)據(jù)處理硬從圖像傳感器接收機器人的環(huán)境的圖像數(shù)據(jù)；接收身體障礙物地圖，所述身體障礙物地圖包括所述機器人的身體不能穿越的障礙物基于所述身體障礙物地圖生成稀疏圖，所述稀疏圖包括開始于起始位置并結(jié)束于目的地的一組節(jié)點和邊，所述節(jié)點和邊表示所述機器人可在所述環(huán)境中行進的路徑；規(guī)劃從所述起始位置到所述目的地的粗略路徑；確定沿著該組節(jié)點中的第一節(jié)點和該組節(jié)點中的第二節(jié)點之間的粗略路徑的、其中所述圖像傳感器的視線丟失的點；在沿著所述粗略路徑的其中所述圖像傳感器的視線丟失的所述點處生成中間路徑點；和沿著所述粗略路徑和所述中間路徑點從所述起始位置朝向所述目的地導(dǎo)航所述機器24.根據(jù)權(quán)利要求23所述的方法，其中所述規(guī)劃粗略路徑包括：確定該組節(jié)點和邊中的相應(yīng)節(jié)點和邊之間的有效互連的路線。25.根據(jù)權(quán)利要求23所述的方法，其中所述生成稀疏圖包括：基于所述身體障礙物地圖生成完全配置空間地圖，所述完全配置空間地圖包括元素的二維網(wǎng)格，所述網(wǎng)格的每個元素表示所述環(huán)境的空間，并且所述完全配置空間地圖的每個元素包括相應(yīng)的偏航配置集；和從所述完全配置空間地圖生成所述稀疏圖。26.根據(jù)權(quán)利要求25所述的方法，其中：每個偏航配置被分類為有效或無效；有效的偏航配置表示在與相應(yīng)元素相關(guān)聯(lián)的空間處免于受到接觸障礙物的危險的機無效的偏航配置表示在與相應(yīng)元素相關(guān)聯(lián)的空間處不能免于受到接觸障礙物的危險的機器人的偏航配置。27.根據(jù)權(quán)利要求25所述的方法，其中所述生成稀疏圖包括：從所述完全配置空間地圖生成經(jīng)壓縮配置空間地圖，所述經(jīng)壓縮配置空間地圖包括元素的第二二維網(wǎng)格，所述第二網(wǎng)格的每個元素表示所述環(huán)境的空間，并且所述第二網(wǎng)格的每個元素被歸類為以下之一：偏航碰撞區(qū)；5從所述經(jīng)壓縮配置空間地圖生成所述稀疏圖。28.根據(jù)權(quán)利要求27所述的方法，其中所述規(guī)劃從起始位置到目的地的粗略路徑包括：從所述經(jīng)壓縮配置空間地圖生成密集圖，所述密集圖包括被歸類為偏航自由區(qū)的元將來自所述稀疏圖的邊與來自所述密集圖的元素相鏈接。29.根據(jù)權(quán)利要求28所述的方法，其中所述將邊與來自密集圖的元素相鏈接包括：組合所述稀疏圖和所述密集圖以生成最終圖；和對所述最終圖執(zhí)行A*搜索算法。30.根據(jù)權(quán)利要求23所述的方法，其中確定沿著所述粗略路徑的、其中所述圖像傳感器的視線丟失的點包括：確定沿著規(guī)劃的粗略路徑的每個元素處的最小允許偏航和最大允許偏航；基于所述最小允許偏航和所述最大允許偏航，確定最小包絡(luò)；和確定在所述粗略路徑上的點處所需的偏航在所述最小包絡(luò)之外。31.根據(jù)權(quán)利要求23所述的方法，其中所述目的地表示所述機器人在所述環(huán)境中的位32.根據(jù)權(quán)利要求23所述的方法，其中所述目的地包括所述稀疏圖的該組節(jié)點中的相應(yīng)節(jié)點。腿，其耦接到所述身體，并被配置為在環(huán)境中操縱所述機器人；與所述腿通信的數(shù)據(jù)處理硬件；和與所述數(shù)據(jù)處理硬件通信的存儲器硬件，所述存儲器硬件存儲指令，所述指令當在所述數(shù)據(jù)處理硬件上執(zhí)行時，促使所述數(shù)據(jù)處理硬件執(zhí)行操作，包括：從圖像傳感器接收所述機器人的環(huán)境的圖像數(shù)據(jù)；接收身體障礙物地圖，所述身體障礙物地圖包括所述機器人的身體不能穿越的障礙物基于所述身體障礙物地圖生成稀疏圖，所述稀疏圖包括開始于起始位置并結(jié)束于目的地的一組節(jié)點和邊，所述節(jié)點和邊表示所述機器人可在所述環(huán)境中行進的路徑；規(guī)劃從所述起始位置到所述目的地的粗略路徑；確定沿著該組節(jié)點中的第一節(jié)點和該組節(jié)點中的第二節(jié)點之間的粗略路徑的、其中所述圖像傳感器的視線丟失的點；在沿著所述粗略路徑的、其中所述圖像傳感器的視線丟失的所述點處，生成中間路徑沿著所述粗略路徑和所述中間路徑點從所述起始位置朝向所述目的地導(dǎo)航所述機器34.根據(jù)權(quán)利要求33所述的機器人，其中所述規(guī)劃粗略路徑包括：確定該組節(jié)點和邊中的相應(yīng)節(jié)點和邊之間的有效互連的路線。35.根據(jù)權(quán)利要求33所述的機器人，其中所述生成稀疏圖包括：6基于所述身體障礙物地圖生成完全配置空間地圖，所述完全配置空間地圖包括元素的二維網(wǎng)格，所述網(wǎng)格的每個元素表示所述環(huán)境的空間，并且所述完全配置空間地圖的每個元素包括相應(yīng)的偏航配置集；和從所述完全配置空間地圖生成所述稀疏圖。36.根據(jù)權(quán)利要求35所述的機器人，其中：每個偏航配置被分類為有效或無效；有效的偏航配置表示在與相應(yīng)元素相關(guān)聯(lián)的空間處免于受到接觸障礙物的危險的機無效的偏航配置表示在與相應(yīng)元素相關(guān)聯(lián)的空間處不能免于受到接觸障礙物的危險的機器人的偏航配置。37.根據(jù)權(quán)利要求35所述的機器人，其中所述生成稀疏圖包括：從所述完全配置空間地圖生成經(jīng)壓縮配置空間地圖，所述經(jīng)壓縮配置空間地圖包含元素的第二二維網(wǎng)格，所述第二網(wǎng)格的每個元素表示所述環(huán)境的空間，并且所述第二網(wǎng)格的每個元素被歸類為以下之一：偏航碰撞區(qū)；從所述經(jīng)壓縮配置空間地圖生成所述稀疏圖。38.根據(jù)權(quán)利要求37所述的機器人，其中所述規(guī)劃從起始位置到目的地的粗略路徑包從所述經(jīng)壓縮配置空間地圖生成密集圖，所述密集圖包括被歸類為偏航自由區(qū)的元將來自所述稀疏圖的邊與來自所述密集圖的元素相鏈接。39.根據(jù)權(quán)利要求38所述的機器人，其中所述將邊與來自密集圖的元素相鏈接包括：組合所述稀疏圖和所述密集圖以生成最終圖；和對所述最終圖執(zhí)行A*搜索算法。40.根據(jù)權(quán)利要求33所述的機器人，其中，確定沿著所述粗略路徑的、其中所述圖像傳感器的視線丟失的點包括：確定沿著規(guī)劃的粗略路徑的每個元素處的最小允許偏航和最大允許偏航；基于所述最小允許偏航和所述最大允許偏航，確定最小包絡(luò)；和確定在所述粗略路徑上的點處所需的偏航在所述最小包絡(luò)之外。41.根據(jù)權(quán)利要求33所述的機器人，其中所述目的地表示所述機器人在所述環(huán)境中的42.根據(jù)權(quán)利要求33所述的機器人，其中所述目的地包括所述稀疏圖的該組節(jié)點中的相應(yīng)節(jié)點。在機器人的數(shù)據(jù)處理硬件處接收導(dǎo)航路線，所述導(dǎo)航路線包括在起始位置開始并在目的地位置結(jié)束的一系列高級路徑點，并且所述導(dǎo)航路線基于表示在所述機器人要導(dǎo)航的區(qū)域中的靜態(tài)障礙物的位置的高級導(dǎo)航數(shù)據(jù)；7在所述數(shù)據(jù)處理硬件處從圖像傳感器接收所述機器人周圍的環(huán)境的圖像數(shù)據(jù)；由所述數(shù)據(jù)處理硬件基于所述圖像數(shù)據(jù)生成至少一個中間路徑點；由所述數(shù)據(jù)處理硬件將所述至少一個中間路徑點添加到所述導(dǎo)航路線的所述一系列由所述數(shù)據(jù)處理硬件沿著所述一系列高級路徑點和所述至少一個中間路徑點從所述起始位置朝向所述目的地位置導(dǎo)航所述機器人，其中每個高級路徑點和所述至少一個中間路徑點中的每個中間路徑點包括指示平面上的位置的兩個坐標、偏航值和時間值，所述時間值指示所述機器人導(dǎo)航到相應(yīng)路徑點的估計時間量。44.根據(jù)權(quán)利要求43所述的方法，還包括由所述數(shù)據(jù)處理硬件維護所述導(dǎo)航路線上的所述一系列高級路徑點中的每一個。45.根據(jù)權(quán)利要求43所述的方法，進一步包括：在所述數(shù)據(jù)處理硬件處接收身體障礙物地圖，所述身體障礙物地圖包括所述機器人的身體不能穿越的障礙物的地圖，其中所述生成至少一個中間路徑點包括：基于所述身體障礙物地圖生成稀疏圖，所述稀疏圖包括節(jié)點和邊的列表，所述節(jié)點和邊表示所述機器人可在所述環(huán)境中行進的路徑；規(guī)劃從所述節(jié)點列表中的第一節(jié)點到所述節(jié)點列表中的第二節(jié)點的粗略路徑，所述第一節(jié)點和所述第二節(jié)點中的每一個表示所述環(huán)境中的空間；確定沿著所述粗略路徑的其中所述圖像傳感器的視線丟失的點；和在其中所述視線丟失的點處，生成所述至少一個中間路徑點中的一個。46.根據(jù)權(quán)利要求45所述的方法，其中所述生成稀疏圖包括：基于所述身體障礙物地圖生成完全配置空間地圖，所述完全配置空間地圖包括元素的二維網(wǎng)格，所述網(wǎng)格的每個元素表示所述環(huán)境的空間，并且所述完全配置空間地圖的每個元素包括相應(yīng)的偏航配置集，每個偏航配置被分類為有效或無效，其中有效的偏航配置表示在與相應(yīng)元素相關(guān)聯(lián)的空間處免于受到接觸障礙物的危險的機器人的偏航配置，而無效的偏航配置表示在與相應(yīng)元素相關(guān)聯(lián)的空間處不能免于受到接觸障礙物的危險的機器人的偏航配置；從所述完全配置空間地圖生成經(jīng)壓縮配置空間地圖，所述經(jīng)壓縮配置空間地圖包含元素的第二二維網(wǎng)格，并且所述第二網(wǎng)格的每個元素表示所述環(huán)境的空間，并且所述第二網(wǎng)格的每個元素被歸類為以下之一：(i)偏航碰撞區(qū)，(ii)偏航自由區(qū)，或(iii)偏航約束區(qū)；和從所述經(jīng)壓縮配置空間地圖生成所述稀疏圖。47.根據(jù)權(quán)利要求46所述的方法，其中規(guī)劃從所述第一節(jié)點到所述第二節(jié)點的粗略路徑包括：從所述經(jīng)壓縮配置空間地圖生成密集圖，所述密集圖包括被歸類為偏航自由區(qū)的元將來自所述稀疏圖的邊與來自所述密集圖的元素相鏈接。48.根據(jù)權(quán)利要求47所述的方法，其中所述將邊與來自密集圖的元素相鏈接包括：8組合所述稀疏圖和所述密集圖以生成最終圖；和對所述最終圖執(zhí)行A*搜索算法。49.根據(jù)權(quán)利要求46所述的方法，其中所述生成稀疏圖進一步包括：將多個沃羅諾伊單元重疊在所述經(jīng)壓縮配置空間地圖上，每個沃羅諾伊單元被歸類為所述稀疏圖上的偏航約束區(qū)，并且每個沃羅諾伊單元與被歸類為偏航碰撞區(qū)的至少兩個元50.根據(jù)權(quán)利要求49所述的方法，其中所述生成稀疏圖進一步包括：將每個沃羅諾伊單元分類為邊或節(jié)點任一者。51.根據(jù)權(quán)利要求50所述的方法，其中對每個沃羅諾伊單元進行分類包括：執(zhí)行洪水填充算法。52.根據(jù)權(quán)利要求46所述的方法，其中規(guī)劃從所述第一節(jié)點到所述第二節(jié)點的粗略路修剪邊，每個經(jīng)修剪的邊包括在閾值長度以下、并且被歸類為偏航碰撞區(qū)或偏航約束區(qū)任一者的元素。53.根據(jù)權(quán)利要求45所述的方法，其中確定沿著所述粗略路徑的、其中所述圖像傳感器的視線丟失的點包括：確定沿著規(guī)劃的粗略路徑的每個元素處的最小允許偏航和最大允許偏航；基于所述最小允許偏航和所述最大允許偏航，確定最小包絡(luò)；和確定在所述粗略路徑上的點處所需的偏航在所述最小包絡(luò)之外。54.根據(jù)權(quán)利要求43所述的方法，還包括由所述數(shù)據(jù)處理硬件將具有所述高級路徑點和所述至少一個中間路徑點的導(dǎo)航路線發(fā)送到低級路徑生成器。在機器人的數(shù)據(jù)處理硬件處接收導(dǎo)航路線，所述導(dǎo)航路線包括在起始位置開始并在目的地位置結(jié)束的一系列高級路徑點，并且所述導(dǎo)航路線基于表示在所述機器人要導(dǎo)航的區(qū)域中的靜態(tài)障礙物的位置的高級導(dǎo)航數(shù)據(jù)；在所述數(shù)據(jù)處理硬件處從圖像傳感器接收機器人周圍的環(huán)境的圖像數(shù)據(jù)；由所述數(shù)據(jù)處理硬件基于所述圖像數(shù)據(jù)生成至少一個中間路徑點；由所述數(shù)據(jù)處理硬件將所述至少一個中間路徑點添加到所述導(dǎo)航路線的所述一系列高級路徑點；由所述數(shù)據(jù)處理硬件沿著所述一系列高級路徑點和所述至少一個中間路徑點從所述起始位置朝向所述目的地位置導(dǎo)航所述機器人；由所述數(shù)據(jù)處理硬件將具有所述高級路徑點和所述至少一個中間路徑點的導(dǎo)航路線發(fā)送到低級路徑生成器；由所述數(shù)據(jù)處理硬件確定是否將所述至少一個中間路徑點添加到所述導(dǎo)航路線；和響應(yīng)于確定不將所述至少一個中間路徑點添加到所述導(dǎo)航路線，由所述數(shù)據(jù)處理硬件將未改變的導(dǎo)航路線傳遞到所述低級路徑生成器。腿，其耦接到所述身體，并被配置為在環(huán)境中操縱9與所述腿通信的數(shù)據(jù)處理硬件；和與所述數(shù)據(jù)處理硬件通信的存儲器硬件，所述存儲器硬件存儲指令，所述指令當在所述數(shù)據(jù)處理硬件上執(zhí)行時，促使所述數(shù)據(jù)處理硬件執(zhí)行操作，包括：接收導(dǎo)航路線，所述導(dǎo)航路線包括在起始位置開始并在目的地位置結(jié)束的一系列高級路徑點，并且所述導(dǎo)航路線基于表示在所述機器人要導(dǎo)航的區(qū)域中的靜態(tài)障礙物的位置的高級導(dǎo)航數(shù)據(jù)；從圖像傳感器接收機器人周圍的環(huán)境的圖像數(shù)據(jù)；基于所述圖像數(shù)據(jù)生成至少一個中間路徑點；將所述至少一個中間路徑點添加到所述導(dǎo)航路線的所述一系列高級路徑點；和沿著所述一系列高級路徑點和所述至少一個中間路徑點從所述起始位置朝向所述目的地位置導(dǎo)航所述機器人，其中每個高級路徑點和所述至少一個中間路徑點中的每個中間路徑點包括：指示平面上的位置的兩個坐標、偏航值和時間值，所述時間值指示所述機器人導(dǎo)航到相應(yīng)路徑點的估計時間量。57.根據(jù)權(quán)利要求56所述的機器人，還包括維護所述導(dǎo)航路線上的所述一系列高級路徑點中的每一個。58.根據(jù)權(quán)利要求56所述的機器人，進一步包括：接收身體障礙物地圖，所述身體障礙物地圖包括所述機器人的身體不能穿越的障礙物其中所述生成至少一個中間路徑點包括：基于所述身體障礙物地圖生成稀疏圖，所述稀疏圖包括節(jié)點和邊的列表，所述節(jié)點和邊表示所述機器人可在所述環(huán)境中行進的路徑；規(guī)劃從所述節(jié)點列表中的第一節(jié)點到所述節(jié)點列表中的第二節(jié)點的粗略路徑，所述第一節(jié)點和所述第二節(jié)點中的每一個表示所述環(huán)境中的空間；確定沿著所述粗略路徑的其中所述圖像傳感器的視線丟失的點；和在其中所述視線丟失的點處生成所述至少一個中間路徑點中的一個。59.根據(jù)權(quán)利要求58所述的機器人，其中所述生成稀疏圖包括：基于所述身體障礙物地圖生成完全配置空間地圖，所述完全配置空間地圖包括元素的二維網(wǎng)格，所述網(wǎng)格的每個元素表示所述環(huán)境的空間，并且所述完全配置空間地圖的每個元素包括相應(yīng)的偏航配置集，每個偏航配置被分類為有效或無效，其中有效的偏航配置表示在與相應(yīng)元素相關(guān)聯(lián)的空間處免于受到接觸障礙物的危險的機器人的偏航配置，而無效的偏航配置表示在與相應(yīng)元素相關(guān)聯(lián)的空間處不能免于受到接觸障礙物的危險的機器人的偏航配置；從所述完全配置空間地圖生成經(jīng)壓縮配置空間地圖，所述經(jīng)壓縮配置空間地圖包括元素的第二二維網(wǎng)格，并且所述第二網(wǎng)格的每個元素表示所述環(huán)境的空間，并且所述第二網(wǎng)格的每個元素被歸類為以下之一：(i)偏航碰撞區(qū)，(ii)偏航自由區(qū)，或(iii)偏航約束區(qū)；和從所述經(jīng)壓縮配置空間地圖生成所述稀疏圖。60.根據(jù)權(quán)利要求59所述的機器人，其中規(guī)劃從所述第一節(jié)點到所述第二節(jié)點的粗略路徑包括：從所述經(jīng)壓縮配置空間地圖生成密集圖，所述密集圖包括被歸類為偏航自由區(qū)的元將來自所述稀疏圖的邊與來自所述密集圖的元素相鏈接。61.根據(jù)權(quán)利要求60所述的機器人，其中所述將邊與來自密集圖的元素相鏈接包括：組合所述稀疏圖和所述密集圖以生成最終圖；和對所述最終圖執(zhí)行A*搜索算法。62.根據(jù)權(quán)利要求59所述的機器人，其中所述生成稀疏圖進一步包括：將多個沃羅諾伊單元重疊在所述經(jīng)壓縮配置空間地圖上，每個沃羅諾伊單元被歸類為所述稀疏圖上的偏航約束區(qū)，并且每個沃羅諾伊單元與被歸類為偏航碰撞區(qū)的至少兩個元63.根據(jù)權(quán)利要求62所述的機器人，其中所述生成稀疏圖進一步包括：將每個沃羅諾伊單元分類為邊或節(jié)點任一者。64.根據(jù)權(quán)利要求63所述的機器人，其中對每個沃羅諾伊單元進行分類包括：執(zhí)行洪水填充算法。65.根據(jù)權(quán)利要求59所述的機器人，其中規(guī)劃從所述第一節(jié)點到所述第二節(jié)點的粗略路徑包括：修剪邊，每個經(jīng)修剪的邊包括在閾值長度以下、并且被歸類為偏航碰撞區(qū)或偏航約束區(qū)任一者的元素。66.根據(jù)權(quán)利要求58所述的機器人，其中，確定沿著所述粗略路徑的、其中所述圖像傳感器的視線丟失的點包括：確定沿著規(guī)劃的粗略路徑的每個元素處的最小允許偏航和最大允許偏航；基于所述最小允許偏航和所述最大允許偏航，確定最小包絡(luò)；和確定在所述粗略路徑上的點處所需的偏航在所述最小包絡(luò)之外。67.根據(jù)權(quán)利要求56所述的機器人，還包括將具有所述高級路徑點和所述至少一個中間路徑點的導(dǎo)航路線發(fā)送到低級路徑生成器。腿，其耦接到所述身體，并被配置為在環(huán)境中操縱所述機器人；與所述腿通信的數(shù)據(jù)處理硬件；和與所述數(shù)據(jù)處理硬件通信的存儲器硬件，所述存儲器硬件存儲指令，所述指令當在所述數(shù)據(jù)處理硬件上執(zhí)行時，促使所述數(shù)據(jù)處理硬件執(zhí)行操作，包括：接收導(dǎo)航路線，所述導(dǎo)航路線包括在起始位置開始并在目的地位置結(jié)束的一系列高級路徑點，并且所述導(dǎo)航路線基于表示在所述機器人要導(dǎo)航的區(qū)域中的靜態(tài)障礙物的位置的高級導(dǎo)航數(shù)據(jù)；從圖像傳感器接收所述機器人周圍的環(huán)境的圖像數(shù)據(jù)；基于所述圖像數(shù)據(jù)生成至少一個中間路徑點；將所述至少一個中間路徑點添加到所述導(dǎo)航路線的所述一系列高級路徑點；沿著所述一系列高級路徑點和所述至少一個中間路徑點從所述起始位置朝向所述目11的地位置導(dǎo)航所述機器人；確定是否將所述至少一個中間路徑點添加到所述導(dǎo)航路線；和響應(yīng)于確定不將所述至少一個中間路徑點添加到所述導(dǎo)航路線，將未改變的導(dǎo)航路線傳遞到低級路徑生成器。計算機實現(xiàn)的方法、機器人和系統(tǒng)[0001]本專利申請是下列發(fā)明專利申請的分案申請：[0002]申請?zhí)枺?01980098897.7[0003]申請日：2019年9月13日[0004]發(fā)明名稱：中間路徑點生成器技術(shù)領(lǐng)域[0005]本公開涉及在存在約束的情況下生成中間路徑點，尤其是那些由地形施加的約束的情況。背景技術(shù)[0006]機器人設(shè)備越來越多地用于在受約束的環(huán)境中導(dǎo)航以執(zhí)行各種任務(wù)或功能。這些機器人設(shè)備經(jīng)常需要在不與障礙物接觸或不被卡住或被困的情況下導(dǎo)航穿過這些受約束的環(huán)境。隨著這些機器人設(shè)備變得更盛行，需要避免與障礙物接觸同時成功導(dǎo)航到目的地的實時導(dǎo)航和路線規(guī)劃。發(fā)明內(nèi)容[0007]本公開的一個方面提供了用于生成針對機器人的導(dǎo)航系統(tǒng)的中間路徑點的方法。該方法包含在機器人的數(shù)據(jù)處理硬件處接收導(dǎo)航路線。該導(dǎo)航路線包含一系列高級路徑點，該一系列高級路徑點開始于起始位置處并結(jié)束于目的地位置處，并且基于高級導(dǎo)航數(shù)據(jù)。該高級導(dǎo)航數(shù)據(jù)表示在機器人要導(dǎo)航的區(qū)域中的靜態(tài)障礙物的位置。該方法還包含在數(shù)據(jù)處理硬件處，從圖像傳感器接收機器人周圍的環(huán)境的圖像數(shù)據(jù)。該方法還包含由數(shù)據(jù)處理硬件基于該圖像數(shù)據(jù)生成至少一個中間路徑點。該方法還包含由數(shù)據(jù)處理硬件將該至少一個中間路徑點添加到該導(dǎo)航路線的該一系列高級路徑點，以及由數(shù)據(jù)處理硬件將機器人從起始位置沿著該一系列高級路徑點和該至少一個中間路徑點朝向目的地位置導(dǎo)航。[0008]本公開的實施方式可以包含以下可選特征中的一個或多個特征。在一些實施方式中，每個高級路徑點和每個中間路徑點包含指示平面上的位置的兩個坐標、偏航值和時間值。該時間值指示對于機器人導(dǎo)航到相應(yīng)路徑點的估計的時間量。在一些示例中，該方法還包含由數(shù)據(jù)處理硬件維護該導(dǎo)航路線上的該一系列高級路徑點中的每個高級路徑點。該方法還可以包含在數(shù)據(jù)處理硬件處接收身體障礙物地圖。該身體障礙物地圖包含機器人的身體不能穿越的障礙物的地圖。附加地，生成至少一個中間路徑點可以包含基于該身體障礙物地圖生成稀疏圖。該稀疏圖包含一系列節(jié)點和邊。該節(jié)點和邊表示該機器人可以在環(huán)境中行進的路徑。該方法還可以包含規(guī)劃從來自一系列節(jié)點的第一節(jié)點至來自該一系列節(jié)點的第二節(jié)點的粗略路徑。第一節(jié)點和第二節(jié)點各表示環(huán)境中的空間。該方法還可以包含確定沿著該粗略路徑的圖像傳感器的視線丟失的點，并且在視線丟失的點處生成至少一個中間路徑點之一。[0009]在一些實施方式中，生成該稀疏圖包含基于身體障礙物地圖生成完全配置空間地圖。該完全配置空間地圖包含元素的二維網(wǎng)格，其中該網(wǎng)格的每個元素表示環(huán)境的空間并且該完全配置空間地圖的每個元素包含相應(yīng)的偏航配置集。每個偏航配置可以被歸類為有效或無效，其中有效偏航配置表示在與相應(yīng)元素相關(guān)聯(lián)的空間處免于受到接觸障礙物的危險的機器人的偏航配置，而無效偏航配置表示在與相應(yīng)元素相關(guān)聯(lián)的空間處不能免于受到接觸障礙物的危險的機器人的偏航配置。該方法還可以包含從完全配置空間地圖生成經(jīng)壓縮配置空間地圖。該經(jīng)壓縮配置空間地圖包含元素的第二二維網(wǎng)格，并且該第二網(wǎng)格的每個元素表示環(huán)境的空間。第二網(wǎng)格的每個元素還被分類為以下之一：(i)偏航碰撞區(qū)、(ii)偏航自由區(qū)或(iii)偏航約束區(qū)。在一些示例中，該方法包含從經(jīng)壓縮配置空間地圖生成稀疏圖。[0010]可選地，規(guī)劃從第一節(jié)點至第二節(jié)點的粗略路徑包含從經(jīng)壓縮配置空間地圖生成密集圖。該密集圖包含被分類為偏航自由區(qū)的元素。該方法還可以包含將來自稀疏圖的邊與來自密集圖的元素相鏈接。在一些實施方式中，將邊與來自密集圖的元素相鏈接包含將稀疏圖和密集圖組合以生成最終圖。在一些示例中，該方法還包含在最終涂上執(zhí)行A*搜索算法。[0011]在一些示例中，生成稀疏圖還包含將多個沃羅諾伊(Voronoi)單元重疊在經(jīng)壓縮配置空間地圖上，其中每個Voronoi單元在稀疏圖上被分類為偏航約束區(qū)。每個Voronoi單元與被分類為偏航碰撞區(qū)的至少兩個元素等距?？蛇x地，生成稀疏圖還包含將每個Voronoi單元歸類為邊或節(jié)點任一者。分類每個Voronoi單元可以包含執(zhí)行洪水填充算法。[0012]在一些實施方式中，規(guī)劃從第一節(jié)點至第二節(jié)點的粗略路徑包含修剪邊，并且每個經(jīng)修剪的邊包含在閾值長度以下并且被分類為偏航碰撞區(qū)或偏航約束區(qū)任一者的元素。確定沿著粗略路徑的圖像傳感器的視線丟失的點可以包含確定沿著規(guī)劃的粗略路徑的每個元素處的最小允許偏航和最大允許偏航，以及基于最小允許偏航和最大允許偏航確定最小包絡(luò)。該方法還可以包含確定在粗略路徑上的點處所需的偏航在最小包絡(luò)之外。[0013]在一些示例中，該方法還包含由數(shù)據(jù)處理硬件將具有高級路徑點和至少一個中間路徑點的導(dǎo)航路線發(fā)送到低級路徑生成器。該方法還可以包含由數(shù)據(jù)處理硬件確定是否將至少一個中間路徑點添加到導(dǎo)航路線，并且響應(yīng)于確定不將該至少一個中間路徑點添加到導(dǎo)航路線，由數(shù)據(jù)處理硬件將不變的導(dǎo)航路線傳遞到低級路徑生成器。[0014]本公開的另一方面提供了一種機器人，該機器人包含身體和耦接到身體并被配置為在環(huán)境中操縱該機器人的腿。該機器人還包含與腿相通信的數(shù)據(jù)處理硬件和與數(shù)據(jù)處理硬件相通信的存儲器硬件。該存儲器硬件存儲指令，當在數(shù)據(jù)處理硬件上執(zhí)行時，該些指令使得數(shù)據(jù)處理硬件執(zhí)行操作。該些操作包含接收導(dǎo)航路線。該導(dǎo)航路線包含一系列高級路徑點，該一系列高級路徑點開始于起始位置處并結(jié)束于目的地位置處，并且基于高級導(dǎo)航數(shù)據(jù)。該高級導(dǎo)航數(shù)據(jù)表示在機器人要導(dǎo)航的區(qū)域中的靜態(tài)障礙物的位置。該操作還包含從圖像傳感器接收機器人周圍的環(huán)境的圖像數(shù)據(jù)。該操作還包含基于該圖像數(shù)據(jù)生成至少一個中間路徑點。該操作還包含將該至少一個中間路徑點添加到該導(dǎo)航路線的該一系列高級路徑點，以及將機器人從起始位置沿著該一系列高級路徑點和該至少一個中間路徑點朝向目的地位置導(dǎo)航。[0015]該方面可以包含以下可選特征中的一個或多個特征。在一些實施方式中，每個高級路徑點和每個中間路徑點包含兩個坐標，該兩個坐標指示平面上的位置、偏航值和時間值。該時間值指示對于機器人導(dǎo)航到相應(yīng)路徑點的估計的時間量。在一些示例中，該操作還包含維護該導(dǎo)航路線上的該一系列高級路徑點中的每個高級路徑點。該操作還可以包含接收身體障礙物地圖。該身體障礙物地圖包含機器人的身體不能穿越的障礙物的地圖。附加地，生成至少一個中間路徑點可以包含基于該身體障礙物地圖生成稀疏圖。該稀疏圖包含一系列節(jié)點和邊。該節(jié)點和邊表示該機器人可以在環(huán)境中行進的路徑。該操作還可以包含規(guī)劃從來自一系列節(jié)點的第一節(jié)點至來自該一系列節(jié)點的第二節(jié)點的粗略路徑。第一節(jié)點和第二節(jié)點各表示環(huán)境中的空間。該操作還可以包含確定沿著該粗略路徑的圖像傳感器的視線丟失的點，并且在視線丟失的點處生成至少一個中間路徑點之一。[0016]在一些實施方式中，生成該稀疏圖包含基于身體障礙物地圖生成完全配置空間地圖。該完全配置空間地圖包含元素的二維網(wǎng)格，其中該網(wǎng)格的每個元素表示環(huán)境的空間并且該完全配置空間地圖的每個元素包含相應(yīng)的偏航配置集。每個偏航配置可以被歸類為有效或無效，其中有效偏航配置表示在與相應(yīng)元素相關(guān)聯(lián)的空間處免受接觸障礙物的危險的機器人的偏航配置，并且無效偏航配置表示在與相應(yīng)元素相關(guān)聯(lián)的空間處不能免受接觸障礙物的危險的機器人的偏航配置。該操作還可以包含從完全配置空間地圖生成經(jīng)壓縮配置空間地圖。該經(jīng)壓縮配置空間地圖包含元素的第二二維網(wǎng)格，并且該第二網(wǎng)格的每個元素表示環(huán)境的空間。第二網(wǎng)格的每個元素還被分類為以下之一：(i)偏航碰撞區(qū)、(ii)偏航自由區(qū)或(iii)偏航約束區(qū)。在一些示例中，該操作包含從經(jīng)壓縮配置空間地圖生成稀疏圖。[0017]可選地，規(guī)劃從第一節(jié)點至第二節(jié)點的粗略路徑包含從經(jīng)壓縮配置空間地圖生成密集圖。該密集圖包含被分類為偏航自由區(qū)的元素。該操作還可以包含將來自稀疏圖的邊與來自密集圖的元素相鏈接。在一些實施方式中，將邊與來自密集圖的元素相鏈接包含將稀疏圖和密集圖組合以生成最終圖。在一些示例中，該方法還包含在最終涂上執(zhí)行A*搜索算法。[0018]在一些示例中，生成稀疏圖還包含將多個沃羅諾伊(Voronoi)單元重疊在經(jīng)壓縮配置空間地圖上，其中每個Voronoi單元在稀疏圖上被分類為偏航約束區(qū)。每個Voronoi單元與被分類為偏航碰撞區(qū)的至少兩個元素等距。可選地，生成稀疏圖還包含將每個Voronoi單元歸類為邊或節(jié)點任一者。分類每個Voronoi單元可以包含執(zhí)行洪水填充算法。[0019]在一些實施方式中，規(guī)劃從第一節(jié)點至第二節(jié)點的粗略路徑包含修剪邊，并且每個經(jīng)修剪的邊包含在閾值長度以下并且被分類為偏航碰撞區(qū)或偏航約束區(qū)任一者的元素。確定沿著粗略路徑的圖像傳感器的視線丟失的點可以包含確定沿著規(guī)劃的粗略路徑的每個元素處的最小允許偏航和最大允許偏航，以及基于最小允許偏航和最大允許偏航確定最小包絡(luò)。該操作還可以包含確定在粗略路徑上的點處所需的偏航在最小包絡(luò)之外。[0020]在一些示例中，該操作還包含將具有高級路徑點和至少一個中間路徑點的導(dǎo)航路線發(fā)送到低級路徑生成器。該操作還可以包含確定是否將至少一個中間路徑點添加到導(dǎo)航路線，并且響應(yīng)于確定不將該至少一個中間路徑點添加到導(dǎo)航路線，將不變的導(dǎo)航路線傳遞到低級路徑生成器。[0021]本公開的另一方面提供了一種計算機實現(xiàn)的方法，包括：在機器人的數(shù)據(jù)處理硬件處接收導(dǎo)航路線，所述導(dǎo)航路線包括第一路徑點和第二路徑點；在所述數(shù)據(jù)處理硬件處，從圖像傳感器接收與所述機器人的環(huán)境相關(guān)聯(lián)的圖像數(shù)據(jù)；由所述數(shù)據(jù)處理硬件基于所述圖像數(shù)據(jù)確定從所述第一路徑點到所述第二路徑點的多條路徑；由所述數(shù)據(jù)處理硬件從所述多條路徑中選擇路徑，所述路徑包括至少一個中間路徑點；和由所述數(shù)據(jù)處理硬件命令所述機器人經(jīng)由所述第一路徑點、所述至少一個中間路徑點和所述第二路徑點、從所述環(huán)境中的起始位置到目的地位置的導(dǎo)航。[0022]本公開的另一方面提供了一種系統(tǒng)，包括：數(shù)據(jù)處理硬件；和與所述數(shù)據(jù)處理硬件通信的存儲器，所述存儲器存儲指令，其中所述指令由所述數(shù)據(jù)處理硬件執(zhí)行促使所述數(shù)據(jù)處理硬件：接收導(dǎo)航路線，所述導(dǎo)航路線包括第一路徑點和第二路徑點；從圖像傳感器接收與機器人的環(huán)境相關(guān)聯(lián)的圖像數(shù)據(jù)；基于所述圖像數(shù)據(jù)確定從所述第一路徑點到所述第二路徑點的多條路徑；從所述多條路徑中選擇路徑，所述路徑包括至少一個中間路徑點；和命令所述機器人經(jīng)由所述第一路徑點、所述至少一個中間路徑點和所述第二路徑點、從所述環(huán)境中的起始位置到目的地位置的導(dǎo)航。[0023]本公開的另一方面提供了一種機器人，包括：圖像傳感器；至少兩條腿；與所述圖像傳感器通信的數(shù)據(jù)處理硬件；和與所述數(shù)據(jù)處理硬件通信的存儲器，所述存儲器存儲指令，其中所述指令由所述數(shù)據(jù)處理硬件執(zhí)行促使所述數(shù)據(jù)處理硬件：接收導(dǎo)航路線，所述導(dǎo)航路線包括第一路徑點和第二路徑點；從所述圖像傳感器接收與所述機器人的環(huán)境相關(guān)聯(lián)的圖像數(shù)據(jù)；基于所述圖像數(shù)據(jù)確定從所述第一路徑點到所述第二路徑點的多條路徑；從所述多條路徑中選擇路徑，所述路徑包括至少一個中間路徑點；和命令所述機器人經(jīng)由所述第一路徑點、所述至少一個中間路徑點和所述第二路徑點、從所述環(huán)境中的起始位置到目的地位置的導(dǎo)航。[0024]本公開的另一方面提供了一種計算機實現(xiàn)的方法，當由機器人的數(shù)據(jù)處理硬件執(zhí)行時，促使所述數(shù)據(jù)處理硬件執(zhí)行操作，包括：從圖像傳感器接收機器人的環(huán)境的圖像數(shù)據(jù)；接收身體障礙物地圖，所述身體障礙物地圖包括所述機器人的身體不能穿越的障礙物的地圖；基于所述身體障礙物地圖生成稀疏圖，所述稀疏圖包括開始于起始位置并結(jié)束于目的地的一組節(jié)點和邊，所述節(jié)點和邊表示所述機器人可在所述環(huán)境中行進的路徑；規(guī)劃從所述起始位置到所述目的地的粗略路徑；確定沿著該組節(jié)點中的第一節(jié)點和該組節(jié)點中的第二節(jié)點之間的粗略路徑的、其中所述圖像傳感器的視線丟失的點；在沿著所述粗略路徑的其中所述圖像傳感器的視線丟失的所述點處生成中間路徑點；和沿著所述粗略路徑和所述中間路徑點從所述起始位置朝向所述目的地導(dǎo)航所述機器人。[0025]本公開的另一方面提供了一種機器人，包括：身體；腿，其耦接到所述身體，并被配置為在環(huán)境中操縱所述機器人；與所述腿通信的數(shù)據(jù)處理硬件；和與所述數(shù)據(jù)處理硬件通信的存儲器硬件，所述存儲器硬件存儲指令，所述指令當在所述數(shù)據(jù)處理硬件上執(zhí)行時，促使所述數(shù)據(jù)處理硬件執(zhí)行操作，包括：從圖像傳感器接收所述機器人的環(huán)境的圖像數(shù)據(jù)；接收身體障礙物地圖，所述身體障礙物地圖包括所述機器人的身體不能穿越的障礙物的地圖；基于所述身體障礙物地圖生成稀疏圖，所述稀疏圖包括開始于起始位置并結(jié)束于目的地的一組節(jié)點和邊，所述節(jié)點和邊表示所述機器人可在所述環(huán)境中行進的路徑；規(guī)劃從所述起始位置到所述目的地的粗略路徑；確定沿著該組節(jié)點中的第一節(jié)點和該組節(jié)點中的第二節(jié)點之間的粗略路徑的、其中所述圖像傳感器的視線丟失的點；在沿著所述粗略路徑的、其中所述圖像傳感器的視線丟失的所述點處，生成中間路徑點；和沿著所述粗略路徑和所述中間路徑點從所述起始位置朝向所述目的地導(dǎo)航所述機器人。[0026]本公開的另一方面提供了一種方法，包括：在機器人的數(shù)據(jù)處理硬件處接收導(dǎo)航所述導(dǎo)航路線基于表示在所述機器人要導(dǎo)航的區(qū)域中的靜態(tài)障礙物的位置的高級導(dǎo)航數(shù)沿著所述一系列高級路徑點和所述至少一個中間路徑點從所述起始位置朝向所述目的地所述導(dǎo)航路線基于表示在所述機器人要導(dǎo)航的區(qū)域中的靜態(tài)障礙物的位置的高級導(dǎo)航數(shù)述一系列高級路徑點和所述至少一個中間路徑點從所述起始位置朝向所述目的地位置導(dǎo)點添加到所述導(dǎo)航路線；和響應(yīng)于確定不將所述至少一個中間路徑點添加到所述導(dǎo)航路航的區(qū)域中的靜態(tài)障礙物的位置的高級導(dǎo)航數(shù)據(jù)；從圖像傳感器個中間路徑點從所述起始位置朝向所述目的地位置導(dǎo)航所述機器人；確定是否將所述至少一個中間路徑點添加到所述導(dǎo)航路線；和響應(yīng)于確定不將所述至少一個中間路徑點添加到所述導(dǎo)航路線，將未改變的導(dǎo)航路線傳遞到低級路徑生成器。[0030]在附圖和以下描述中闡述了本公開的一個或多個實施方式的細節(jié)。從說明書和附圖以及權(quán)利要求中，其他方面、特征和優(yōu)點將是顯而易見的。附圖說明[0031]圖1是對于機器人生成中間路徑點的導(dǎo)航系統(tǒng)的示例系統(tǒng)的示意圖。[0032]圖2A和圖2B是機器人使用高級路徑點對導(dǎo)航路線進行導(dǎo)航的示意圖。[0033]圖3是機器人使用高級路徑點和中間路徑點導(dǎo)航圖2A和圖2B的導(dǎo)航路線的示意[0034]圖4是圖1的導(dǎo)航系統(tǒng)的示例中間路徑點生成器的示意圖。[0035]圖5是經(jīng)壓縮配置空間地圖的示意圖。[0036]圖6是圖5的配置空間地圖與Voronoi單元重疊的示意圖。[0037]圖7是圖6的Voronoi單元的示意圖，示出了元素之間的距離和Voronoi單元的最近障礙物。[0038]圖8A-圖8E是填充圖6的Voronoi單元的洪水填充算法[0039]圖9是從圖6的Voronoi單元導(dǎo)出的邊和節(jié)點的示意圖。[0040]圖10是從圖6的Voronoi單元導(dǎo)出的經(jīng)修剪的邊和節(jié)點的示意圖。[0041]圖11A和圖11B是二維稀疏圖(圖11A)和SE2稀疏圖(圖11B)的示意圖。[0042]圖12A和圖12B是對于目標目的地的添加的節(jié)點的示意圖。[0043]圖13是穿過偏航自由區(qū)和偏航約束區(qū)的路徑的示意圖。[0044]圖14是穿過偏航約束區(qū)的路徑的示意圖。[0045]圖15A和圖15B是機器人的導(dǎo)航路線的示意圖，該導(dǎo)航路線包含放置在視線丟失位置的中間路徑點。[0046]圖16是用于生成機器人的導(dǎo)航系統(tǒng)的中間路徑點的示例方法的流程圖。[0047]圖17是可以用于實施本文所描述的系統(tǒng)和方法的示例計算設(shè)備的示意圖。[0048]不同附圖中相同的參考符號表示相同的元素。具體實施方式[0049]隨著有腿機器人設(shè)備(也稱為“機器人”)變得更加盛行，越來越需要機器人自主地在許多方面受限的環(huán)境中導(dǎo)航。通常，機器人依賴于存儲與大型和/或靜態(tài)物體(例如，墻壁、門等)相關(guān)的信息的高級地圖數(shù)據(jù)。當給定目的地目標時，機器人將通常首先從這個高級地圖中繪制路徑或道路來導(dǎo)航靜態(tài)障礙物，然后依賴于收集低級導(dǎo)航數(shù)據(jù)的感知系統(tǒng)以繞過行進中遇到的小型且動態(tài)物體進行導(dǎo)航。通常，在這類環(huán)境導(dǎo)航時，機器人會遇到高級地圖中沒有說明，但對于低級系統(tǒng)來說太大無法導(dǎo)航繞過的障礙物。在這些情況下，機器人變得被卡住或被困并不少見。本文的實施方式針對用于中間路徑點生成器的系統(tǒng)和方法，該中間路徑點生成器用于實時生成到高級路線的中間路徑點，從而允許有腿機器人設(shè)備有效地繞過更大的動態(tài)物體導(dǎo)航。[0050]參考圖1,機器人或機器人設(shè)備10包含具有兩條或更多條腿12的身體11,并執(zhí)行導(dǎo)的腳19是可選的，并且一條或多條腿12的下部分的終端(terminalend)可以耦接到輪子上，或者每條腿12的末端(distalend)可以直接接觸地面9.機器人10具有沿著直的重力軸Vg和質(zhì)心CM,質(zhì)心CM是機器人10的分布質(zhì)量的加權(quán)相對位置在其處總和為零的公開的范圍的情況下包含更多或更少的部分。第一部[0052]機器人10還包含具有至少一個成像傳感器或相機31的視覺系統(tǒng)30,每個傳感器或相機31以視角32并在視場34內(nèi)捕獲機器人10周圍環(huán)境8的圖像數(shù)據(jù)或傳感器數(shù)據(jù)17。視覺系統(tǒng)30可以被配置為通過調(diào)整視角32或者通過(獨立地或經(jīng)由機器人10任一者)平移和/或[0053]在一些實施方式中，視覺系統(tǒng)30的一個或多個相機31包含一個或多個立體相機[0054]視覺系統(tǒng)30向機器人10的數(shù)據(jù)處理硬件36提供圖像數(shù)據(jù)或傳感器數(shù)據(jù)17,該圖像[0055]在所示的示例中，導(dǎo)航系統(tǒng)100包含高級路徑點生成器110,其接收地圖數(shù)據(jù)50(即，表示機器人10要導(dǎo)航的區(qū)域中的靜態(tài)障礙物的位置的高級導(dǎo)航數(shù)據(jù))并為導(dǎo)航路線112生成一個或多個高級路徑點210(圖2A和2B),導(dǎo)航路線112繪制了從機器人10的當前位100還包含中間路徑點生成器120,其從視覺系統(tǒng)30接收導(dǎo)航路線112和圖像或傳感器數(shù)據(jù)17,并且包含中間路徑點生成器120?；趥鞲衅鲾?shù)據(jù)17,中間路徑點生成器120可以將一個或多個中間路徑點310(圖3)添加到導(dǎo)航路線112的高級路徑點210(圖2A、圖2B和圖3),其形成機器人10行進的粗略路徑或軌跡。導(dǎo)航路線112的高級路徑點210和任何添加的中間路徑點310被傳遞到低級路徑生成器130,低級路徑生成器130與傳感器數(shù)據(jù)17相結(jié)合地生成繪制機器人10的每個單獨腳步的腳步規(guī)劃142,以從機器人10的當前位置導(dǎo)航到下一路徑點210、310。使用腳步規(guī)劃142,機器人10通過將腳19或腿12的末端放置在由腳步規(guī)劃142指示的位置處的地面9上來遵循腳步規(guī)劃142,從而操縱穿過環(huán)境8。在一些實施方式中，低級路徑生成器130通過使用勢場方法來提供更低級障礙物避免，以避免大約四米尺度的障礙物。該勢場方法可以通過對朝向目標的速度和障礙物避免速度的總和進行集成來“推動”機器人10遠離障礙物。[0056]在一些實施方式中，導(dǎo)航系統(tǒng)100的至少一部分在與機器人10通信的遠程設(shè)備上執(zhí)行。例如，高級路徑點生成器110可以在遠程設(shè)備上執(zhí)行以生成一個或多個高級路徑點210,并且在機器人10上執(zhí)行的中間路徑點生成器120可以從遠程設(shè)備接收高級路徑點210?？蛇x地，整個導(dǎo)航系統(tǒng)100可以在遠程設(shè)備上執(zhí)行，并且遠程設(shè)備可以基于腳步規(guī)劃142控制/指示機器人10操縱環(huán)境8。[0057]現(xiàn)在參考圖2A和圖2B,低級路徑生成器130(使用，例如，勢場方法)在導(dǎo)航特定形狀和/或凸起的障礙物時可能會遇到問題。例如，低級路徑生成器130在試圖導(dǎo)航到對應(yīng)的導(dǎo)航路線112的高級路徑點210時，可能滑下障礙物或表面220并卡在局部最小值230中(圖2A)。在另一示例中，低級路徑生成器130可能缺乏關(guān)于使機器人10轉(zhuǎn)向的必要上下文(context)或決策制定能力。也就是說，低級路徑生成器130可能難以區(qū)分何時“轉(zhuǎn)向然后行[0058]現(xiàn)在參考圖3,將附加路徑點(即，中間路徑點310)添加到導(dǎo)航路線112有助于低級路徑生成器130作出恰當?shù)耐負錄Q策，因為附加的一個或多個路徑點310可以使軌跡對低級路徑生成器130呈現(xiàn)凸形，并且允許低級路徑生成器成功地繞過障礙物220導(dǎo)航。中間路徑點生成器120可以確保添加到導(dǎo)航路線112的任何添加的中間路徑點310離機器人10有足夠的距離，以最小化地圖抖動的影響。此外，中間路徑點生成器120可以避免移除或刪除任何高級路徑點210,因為高級路徑點生成器110可以知道對于中間路徑點生成器120不可用的附加地圖上下文，以及移除高級路徑點210可能產(chǎn)生不可預(yù)測的結(jié)果。[0059]現(xiàn)在參考圖4,在一些實施方式中，中間路徑點生成器120包含稀疏圖生成器410、粗略路徑規(guī)劃器420和路徑點放置器430。稀疏圖生成器410從例如感知系統(tǒng)102接收身體障礙物地圖412。身體障礙物地圖412是機器人10的緊鄰處(例如，四米內(nèi))的障礙物(例如，機器人10的身體11不能穿越的障礙物)的地圖。稀疏圖生成器410從身體障礙物地圖412生成稀疏圖416S。如下文更詳細討論的，稀疏圖416S提供了節(jié)點812(圖8A-圖8E)之間的一系列有效互連和邊810(圖8A-圖8E)。節(jié)點812和邊810表示穿過機器人10附近的偏航約束區(qū)(即，困難或嚴格操縱的區(qū)域)的有效潛在路徑，并且因此稀疏圖416S提供了確定機器人10穿過偏航約束區(qū)的潛在路徑所需的信息。[0060]稀疏圖生成器410將稀疏圖416S傳遞到粗略路徑規(guī)劃器420。粗略路徑規(guī)劃器420使用稀疏圖416S繪制從起始位置到目標目的地的粗略路徑1310(圖13)。在一些示例中，粗略路徑規(guī)劃器420通過使用搜索算法(例如，A*)來繪制粗略路徑1310,以確定由稀疏圖416S指示的有效潛在路徑(即，一系列節(jié)點812之間的互連和邊810)的最佳路線。粗略路徑規(guī)劃器420可以將路徑1310傳遞到路徑點放置器430。路徑點放置器430根據(jù)機器人10的當前位置確定當沿著路徑1310行進時視線丟失的位置，并將中間路徑點放置在該位置。也就是說，如果機器人10從當前位置沿著粗略路徑1310看，路徑點放置器確定其中機器人10將丟失路徑的視線(例如，因為障礙物)的位置，并將中間路徑點310放置在路徑1310上視線丟失的位置。中間路徑點310將引導(dǎo)機器人10到低級路徑生成器130能夠成功地導(dǎo)航障礙物的位置。中間路徑點310包含在導(dǎo)航路線112中，并被傳遞到低級路徑生成器130。[0061]在一些實施方式中，稀疏圖生成器410最初基于接收到的身體障礙物地圖412來生成完全配置空間地圖414.在一些示例中，完全配置空間地圖414包含元素510、510a-n的二維(2D)網(wǎng)格或陣列，其中每個元素510表示環(huán)境8的區(qū)域(例如，3厘米乘3厘米的平方),其指示障礙物是否阻止機器人10進入特定元素510?？蛇x地，完全配置空間地圖414是128個元素乘128個元素的陣列。在一些示例中，每個元素510可以與多個相應(yīng)的偏航配置512、512a-n(相應(yīng)的偏航配置集512、512a-n)相關(guān)聯(lián)，并且完全配置空間地圖414可以指示每個元素510的每個相應(yīng)的偏航配置512的狀態(tài)。例如，每個元素510可以與64個相應(yīng)偏航配置相關(guān)聯(lián)。在該示例中，每個偏航配置將從先前配置旋轉(zhuǎn)5.625度，因為360度(即，整圓)除以64(即，偏航配置的數(shù)量)等于5.625度。對于與相應(yīng)元素510相關(guān)聯(lián)的每個相應(yīng)偏航配置512,完全配置空間地圖414可以指示如果機器人10的選擇點占據(jù)由元素510表示的空間，相應(yīng)偏航配置512是否將導(dǎo)致與身體障礙物的碰撞。也就是說，完全配置空間地圖414可以指示每個偏航配置512是有效的(即，機器人10在該偏航配置512中不會與障礙物碰撞)還是無效的(即，機器人10在該偏航配置512中會與障礙物碰撞)。選擇點可以例如包含機器人10的身體11的中心點(例如，與每條腿12的頂部等距)。[0062]在一些實施方式中，稀疏圖生成器410從完全配置空間地圖414生成經(jīng)壓縮配置空間地圖500。經(jīng)壓縮配置空間地圖500可以對配置空間地圖500的每個元素510進行分類，而不是將每個元素與多個偏航配置512相關(guān)聯(lián)。例如，每個元素510可以被分類為身體障礙物元素510A(圖5)、偏航碰撞元素510B(圖5)、偏航自由元素510C(圖5)或偏航約束元素510D(圖5)。也就是說，來自完全配置空間地圖414的偏航配置512可以用于對經(jīng)壓縮配置空間地圖500的每個元素510進行分類。[0063]現(xiàn)在參考圖5,示出了示例性經(jīng)壓縮配置空間地圖500。在該示例中，經(jīng)壓縮配置空間地圖500包含128乘128個元素510的網(wǎng)格，每個元素被分類為身體障礙物元素510、偏航碰撞元素510B、偏航自由元素510C或偏航約束元素510D。身體障礙物元素510A表示機器人10不能穿越的障礙物(即，從身體障礙地圖412接收的障礙物)占據(jù)的元素。例如，機器人10必須避免的椅子、箱子或墻壁可以被分類為身體障礙物元素510A。偏航碰撞元素510B是其中當機器人10的選擇點(例如，身體11的中心)占據(jù)由元素510B表示的空間時，機器人10的所有偏航配置512(例如，所有64個偏航配置)導(dǎo)致與身體障礙物(即，身體障礙物元素510A)碰撞的元素。例如，緊鄰墻壁的空間，盡管實際上不含有墻壁，但對于機器人10可以太靠近墻壁以至于無法站立而不與墻壁碰撞。[0064]偏航自由元素510C與偏航碰撞元素510B相反，因為沒有偏航配置512將導(dǎo)致與身體障礙物的碰撞。換句話說，偏航自由元素510C表示環(huán)境8中機器人10可以旋轉(zhuǎn)穿過所有偏航配置512(即，以在選擇點處的軸心旋轉(zhuǎn)360度)而不與身體障礙物碰撞的區(qū)域。偏航約束元素510D是其中一些偏航配置512是安全的或有效的(即，機器人10不會與障礙物碰撞),而一些偏航配置512是不安全的(即，無效的偏航配置512,其中機器人10在那些偏航配置512中將與障礙物碰撞)的元素。例如，機器人10可以能夠靠近并平行于墻壁行進，但是轉(zhuǎn)向90度可能導(dǎo)致與墻壁碰撞。在該示例中，一些偏航配置512(即，機器人10平行于墻壁的偏航配置512)是安全的，而其他(即，機器人10垂直于墻壁的偏航配置512)是不安全的。[0065]在一些示例中，稀疏圖生成器410確定穿過經(jīng)壓縮配置空間地圖500的偏航約束區(qū)510DZ(即，偏航約束元素510D的區(qū)域)的有效路徑?，F(xiàn)在參考圖6,在一些實施方式中，稀疏圖生成器410用多個Voronoi單元610重疊到經(jīng)壓縮配置空間地圖500.Voronoi單元610包含偏航約束區(qū)510DZ和/或偏航自由區(qū)510CZ中的所有元素510,這些元素與被分類為偏航碰撞元素510B的至少兩個元素510等距。換句話說，Voronoi單元610是離偏航碰撞區(qū)510BZ最遠(因此離身體障礙物最遠)的元素510。替代地，Voronoi單元610包含偏航約束區(qū)510DZ和/或偏航自由區(qū)510CZ中的所有元素510,這些元素與至少兩個身體障礙物元素510A等距。在圖6的示例中，單元610位于偏航碰撞區(qū)510BZ之間的偏航自由區(qū)510CZ和偏航約束區(qū)510DZ的中心。Voronoi單元610易于根據(jù)機器人10可以已經(jīng)訪問的數(shù)據(jù)(例如，有符號的距離場)來[0066]為了確定被標記為Voronoi單元610的元素510,稀疏圖生成器410確定(配置空間地圖500的)與配置空間地圖500上的障礙物(即，身體障礙物元素510A)等距的元素510。也就是說，每個元素510固有地具有到最近障礙物邊界的距離和方向。圖7描繪了配置空間地圖500的一部分，包含由偏航約束區(qū)510DZ分開的兩個偏航碰撞區(qū)510BZ。一些Voronoi單元610穿過偏航約束區(qū)510DZ并在偏航碰撞區(qū)510BZ之間。在一些示例中，稀疏圖生成器分析配置空間地圖500的每個元素510,以確定元素510是否應(yīng)該被標記為Voronoi單元610。當分析每個元素510以確定元素510是否是Voronoi單元610時，在一些實施方式中，稀疏圖生成器410確定元素510(即，當前正在被分析的元素510)和相鄰元素510是否指向基本不同的位置作為最近障礙物邊界。也就是說，對于配置空間地圖500中的每個元素510,稀疏圖生成器410可以定位到相應(yīng)元素的最近障礙物邊界、相應(yīng)元素的底部相鄰的最近障礙物邊界以及相應(yīng)元素的右側(cè)相鄰的最近障礙物邊界。每當三個最近障礙物邊界中的任何兩個之間的距離滿足閾值距離時，元素510可以被標記為Voronoi單元610。閾值距離可以被表示為任意數(shù)[0067]在所示的示例中，當稀疏圖生成器410分析被標為“A”的元素510時，稀疏圖生成器410確定與元素“A”最近偏航碰撞元素510B(或身體障礙物元素510A)是元素510a。稀疏圖生成器410然后確定與元素(標為“B”)的右側(cè)相鄰最近偏航碰撞元素510B,其在這種情況下是元素510b。稀疏圖生成器410然后可以確定從元素的底部相鄰(標為“C”)到最近偏航碰撞元素510B(在這種情況下，也是元素510a)的距離。在一些示例中，稀疏圖生成器410可以確定距離中的兩個)是否在相距閾值距離內(nèi)。當元素具有相距相同距離的兩個障礙物邊界時，稀疏圖生成器410可以確定兩個元素之間的距離。[0068]在該示例中，“A”和“B”的最近障礙物邊界之間的距離是十個元素，“A”和“C”的最近障礙物邊界之間的距離是零個元素(即它們共享相同的最近障礙物邊界),并且“B”和“C”的最近障礙物邊界之間的距離也是十個元素。當閾值距記為Voronoi單元610。[0069]如前所討論的，稀疏圖生成器410可以為配置空間地圖500的每個元素進行類似的分析。繼續(xù)參考圖7,稀疏圖生成器410可以不將元素“D”標記為Voronoi單元610,因為與其是因為最近障礙物邊界(即，元素510c、510d)之間的距離僅僅是一個元素，這可能不滿足閾值。[0070]現(xiàn)在參考圖8A-圖8E,在一些實施方式中，稀疏圖生成器410確定從Voronoi單元610導(dǎo)出的邊810和節(jié)點812。圖8A示出了在偏航約束區(qū)510DZ中的示例性Voronoi單元610。在一些實施方式中，稀疏圖生成器選擇被標記為Voronoi單元610的任意(即，隨機或接近隨機)元素510ff。從任意元素510ff起始，稀疏圖生成器執(zhí)行洪水填充，并記錄從被標記為Voronoi單元610的每個元素510到任意選擇的元素510ff的距離。在所示的示例中，每個元素都用距任意元素510ff的距離(以元素為單位)來標記。洪水填充是一種確定連接到陣列中給定節(jié)點的區(qū)域的算法。在該情況下，洪水填充繼續(xù)流過被標記為Voronoi單元610的所有元素510,直到所有元素都被分配了距離。雖然可以完全隨機地選擇任意選擇的元素510ff,但是限制對在機器人10附近的元素510的選擇可以是有利的，以便最小化來自任何誤差的影響。[0071]在被標記為Voronoi單元610的每個元素被分配了距離之后，在一些示例中，稀疏圖生成器410確定Voronoi單元610的每個分支的端或端節(jié)點812。每個分支的端節(jié)點812將與任意選擇的元素510ff具有局部最大的距離。在一些示例中，稀疏圖生成器410從分支的端節(jié)點812開始標記每個元素510,同時朝向選擇的元素510ff往回行進。每當稀疏圖生成器410遇到先前已經(jīng)被標記的元素510時，該生成器可以將唯一的標簽附加到元素的組合。例如，在圖8B中，稀疏圖生成器410起始于端節(jié)點812a處，并朝著選擇的元素510ff往回行進，沿途標記每個元素以形成邊810a。也就是說，從端節(jié)點812a到選擇的元素510ff的Voronoi單元610可以形成邊810a。稀疏圖生成器410可以繼續(xù)該過程，直到所有元素都已被標記。例如，在圖8C中，稀疏圖生成器410從端節(jié)點812b向元素510ff行進，并標記每個元素以形成另一個邊810b,直到在812c遇到先前標記的元素(圖8B)。稀疏圖生成器410可以在812c處為連接點(junction)元素(即，遇到的先前已經(jīng)標記的第一個元素)分配唯一的標簽。稀疏圖生成器410可以繼續(xù)往回行進，直到到達選擇的元素510ff處，注意先前被標記為分開的邊810c的每個元素。[0072]現(xiàn)在參考圖8D,稀疏圖生成器410可以從端節(jié)點812d起始，并往回行進到元素510ff,再次標記沿途的每個元素以形成另一個邊810d。在所有元素510都已被標記(并被分配給邊810)之后，在一些實施方式中，稀疏圖生成器410確定選擇的元素510ff是否僅接觸兩個邊810(即，不是三個或更多個邊之間的連接點)。在這種情形下，稀疏圖生成器410可以將兩個邊組合成單個邊。例如，如圖8D所示，選擇的元素510ff僅接觸兩個其他邊(即，邊810c和邊810d),并且在圖8E中，邊810c和邊810d被組合成單個邊810.洪水填充和元素標記的最終結(jié)果向稀疏圖生成器410提供了沿著邊810的元素510的有序集和一系列節(jié)點元素812。一系列節(jié)點和邊形成稀疏圖416S,并表示機器人10可以行進穿過附近環(huán)境的約束空間(即，經(jīng)壓縮配置空間地圖500的偏航約束區(qū)510DZ)的有效路徑。[0073]圖9示出了配置空間地圖500,其重疊有分類為多個邊810和節(jié)點812的Voronoi單元610,每個邊810連接到另一個邊810(通過節(jié)點812)或者到偏航自由區(qū)510CZ(也通過節(jié)點812)任一者。在一些實施方式中，當生成稀疏圖416S時，稀疏圖生成器410僅考慮被標記為位于偏航約束區(qū)510DZ中的Voronoi單元610的元素510,因為穿過偏航自由區(qū)510DZ的路徑可以在稍后確定。如參考圖8A-圖8E所討論的，稀疏圖生成器410可以將被標記為Voronoi單元610的元素分割成單獨的邊810和節(jié)點812。在一些示例中，稀疏圖生成器410標記或識別在其處邊810連接到偏航自由區(qū)510CZ的節(jié)點812。也就是說，稀疏圖生成器410識別沿著連接偏航自由區(qū)510CZ和偏航約束區(qū)510DZ的Voronoi單元610的節(jié)點812(即，端或邊810或邊810之間的連接點)。稀疏圖生成器410還可以識別是多個邊810的連接點的節(jié)點812。在一些示例中，稀疏圖生成器410假設(shè)連接到同一偏航自由區(qū)510CZ的所有節(jié)點812彼此連接。也就是說，只要節(jié)點812之間存在路徑(即，連接到同一偏航自由區(qū)510CZ),稀疏圖生成器就可以(至少暫時)忽略穿過偏航自由區(qū)510CZ的運動。擁有邊810和節(jié)點812,稀疏圖生成器410可以首先基于與Voronoi單元610重疊的經(jīng)壓縮配置空間地圖500中先前確定的邊810和節(jié)點812,通過修剪掉不具有導(dǎo)航顯著性的邊810,生成最終2D配置地圖1000(圖10)。例如，圖10示出了經(jīng)壓縮配置空間地圖500,其覆蓋有多個Voronoi單元610,并且具有被修剪以生成最終2D配置地圖1000的多個不顯著的邊1010。也就是說，在一些實施方式中，稀疏圖生成器410修剪比閾值長度更短并且終止或結(jié)束于偏航約束區(qū)域510DZ內(nèi)的不顯著的邊1010,因為這些路徑極不可能值得機器人10穿越?？蛇x地，閾值長度可以大約是機器人10的半徑。在一些示例中，當在修剪之后，連接點節(jié)點812連接到少于三個邊810時，稀疏圖生成器410將邊810組合在一起。[0074]現(xiàn)在參考圖11A和圖11B,在一些實施方式中，稀疏圖生成器410將最終2D配置地圖1000(圖11A)轉(zhuǎn)換成該圖的SE2表示1100(圖11B)。SE2是坐標系，其包含具有標準笛卡爾坐標的偏航(即x坐標、y坐標和偏航)。也就是說，SE2圖1100采用最終2D配置地圖1000,并且包含偏航。圖11B示出了SE2圖1100,其中偏航是高度。雖然機器人10可以具有任意數(shù)量的偏航配置512(例如，如前所討論的64),但是可以通過僅考慮兩個偏航配置——向前和向后來簡化SE2圖1100。也就是說，通常，機器人10將在與其行進路徑對齊的偏航配置512中行進，因此，通過僅考慮這兩種偏航配置就可以極大地簡化SE2圖1100.2D地圖1000的每個邊810可節(jié)點812(圖11A)由連接到2D地圖1000表示中的節(jié)點812的數(shù)量的兩倍數(shù)量的邊1110(圖11B)表示。例如，圖11A示出了在單個節(jié)點812處連接的三個邊810,這轉(zhuǎn)化為SE2圖1100中的六個節(jié)點1112。這意味著機器人10將在節(jié)點1112處原地旋轉(zhuǎn)，并且稀疏圖生成器410可以基于來自完全配置空間地圖414的有效偏航配置512來確定節(jié)點1112之間的互連。[0075]為了最終確定SE2地圖1100,在一些實施方式中，稀疏圖生成器410從地圖1100中為機器人10確定入口點和出口點。現(xiàn)在參考圖12A和圖12B,稀疏圖生成器410可以沿著直線將地圖外目標1210(即，目標目的地)投影到地圖1100邊界。當目標1210被設(shè)置在偏航自由區(qū)510CZ中時，稀疏圖生成器410可以使用與目標1210相關(guān)聯(lián)的相應(yīng)元素。然而，當在偏航約束區(qū)510DZ中時，稀疏圖生成器410可以沿著被標記為Voronoi單元610(來自2D地圖1000)或偏航自由區(qū)510CZ邊界的最近元素510進行搜索。如果最近元素在偏航自由區(qū)510CZ邊界上，稀疏圖生成器410可以將該元素設(shè)置為目標。當最近元素在邊緣810上被標記為Voronoi單元610時，稀疏圖生成器410可以通過在相應(yīng)最近元素處放置新的節(jié)點1220來將邊810一分為二。在圖12A所示的示例中，目標12近期望元素是Voronoi單元610。稀疏圖生成器410在最接近目標1210的元素處創(chuàng)建新的節(jié)點1220,并將先前的邊810分成兩個獨立的邊810。在一些實施方式中，稀疏圖生成器410創(chuàng)建兩個新的節(jié)點1220,其中一個節(jié)點1220表示向前偏航配置512,一個節(jié)點1220表示向后偏航配置512。[0076]一旦已放置了新的節(jié)點1220,稀疏圖生成器410確定機器人10的起始位置(例如，機器人的當前位置)是否連接向前偏航配置節(jié)點1220、向后偏航配置節(jié)點1220或兩者。也就是說，稀疏圖生成器410確定機器人10是否能夠連接到具有相應(yīng)的偏航配置的節(jié)點1220。在一些示例中，稀疏圖生成器410確定原始或真實目標1210和沿著新的節(jié)點1220的邊810的兩個偏航配置(即，向前和向后)之間的角度1222。在圖12B所示的示例中，當角度滿足閾值時(例如，當角度在區(qū)域1230內(nèi)時),面向前方的節(jié)點1220連接到機器人的位置。當角度滿足第二閾值時(例如，當角度在區(qū)域1240內(nèi)時),面向后方的節(jié)點1220連接到機器人的位置。當角度滿足第三閾值時(例如，當角度在區(qū)域1250內(nèi)時),面向前方的節(jié)點1220和面向后方的節(jié)點1220都連接到機器人的起始位置。也就是說，機器人10可以向前或向后任一者行進到節(jié)點1220的位置。[0077]在一些示例中，稀疏圖生成器410連接指示機器人10將與障礙物碰撞的節(jié)點812。例如，稀疏圖生成器410可以總是假設(shè)機器人通過從中心點旋轉(zhuǎn)而轉(zhuǎn)向，這可能使得一些轉(zhuǎn)向是不可能的。然而，在一些情況下，低級路徑生成器130仍然能夠通過打開不在機器人10中心處的樞軸點來導(dǎo)航路徑，并且在這些情況下，稀疏圖生成器410可以在節(jié)點812之間創(chuàng)建邊810,否則生成器120可以確定機器人不能穿越這些邊。[0078]返回參考圖4,中間路徑點生成器120還包含粗略路徑規(guī)劃器420,其被配置為從稀疏圖生成器410接收稀疏圖416S,并確定機器人10行進以到達目標1210(即，對應(yīng)于目標目的地的節(jié)點1220(圖12A))的拓撲正確路徑(即，粗略路徑1310)。在一些實施方式中，粗略路徑規(guī)劃器420還接收完全配置空間地圖414和/或經(jīng)壓縮配置空間地圖500?，F(xiàn)在參考圖4和圖13,地圖1100包含粗略路徑1310,該粗略路徑1310從偏航自由區(qū)510CZ中的起始點1320導(dǎo)航，穿過偏航約束區(qū)510DZ到達另一個偏航區(qū)自由510CZ。[0079]為了生成路徑1