[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

TWI687191B - 用於多個清潔裝置之任務區域分配方法以及其系統 - Google Patents

用於多個清潔裝置之任務區域分配方法以及其系統 Download PDF

Info

Publication number
TWI687191B
TWI687191B TW107137349A TW107137349A TWI687191B TW I687191 B TWI687191 B TW I687191B TW 107137349 A TW107137349 A TW 107137349A TW 107137349 A TW107137349 A TW 107137349A TW I687191 B TWI687191 B TW I687191B
Authority
TW
Taiwan
Prior art keywords
task
sub
cleaning
region
regions
Prior art date
Application number
TW107137349A
Other languages
English (en)
Other versions
TW202015606A (zh
Inventor
徐道智
王揚生
陳俊廷
陳宇晴
Original Assignee
廣達電腦股份有限公司
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by 廣達電腦股份有限公司 filed Critical 廣達電腦股份有限公司
Priority to TW107137349A priority Critical patent/TWI687191B/zh
Priority to CN201811275903.5A priority patent/CN111178646B/zh
Priority to US16/410,193 priority patent/US10824166B2/en
Application granted granted Critical
Publication of TWI687191B publication Critical patent/TWI687191B/zh
Publication of TW202015606A publication Critical patent/TW202015606A/zh

Links

Images

Classifications

    • G—PHYSICS
    • G05—CONTROLLING; REGULATING
    • G05D—SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES
    • G05D1/00—Control of position, course, altitude or attitude of land, water, air or space vehicles, e.g. using automatic pilots
    • G05D1/02—Control of position or course in two dimensions
    • G05D1/021—Control of position or course in two dimensions specially adapted to land vehicles
    • G05D1/0287—Control of position or course in two dimensions specially adapted to land vehicles involving a plurality of land vehicles, e.g. fleet or convoy travelling
    • G—PHYSICS
    • G05—CONTROLLING; REGULATING
    • G05D—SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES
    • G05D1/00—Control of position, course, altitude or attitude of land, water, air or space vehicles, e.g. using automatic pilots
    • G05D1/02—Control of position or course in two dimensions
    • G05D1/021—Control of position or course in two dimensions specially adapted to land vehicles
    • G05D1/0268—Control of position or course in two dimensions specially adapted to land vehicles using internal positioning means
    • G05D1/0274—Control of position or course in two dimensions specially adapted to land vehicles using internal positioning means using mapping information stored in a memory device
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06Q—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
    • G06Q10/00—Administration; Management
    • G06Q10/06—Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
    • G06Q10/063—Operations research, analysis or management
    • G06Q10/0631—Resource planning, allocation, distributing or scheduling for enterprises or organisations
    • G06Q10/06311—Scheduling, planning or task assignment for a person or group
    • A—HUMAN NECESSITIES
    • A47—FURNITURE; DOMESTIC ARTICLES OR APPLIANCES; COFFEE MILLS; SPICE MILLS; SUCTION CLEANERS IN GENERAL
    • A47L—DOMESTIC WASHING OR CLEANING; SUCTION CLEANERS IN GENERAL
    • A47L11/00—Machines for cleaning floors, carpets, furniture, walls, or wall coverings
    • A47L11/40—Parts or details of machines not provided for in groups A47L11/02 - A47L11/38, or not restricted to one of these groups, e.g. handles, arrangements of switches, skirts, buffers, levers
    • A47L11/4011—Regulation of the cleaning machine by electric means; Control systems and remote control systems therefor
    • G—PHYSICS
    • G05—CONTROLLING; REGULATING
    • G05D—SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES
    • G05D1/00—Control of position, course, altitude or attitude of land, water, air or space vehicles, e.g. using automatic pilots
    • G05D1/02—Control of position or course in two dimensions
    • G05D1/021—Control of position or course in two dimensions specially adapted to land vehicles
    • G05D1/0212—Control of position or course in two dimensions specially adapted to land vehicles with means for defining a desired trajectory
    • G05D1/0217—Control of position or course in two dimensions specially adapted to land vehicles with means for defining a desired trajectory in accordance with energy consumption, time reduction or distance reduction criteria
    • G—PHYSICS
    • G05—CONTROLLING; REGULATING
    • G05D—SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES
    • G05D1/00—Control of position, course, altitude or attitude of land, water, air or space vehicles, e.g. using automatic pilots
    • G05D1/02—Control of position or course in two dimensions
    • G05D1/021—Control of position or course in two dimensions specially adapted to land vehicles
    • G05D1/0212—Control of position or course in two dimensions specially adapted to land vehicles with means for defining a desired trajectory
    • G05D1/0219—Control of position or course in two dimensions specially adapted to land vehicles with means for defining a desired trajectory ensuring the processing of the whole working surface
    • G—PHYSICS
    • G05—CONTROLLING; REGULATING
    • G05D—SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES
    • G05D1/00—Control of position, course, altitude or attitude of land, water, air or space vehicles, e.g. using automatic pilots
    • G05D1/02—Control of position or course in two dimensions
    • G05D1/021—Control of position or course in two dimensions specially adapted to land vehicles
    • G05D1/0287—Control of position or course in two dimensions specially adapted to land vehicles involving a plurality of land vehicles, e.g. fleet or convoy travelling
    • G05D1/0291—Fleet control
    • G05D1/0297—Fleet control by controlling means in a control room
    • A—HUMAN NECESSITIES
    • A47—FURNITURE; DOMESTIC ARTICLES OR APPLIANCES; COFFEE MILLS; SPICE MILLS; SUCTION CLEANERS IN GENERAL
    • A47L—DOMESTIC WASHING OR CLEANING; SUCTION CLEANERS IN GENERAL
    • A47L2201/00—Robotic cleaning machines, i.e. with automatic control of the travelling movement or the cleaning operation
    • A47L2201/04—Automatic control of the travelling movement; Automatic obstacle detection

Landscapes

  • Engineering & Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • Radar, Positioning & Navigation (AREA)
  • General Physics & Mathematics (AREA)
  • Automation & Control Theory (AREA)
  • Remote Sensing (AREA)
  • Aviation & Aerospace Engineering (AREA)
  • Business, Economics & Management (AREA)
  • Human Resources & Organizations (AREA)
  • Economics (AREA)
  • Entrepreneurship & Innovation (AREA)
  • Strategic Management (AREA)
  • Educational Administration (AREA)
  • Tourism & Hospitality (AREA)
  • General Business, Economics & Management (AREA)
  • Quality & Reliability (AREA)
  • Theoretical Computer Science (AREA)
  • Operations Research (AREA)
  • Marketing (AREA)
  • Game Theory and Decision Science (AREA)
  • Development Economics (AREA)
  • Control Of Position, Course, Altitude, Or Attitude Of Moving Bodies (AREA)
  • Cleaning Or Drying Semiconductors (AREA)

Abstract

一種用於多個清潔裝置之任務區域分配方法，包括：根據對應於任務地圖之外形之複數凹角將任務地圖分割為複數基本子區域；合併每兩個相鄰的基本子區域，並計算對應於每個合併的基本子區域所對應之基本清掃時間；根據基本清掃時間重複合併每兩個相鄰的基本子區域，並取得基本分區結果；根據基本分區結果中複數任務子區域之位置選擇複數起始區塊；根據每個起始區塊之位置、每個任務子區域之位置以及對應於每個任務子區域之清掃時間合併任務子區域，並取得任務區域分配結果；根據清潔裝置之位置以及任務分配結果致使清潔裝置執行清掃任務。

Description

用於多個清潔裝置之任務區域分配方法以及其系統
本發明係有關於一種清潔裝置之任務區域分配方法、清潔裝置任務分配系統以及清潔裝置。
隨著科技之進步，清潔裝置，如掃地機器人於生活上的應用已相當地廣泛。然而，由於在居家環境中需要清掃的區域通常並非為由單一個矩形所構成，而現有的任務區域分配方法為清掃完具有固定大小的任務區域後，再行走至下一個任務區域進行清掃，如此清潔裝置將執行過多不必要的轉彎動作，從而增加清掃的時間，使得清掃效率不佳。因此，如何有效率地切割清掃區域以增加清掃的效率為目前所需解決之問題。
本發明一實施例提供一種用於多個清潔裝置之任務區域分配方法，包括：取得一任務地圖；取得對應於任務地圖之一外形；根據外形之複數凹角將任務地圖分割為複數基本子區域；合併每兩個相鄰的基本子區域，並計算對應於每個合併的基本子區域所對應之一基本清掃時間，其中每兩個相鄰的基本子區域具有共同且長度相同的邊；根據基本清掃時間之長 短重複合併每兩個相鄰的基本子區域直到所有相鄰的基本子區域不具有共同且長度相同的邊為止，並取得一基本分區結果；根據基本分區結果中複數任務子區域之位置選擇複數起始區塊，其中起始區塊的數量等於複數清潔裝置之數量；根據每個起始區塊之一位置、每個任務子區域之一位置以及對應於每個任務子區域之一清掃時間合併任務子區域，直到剩餘的任務子區域的數量等於清潔裝置之數量為止，並取得一任務區域分配結果；根據清潔裝置之位置以及任務分配結果致使每個清潔裝置執行一清掃任務。
本發明另一實施例提供一種清潔裝置任務分配系統，包括複數清潔裝置以及一控制端。控制端包括一第一儲存單元以及一第一處理單元。第一儲存單元儲存一任務地圖。第一處理單元用以：自第一儲存單元取得任務地圖；取得對應於任務地圖之一外形；根據外形之複數凹角將任務地圖分割為複數基本子區域；合併每兩個相鄰的基本子區域，並計算對應於每個合併動作之一基本清掃時間，其中每兩個相鄰的基本子區域具有共同且長度相同的邊；根據基本清掃時間之長短重複合併每兩個相鄰的基本子區域直到所有相鄰的基本子區域不具有共同且長度相同的邊為止，並取得一基本分區結果；根據基本分區結果中複數任務子區域之位置選擇複數起始區塊，其中起始區塊的數量等於複數清潔裝置之數量；根據每個起始區塊之一位置、每個任務子區域之一位置以及對應於每個任務子區域之一清掃時間合併任務子區域，直到剩餘的任務子區域的數量等於清潔裝置之數量為止，並取得一任務區域分配結果；以 及根據清潔裝置之位置以及任務分配結果分配一清掃任務給每個清潔裝置。每個清潔裝置包括一第二儲存單元以及一第二處理單元。第二儲存單元儲存任務區域分配結果。第二處理單元根據任務區域分配結果執行清掃任務。
110‧‧‧控制端
111‧‧‧第一處理單元
112‧‧‧第一儲存單元
120‧‧‧清潔裝置
121‧‧‧第二處理單元
122‧‧‧第二儲存單元
200‧‧‧任務地圖
201~213‧‧‧基本子區域
201’、202’‧‧‧合併的基本子區域
251~255‧‧‧凹角
270‧‧‧最小清掃單位
301a、301b、401~405、601~606、701~706、901~904‧‧‧任務子區域
350‧‧‧清掃起點
510、520、610~630、710~740‧‧‧分配給不同清潔裝置的任務區域
801~805‧‧‧不同任務子區域之中心
850‧‧‧任務地圖之中心
R1~R4‧‧‧清潔裝置之起始清掃位置
S1001~S1021‧‧‧步驟流程
第1圖係顯示根據本發明一實施例所述之清潔裝置任務分配系統之系統架構圖。
第2A~2D圖係顯示根據本發明一些實施例所述之任務地圖以及將任務地圖切割為複數任務子區域之示意圖。
第3A、3B圖係顯示根據本發明一些實施例所述之清潔裝置清掃路徑之示意圖。
第4圖係顯示根據本發明一實施例所述之對應於一任務地圖之基本分區結果之示意圖
第5圖係顯示根據本發明一實施例所述之對應於兩個清潔裝置之最佳化分區之示意圖。
第6A、6B圖係顯示根據本發明一實施例所述之對應於三個清潔裝置之最佳化分區之示意圖。
第7A~7C圖係顯示根據本發明一實施例所述之對應於四個清潔裝置之最佳化分區之示意圖。
第8圖係顯示根據本發明一實施例所述之任務地圖之中心以及各個任務子區域之中心之示意圖。
第9圖係顯示根據本發明一實施例所述之合併相鄰的任務子區域之示意圖。
第10圖係顯示根據本發明一實施例所述之清潔裝置之任務區域分配方法之示意圖。
有關本發明之用於多個清潔裝置之任務分配方法以及其系統適用之其他範圍將於接下來所提供之詳述中清楚易見。必須了解的是下列之詳述以及具體之實施例，當提出有關用於多個清潔裝置之任務分配方法以及其系統之示範實施例時，僅作為描述之目的以及並非用以限制本發明之範圍。
第1圖係顯示根據本發明一實施例所述之清潔裝置任務區域分配系統之系統架構圖。任務分配系統可包括一控制端110以及複數清潔裝置1201~120n。控制端110可實施於例如桌上型電腦、筆記型電腦、平板電腦或者智慧型手機等的電子裝置中，且至少包含一第一處理單元111、一第一儲存單元112以及一第一通訊介面。第一處理單元111可透過多種方式實施，例如以專用硬體電路或者通用硬體(例如，單一處理器、具平行處理能力之多處理器、圖形處理器或者其它具有運算能力之處理器)，且於執行程式碼或者軟體時，提供之後所描述的功能。第一儲存單元112用以儲存至少一任務地圖、根據任務地圖所產生的任務相關資訊等，以供第一處理單元111於執行相關運算時進行存取。其中，第一儲存單元112可為硬碟、快閃記憶體、ROM等非揮發性儲存裝置。此外，控制端110更可包括一無線通訊介面(未顯示)，無線通訊介面可為區域網路(local area network,LAN)通訊模組、無線區域網路通訊模組(WLAN)或藍芽(Bluetooth)通訊模組等，用以與清潔 裝置120交換各種訊號以及數據。於一具體實施例中，清潔裝置例如為掃地機器人。
清潔裝置1201~120n之每一者至少包含一第二處理單元121以及一第二儲存單元122。同樣地，第二處理單元121可透過多種方式實施，例如以專用硬體電路或者通用硬體，且於執行程式碼或者軟體時，提供之後所描述的功能。第二儲存單元122可為硬碟、快閃記憶體、ROM等非揮發性儲存裝置，用以儲存任務地圖以及自控制端110所接收到的與清掃任務相關的資訊等。第二處理單元121用以根據接收到的任務地圖執行清掃任務，或者執行與清掃任務相關之計算。
第2A~2D圖係顯示根據本發明一實施例所述之任務地圖以及複數任務子區域之合併之示意圖。根據本發明一實施例，當控制端110之第一處理單元111接收到任務地圖200後(如第2A圖所示)，首先取得任務地圖200之外形，並根據外形取得任務地圖200中的每一個凹角(如圖中所示之凹角251~255)，以進行後續的任務子區域切割作業。其中，第2A圖中所示之方塊270表示清潔裝置120所能清掃的最小清掃單位，其主要用以估算清掃每個任務子區域所需的時間。接著，第一處理單元111以任務地圖之每個凹角為基準點將任務地圖200切割為複數基本子區域。舉例來說，當以凹角251~255為基準點對第2A圖所示之任務地圖進行縱向以及橫向的切割後，可取得如第2B圖所示之複數個基本子區域201~213。
於取得多個基本子區域201~213後，第一處理單元111將相鄰且鄰接的基本子區域合併，並計算合併的子區域所 對應的清掃時間。其中，合併的兩個基本子區域具有共同且長度相同的邊。舉例來說，如第2B圖所示，由於基本子區域201與基本子區域202相鄰且鄰接，以及基本子區域201右側的邊與基本子區域202左側的邊的長度相同，因此第一處理單元111將基本子區域201與基本子區域202合併為如第2C圖所示之另一個較大的子區域201’(第一合併結果)，並計算清掃子區域201’所需的時間。同樣地，如第2B圖所示，由於基本子區域202與基本子區域205相鄰且鄰接，且基本子區域202下側的邊與基本子區域205上側的邊的長度相同，因此第一處理單元111將基本子區域202與基本子區域205合併為如第2D圖所示之另一個較大的子區域202’(第二合併結果)，並計算清掃子區域202’所需的時間，以此類推。當第一處理單元111將每兩個基本子區域合併並計算清掃合併的子區域所需的時間後，留下時間最短的前三者作為”第一次合併結果”。接著，第一處理單元111執行第二次的合併動作。其中，第二次的合併動作如前所述，第一處理單元111合併具有共同且長度相同的邊的兩個基本子區域或者合併的子區域，並計算其所對應的清掃時間，並留下時間最短的前三者作為第二次合併結果。以此類推，第一處理單元111重複執行前述之合併動作，直到所有合併過的任務子區域不具有共同且長度相同的邊為止。其中，第一處理單元111更將最後的合併結果儲存為一”基本分區結果”。
其中，於計算子區域所對應之清掃時間時，第一處理單元111更根據子區域的短邊的長度套用不同的公式。舉例來說，第3A、3B圖係顯示根據本發明一些實施例所述之清 潔裝置清掃路徑之示意圖。其中，由於清潔裝置清掃一個最小清掃單位所需的時間小於轉彎所需耗費的時間，因此清潔裝置於清掃一個任務子區域時，最佳的清掃路徑為轉彎次數最少的路徑。於本發明之一些實施例中，清掃任務子區域的方式係透過沿著長邊清掃以最少化轉彎的次數。舉例來說，如第3A圖所示，任務子區域301a的大小為4*3，清潔裝置的起始位置為350。清潔裝置首先沿著任務子區域301a上側的長邊清掃，直到移動至任務子區域301a的最右上角為止。接著，清潔裝置執行一次轉彎90°的動作，並再次往前清掃最長的直線距離(即兩個最小清潔單位)，直到移動至任務子區域301a的最右下角為止，以此類推。最後，當清潔裝置沿著第3A圖所示之路徑回到起點350後，完成清掃任務子區域301a。而根據上述之路徑，響應於任務子區域的短邊為奇數時，第一處理單元111根據以下的公式計算清掃一個任務子區域所需的時間：T total =2XT+XYL+RL
Figure 107137349-A0101-12-0007-1
 其中，T total 為所需的清掃時間，X為短邊的清掃單位的數量，Y為長邊的清掃單位的數量，T為清潔裝置轉彎所需的時間，以及L為清潔裝置清掃一個清掃單位所需的時間。此外，當任務子區域的長邊越長時，R約等於Y-2。
第3B圖係顯示根據本發明另一實施例所述之所示之清潔裝置清掃路徑之示意圖。相較於任務子區域301a，任務子區域301b之短邊為偶數，如此當清潔裝置欲回到起點350時，將可以平行於長邊之方向移動。舉例來說，如圖所示，為了完 成清掃任務子區域301b，清潔裝置區將清掃6*4個最小清掃單位，並執行八次轉彎動作。同樣地，根據上述之路徑，響應於任務子區域的短邊為偶數時，第一處理單元111根據以下的公式計算清掃一個任務子區域所需的時間：T total =2XT+XYL同樣地，T total 為所需的清掃時間，X為短邊的清掃單位的數量，Y為長邊的清掃單位的數量，T為清潔裝置轉彎所需的時間，以及L為清潔裝置清掃一個清掃單位所需的時間。
如表1所示，表1係顯示根據本發明一些實施例所述之完成各種大小之任務子區域所需的時間。其中，表中所示的清掃時間皆透過前述的兩個公式求得。
Figure 107137349-A0101-12-0008-2
值得注意的是，前述任務地圖之切割以及任務子區域之合併之相關運算亦可由清潔裝置120之第二處理單元 121執行。換言之，清潔裝置120可直接於控制端110下載任務地圖，並執行相關之運算。
於第一處理單元111取得基本分區結果以及對應於每個任務子區域的清掃時間後，第一處理單元111更根據每個任務子區務的清掃時間將任務子區域大致上平均地分配給多個清潔裝置，以增加執行清掃任務的效率。其中，大致上平均地分配任務子區域表示每個清潔裝置完成被分配到的任務子區域所需的時間與平均清掃時間之差異小於一既定容忍值。此外，平均清掃時間等於基本分區結果中各個任務子區域所對應之清掃時間之總和除以清潔裝置之數量。
Figure 107137349-A0101-12-0009-3
第4圖係顯示根據本發明一實施例所述之對應於一任務地圖之基本分區結果之示意圖，以及表2為第4圖中各個任務子區域所對應之尺寸以及清掃時間。
第5圖係顯示根據本發明一實施例所述之對應於兩個清潔裝置之最佳化分區之示意圖。根據表2之內容，第一處理單元111可取得所有任務子區域的清掃時間總合為 15.2+21.3+17.4+36+14.1=104(秒)，而平均清掃時間為104/2=52(秒)。接著，第一處理單元111根據平均清掃時間合併第4圖中所示之任務子區域直到兩個任務子區域所對應之清掃時間接近52秒為止。首先，根據第4圖之內容，任務子區域401以及任務子區域404兩者距離整個任務地圖之中心最遠，因此第一處理單元111首先選擇任務子區域401以及任務子區域404作為2個清潔裝置的起始區塊(其中，第5圖所示之R1以及R2即為清潔裝置之起始清掃位置)。接著，由於任務子區域401所對應之清掃時間(15.2秒)小於任務子區域404所對應之清掃時間(36秒)，而任務子區域403係與任務子區域401相鄰，因此第一處理單元111將任務子區域401以及任務子區域403合併，並取得其對應之清掃時間(即15.2+17.4=32.6(秒))。然而，由於合併的任務子區域所對應的清掃時間仍小於任務子區域404所對應之清掃時間(36秒)，因此第一處理單元111接著將合併的任務子區域與任務子區域402合併，並取得對應之清掃時間(即32.6+21.3=53.9秒)。其中，合併的任務子區域所對應之清掃時間已大於任務子區域404所對應之清掃時間(36秒)，且其與平均清掃時間(52秒)之差異小於既定容忍值(例如平均清掃時間的10%)，則第一處理單元111完成一個清掃裝置之任務區域之配置(如第5圖所示之任務區域510)。
接著，由於任務子區域404所對應之清掃時間與平均清掃時間之差異仍大於既定容忍值，且任務子區域404係與任務子區域405相鄰，因此第一處理單元111將任務子區域404與任務子區域405合併，並取得其所對應之清掃時間為50.1秒。 其中，合併的任務子區域所對應之清掃時間與平均清掃時間(52秒)之差異已小於既定容忍值，且任務地圖中已無未被合併的任務子區域，則第一處理單元111將合併的任務子區域配置為對應於另一個清掃裝置之任務區域(如第5圖所示之任務區域520)。接著，第一處理單元111進一步地根據兩個清潔裝置之位置透過第一通訊介面將兩個任務區域分配給兩個清潔裝置，使得兩個清潔裝置可根據任務區域進行清掃作業。
第6A、6B圖係顯示根據本發明另一實施例所述之對應於三個清潔裝置之最佳化分區之示意圖。響應於清潔裝置的數量為三個時，平均清掃時間為104/3=34.67(秒)。其中，由於最大的任務子區域404所對應的清掃時間(36秒)已大於平均清掃時間，故第一處理單元111首先減少任務子區域404之清掃區域。其中，於減少任務子區域的面積時，將以長邊為單位進行切割，以避免增加清潔裝置的轉彎次數。舉例來說，如第6A圖所示，任務子區域404被切割為任務子區域604(9*16)以及606(1*16)。接著，第一處理單元111選擇三個清潔裝置的起始區塊。其中，任務子區域601、任務子區域602以及任務子區域604為距離任務地圖之中心最遠的三個任務子區域，因此第一處理單元111將任務子區域601、任務子區域602以及任務子區域604設定為三個清潔裝置的起始區塊。第一處理單元111接著從三個任務子區域中選取清掃時間最短之一者作為優先合併的任務子區域(即任務子區域601)，並判斷其是否有相鄰的任務子區域。其中，由於任務子區域603與任務子區域601相鄰，因此第一處理單元111將兩者合併以作為第一合併結果， 並計算得其所對應之清掃時間為32.6秒。
接著，由於任務子區域602所對應之清掃時間(21.3秒)小於任務子區域604所對應之清掃時間(33.9秒)以及第一合併結果所對應之清掃時間(32.6秒)，因此第一處理單元111判斷任務子區域602是否有相鄰且未被合併的任務子區域。其中，由於任務子區域605與任務子區域602相鄰且任務子區域605尚未被合併，因此第一處理單元111將任務子區域605與任務子區域602合併以作為第二合併結果，並計算得其所對應的清掃時間為35.4秒。
接著，由於第一合併結果所對應之清掃時間(32.6秒)小於任務子區域604所對應之清掃時間(33.9秒)以及第二合併結果所對應之清掃時間(35.4秒)，但其已無相鄰且尚未被合併的任務子區域，因此第一處理單元111更進一步地判斷任務子區域604是否有相鄰且未被合併的任務子區域。其中，由於任務子區域606並未被合併，因此第一處理單元111將任務子區域604與任務子區域606合併以作為第三合併結果，並計算得其所對應之清掃時間為36秒。
最後，由於任務地圖中已無尚未被合併的任務子區域，因此第一處理單元111判斷第一合併結果、第二合併結果以及第三合併結果所對應之清掃時間與平均清掃時間之差異是否皆小於既定容忍值。而經過計算後，由於第一合併結果、第二合併結果以及第三合併結果所對應之清掃時間與平均清掃時間之差異皆小於既定容忍值，因此第一處理單元111將第一合併結果、第二合併結果以及第三合併結果分別設定為最後 的任務區域(即如第6B圖所示之任務區域610~630)，並根據三個清潔裝置之位置對任務區域610~630進行分配。
第7A~7C圖係顯示根據本發明另一實施例所述之對應於四個清潔裝置之最佳化分區之示意圖。響應於清潔裝置的數量為四個時，平均清掃時間為104/4=26(秒)。然而，同樣地，由於最大的任務子區域404所對應之清掃時間已大於平均清掃時間，故第一處理單元111首先減少任務子區域404之清掃區域。其中，於減少任務子區域的面積時，亦以長邊為單位進行切割(如第7A圖所示，任務子區域404被切割為任務子區域704(7*16)以及706(3*16))，以避免增加清潔裝置的轉彎次數。接著，由於任務子區域701、任務子區域702、任務子區域706以及任務子區域704距離任務地圖之中心最遠，因此第一處理單元111將上述任務子區域設定為清潔裝置之起始區塊。其中，由於任務子區域706所對應之清掃時間最短，因此第一處理單元111首先對任務子區域706執行合併之動作。由於任務子區域706與任務子區域705相鄰，因此第一處理單元111將任務子區域706與任務子區域705合併以作為第一合併結果，並計算得其所對應之清掃時間為26.4秒。
接著，由於任務子區域701所對應之清掃時間(15.2秒)小於第一合併結果所對應之清掃時間(26.4秒)、任務子區域704所對應之清掃時間(26.7秒)以及任務子區域702所對應之清掃時間(21.3秒)，因此第一處理單元111判斷任務子區域701是否有相鄰且未被合併的任務子區域。其中，由於任務子區域703與任務子區域701相鄰且尚未被合併，因此第一處理 單元將任務子區域703與任務子區域701以作為第二合併結果，並計算得其所對應之清掃時間為32.6秒。
其中，由於第二合併結果所對應之清掃時間與平均之差異遠大於既定容忍值，且任務子區域703同時與任務子區域701以及任務子區域702鄰接，因此第一處理單元將對任務子區域703進行切割，以使得第二合併結果所對應之清掃時間接近平均清掃時間。如第7B圖所示，第一處理單元111重新將任務子區域703切割為任務子區域703a、703b，並分別將任務子區域703a與任務子區域701合併以及將任務子區域703b與任務子區域702合併，以分別作為第三合併結果以及第四合併結果。其中，第三合併結果所對應之清掃時間為26.8秒以及第四合併結果所對應之清掃時間為27.1秒，其兩者與平均清掃時間之差異已皆小於既定容忍值，故在第一處理單元111將兩者設定為對應於兩個清潔裝置之任務區域。
最後，由於任務子區域704(26.7秒)與平均清掃時間之差異值原先已小於既定容忍值，且任務地圖中已無未被合併的任務子區域，因此第一處理單元111將第一合併結果、第三合併結果、第四合併結果以及任務子區域704設定為最後的任務區域(即如第7C圖所示之任務區域710~740)，並根據四個清潔裝置之位置對任務區域710~740進行分配。
值得注意的是，當對任務子區域進行切割時，已被切割過的任務子區域將不會進行第二次的切割動作。然而，當所有的任務子區域皆被切割過(即切割次數等於清潔裝置之數量)時，第一處理單元111將依照比例調高既定容忍值(例 如每次增加既定容忍值5%)。
此外，根據本發明一實施例，當計算任務子區域與任務地圖之中心之距離時，係計算指任務子區域之中心與任務地圖之中心之距離。舉例來說，如第8圖所示，任務地圖之中心850為可包含所有任務子區域之矩形之中心，而中心801~805則分別為任務子區域401~405之中心。因此，於本發明之實施例中，任務子區域401之中心801距離任務地圖之中心850為最遠的，故其為清潔裝置之起始區塊之首選。
根據本發明另一實施例，當對任務子區域進行合併時，若初始區塊具有兩個以上的相鄰任務子區域，第一處理單元111將合併距離其它任務子區域較遠的任務子區域。舉例來說，如第9圖所示，任務子區域901同時與任務子區域902以及任務子區域903相鄰，但由於任務子區域902距離其它任務子區域(例如任務子區域904)較遠，因此第一處理單元111將優先合併任務子區域901與任務子區域902。
第10圖係顯示根據本發明一實施例所述之用於清潔裝置之任務區域分配方法之流程圖。首先，於步驟S1001，第一處理單元111自第一儲存單元112存取任務地圖。於步驟S1002，第一處理單元111取得對應於任務地圖之外形。於步驟S1003，第一處理單元111根據外形之複數凹角將任務地圖分割為複數基本子區域。於步驟S1004，第一處理單元111分別合併相鄰且鄰接的兩個基本子區域，並分別取得對應於複數合併動作之複數區域合併結果。其中，兩個合併的基本子區域具有共同且長度相同的邊。於步驟S1005，第一處理單元111更計算對 應於每個合併的基本子區域所對應的清掃時間。於步驟S1006，第一處理單元111根據清掃時間重複執行合併動作直到所有相鄰且合併過的基本子區域不具有共同長度的邊為止，並取得基本分區結果。於步驟S1007，第一處理單元111加總基本分區結果中所有任務子區域所對應之清掃時間，並除以清掃裝置的數量，以取得平均清掃時間。於步驟S1008，第一處理單元111判斷每個任務子區域所對應之清掃時間是否大於平均清掃時間。響應於任務子區域之任一者所對應之清掃時間大於平均清掃時間時，進入步驟S1009，第一處理單元111將該任務子區域切割為兩個任務子區域，使其清掃時間小於並約等於平均清掃時間。於步驟S1010，第一處理單元111優先選擇被分割的任務子區域作為起始區塊之一者。
反之，響應於所有任務子區域所對應之清掃時間皆未大於平均清掃時間時，進入步驟S1011，第一處理單元111選擇距離任務地圖中心最遠的複數任務子區域作為起始區塊。其中，起始區塊之數量等於清潔裝置之數量。於步驟S1012，第一處理單元111選擇對應於清掃時間最少的起始區塊，以與其它任務子區域合併。於步驟S1013，第一處理單元111首先判斷欲與其它任務子區域合併的起始區塊是否有相鄰的任務子區域。響應於清掃時間最少的起始區塊未有相鄰的任務子區域時，進入步驟S1014，第一處理單元111選擇對應於清掃時間次少的起始區塊，並回到步驟S1013，第一處理單元111再次判斷對應於清掃時間次少的起始區塊是否有相鄰的任務子區域。
反之，響應於清掃時間最少的起始區塊具有相鄰 的任務子區域時，進入步驟S1015，第一處理單元111將起始區塊與相鄰的任務子區域合併，並再次選擇清掃時間最少的起始區塊，以重複地執行合併的動作，直到沒有未被合併的任務子區域為止。於步驟S1016，第一處理單元111判斷合併的任務子區域所對應的清掃時間與平均清掃時間之差異是否大於既定容忍值。響應於合併的任務子區域所對應的清掃時間大於既定容忍值，則進入步驟S1017，第一處理單元111將大於既定容忍值的任務子區域的一部份切給相鄰的任務子區域，以使得兩者所對應的清掃時間接近平均值。然而，第一處理單元111更判斷切割次數是否大於清潔裝置的數量(步驟S1018)。響應於切割次數大於清潔裝置的數量時(即每個合併的任務子區域皆被切割過)，進入步驟S1019，第一處理單元111增加既定容忍值，並回到步驟S1016，第一處理單元111重新判斷每個合併的任務子區域所對應之清掃時間與平均清掃時間之差異是否大於既定容忍值。響應於所有任務子區域或者合併的任務子區域所對應之清掃時間與平均清掃時間之差異皆小於既定容忍值時，進入步驟S1020，第一處理單元111完成清掃裝置的任務子區域的分配。最後，進入步驟S1021，第一處理單元111根據清掃裝置的當前位置選擇對應的任務區域。
值得注意的是，於上述示例性裝置中，儘管上述方法已在使用一系列步驟或方框之流程圖的基礎上描述，但本發明不侷限於這些步驟的順序，並且一些步驟可不同於其餘步驟的順序執行或其餘步驟可同時進行。此外，本領域的技術人士將理解在流程圖中所示的步驟並非唯一的，其可包括流程圖 的其他步驟，或者一或多個步驟可被刪除而不會影響本發明的範圍。
本發明之方法，或特定型態或其部份，可以以程式碼的型態存在。程式碼可以包含於實體媒體，如軟碟、光碟片、硬碟、或是任何其他機器可讀取(如電腦可讀取)儲存媒體，亦或不限於外在形式之電腦程式產品，其中，當程式碼被機器，如電腦載入且執行時，此機器變成用以參與本發明之裝置。程式碼也可透過一些傳送媒體，如電線或電纜線、光纖、或是任何傳輸型態進行傳送，其中，當程式碼被機器，如電腦接收、載入且執行時，此機器變成用以參與本發明之裝置。當在一般用途處理單元實作時，程式碼結合處理單元提供一操作類似於應用特定邏輯電路之獨特裝置。
綜上所述，當清潔裝置接收到形狀不一致的任務地圖時，透過本發明所述之清潔裝置之任務分配方法，將可有效率地將任務地圖切割為複數任務子區域，以有效率地提升清掃的速度。此外，透過更進一步地對任務子區域進行切割以及合併，以平均每個任務子區域所對應之清掃時間，將可在具有多個清潔裝置之情況下，把清掃效率提升至最大。
以上敘述許多實施例的特徵，使所屬技術領域中具有通常知識者能夠清楚理解本說明書的形態。所屬技術領域中具有通常知識者能夠理解其可利用本發明揭示內容為基礎以設計或更動其他製程及結構而完成相同於上述實施例的目的及/或達到相同於上述實施例的優點。所屬技術領域中具有通常知識者亦能夠理解不脫離本發明之精神和範圍的等效構 造可在不脫離本發明之精神和範圍內作任意之更動、替代與潤飾。
S1001~S1021‧‧‧步驟流程

Claims (10)

  1. 一種用於多個清潔裝置之任務區域分配方法，包括：取得一任務地圖；取得對應於上述任務地圖之一外形；根據上述外形之複數凹角將上述任務地圖分割為複數基本子區域；合併每兩個相鄰的基本子區域，並計算對應於每個合併的基本子區域所對應之一基本清掃時間，其中上述每兩個相鄰的基本子區域具有共同且長度相同的邊；根據上述基本清掃時間之長短重複合併每兩個相鄰的上述基本子區域直到所有相鄰的上述基本子區域不具有共同且長度相同的邊為止，並取得一基本分區結果，其中上述基本分區結果包括複數任務子區域；根據上述基本分區結果中上述任務子區域之位置選擇複數起始區塊，其中上述起始區塊的數量等於複數清潔裝置之數量，且上述起始區塊的選擇，是選擇上述任務子區域中距離上述任務地圖之中心最遠者；根據每個上述起始區塊之一位置、每個上述任務子區域之一位置以及對應於每個上述任務子區域之一清掃時間合併上述任務子區域，直到剩餘的上述任務子區域的數量等於上述清潔裝置之數量為止，並取得一任務區域分配結果；根據上述清潔裝置之位置以及上述任務分配結果致使 每個上述清潔裝置執行一清掃任務。
  2. 如申請專利範圍第1項所述之任務區域分配方法，其中計算對應於上述基本子區域以及上述任務子區域之步驟更包括：根據上述基本子區域以及上述任務子區域之上述短邊的清掃單位的數量以一第一公式或者一第二公式取得上述清掃時間；其中，當上述短邊的清掃單位的數量為奇數時，透過上述第一公式計算上述清掃時間，上述第一公式表示為：
    Figure 107137349-A0305-02-0024-1
     其中，當上述短邊的清掃單位的數量為偶數時，透過上述第二公式計算上述清掃時間，上述第二公式表示為：T total =2XT+XYL其中，T total 為上述清掃時間，X為上述短邊的上述清掃單位的數量，Y為上述長邊的上述清掃單位的數量，T為上述清潔裝置轉彎所需的時間，以及L為上述清潔裝置清掃一個上述清掃單位所需的時間。
  3. 如申請專利範圍第1項所述之任務區域分配方法，步驟更包括：根據每個上述任務子區域所對應之上述清掃時間以及上述清潔裝置之數量取得一平均清掃時間；根據上述起始區塊所對應之上述清掃時間之長短順序合併相鄰之上述任務子區域直到合併的任務子區域所對應之清掃時間與上述平均清掃時間之差異小於一既定容忍值 為止，並取得上述任務區域分配結果。
  4. 如申請專利範圍第3項所述之任務區域分配方法，更包括：判斷上述任務子區域所對應之上述清掃時間是否大於上述平均清掃時間；響應於上述任務子區域所對應之上述清掃時間大於上述平均清掃時間時，沿著上述長邊切割上述任務子區域。
  5. 如申請專利範圍第4項所述之任務區域分配方法，更包括：響應於上述任務子區域無相鄰且未被合併的上述任務子區域時，切割合併的任務子區域；以及響應於所有上述合併的任務子區域皆被切割過、且上述合併的任務子區域之任一者與上述平均清掃時間之差異仍大於上述既定容忍值時，提高上述既定容忍值。
  6. 一種清潔裝置任務分配系統，包括：一控制端，包括：一第一儲存單元，儲存一任務地圖；一第一處理單元，用以：自上述第一儲存單元取得上述任務地圖；取得對應於上述任務地圖之一外形；根據上述外形之複數凹角將上述任務地圖分割為複數基本子區域；合併每兩個相鄰的基本子區域，並計算對應於每個合併動作之一基本清掃時間，其中上述每兩個相鄰 的基本子區域具有共同且長度相同的邊；根據上述基本清掃時間之長短重複合併每兩個相鄰的上述基本子區域直到所有相鄰的上述基本子區域不具有共同且長度相同的邊為止，並取得一基本分區結果，其中上述基本分區結果包括複數任務子區域；根據上述基本分區結果中上述任務子區域之位置選擇複數起始區塊，其中上述起始區塊的數量等於複數清潔裝置之數量，且上述起始區塊的選擇，是選擇上述任務子區域中距離上述任務地圖之中心最遠者；根據每個上述起始區塊之一位置、每個上述任務子區域之一位置以及對應於每個上述任務子區域之一清掃時間合併上述任務子區域，直到剩餘的上述任務子區域的數量等於上述清潔裝置之數量為止，並取得一任務區域分配結果；以及根據上述清潔裝置之位置以及上述任務分配結果分配一清掃任務給每個上述清潔裝置；以及複數上述清潔裝置，其中每個上述清潔裝置包括：一第二儲存單元，儲存上述任務區域分配結果；以及一第二處理單元，根據上述任務區域分配結果執行上述清掃任務。
  7. 如申請專利範圍第6項所述之清潔裝置任務分配系統，其中上述第一處理單元更根據上述基本子區域以及上 述任務子區域之上述短邊的清掃單位的數量以一第一公式或者一第二公式取得上述清掃時間；其中，當上述短邊的清掃單位的數量為奇數時，透過上述第一公式計算上述清掃時間，上述第一公式表示為：
    Figure 107137349-A0305-02-0027-2
     其中，當上述短邊的清掃單位的數量為偶數時，透過上述第二公式計算上述清掃時間，上述第二公式表示為：T total =2XT+XYL其中，T total 為上述清掃時間，X為上述短邊的上述清掃單位的數量，Y為上述長邊的上述清掃單位的數量，T為上述清潔裝置轉彎所需的時間，以及L為上述清潔裝置清掃一個上述清掃單位所需的時間。
  8. 如申請專利範圍第6項所述之清潔裝置任務分配系統，其中上述第一處理單元更用以：根據每個上述任務子區域所對應之上述清掃時間以及上述清潔裝置之數量取得一平均清掃時間；根據上述起始區塊所對應之上述清掃時間之長短順序合併相鄰之上述任務子區域直到合併的任務子區域所對應之清掃時間與上述平均清掃時間之差異小於一既定容忍值為止，並取得上述任務區域分配結果。
  9. 如申請專利範圍第8項所述之清潔裝置任務分配系統，其中上述第一處理單元更用以：判斷上述任務子區域所對應之上述清掃時間是否大於上述平均清掃時間； 響應於上述任務子區域所對應之上述清掃時間大於上述平均清掃時間時，沿著上述長邊切割上述任務子區域。
  10. 如申請專利範圍第9項所述之清潔裝置任務分配系統，其中上述第一處理單元更用以：響應於上述任務子區域無相鄰且未被合併的上述任務子區域時，切割合併的任務子區域；以及響應於所有上述合併的任務子區域皆被切割過、且上述合併的任務子區域之任一者與上述平均清掃時間之差異仍大於上述既定容忍值時，提高上述既定容忍值。
TW107137349A 2018-10-23 2018-10-23 用於多個清潔裝置之任務區域分配方法以及其系統 TWI687191B (zh)

Priority Applications (3)

Application Number Priority Date Filing Date Title
TW107137349A TWI687191B (zh) 2018-10-23 2018-10-23 用於多個清潔裝置之任務區域分配方法以及其系統
CN201811275903.5A CN111178646B (zh) 2018-10-23 2018-10-30 用于多个清洁装置的任务区域分配方法以及其系统
US16/410,193 US10824166B2 (en) 2018-10-23 2019-05-13 Methods and systems of distributing task regions for a plurality of cleaning devices

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
TW107137349A TWI687191B (zh) 2018-10-23 2018-10-23 用於多個清潔裝置之任務區域分配方法以及其系統

Publications (2)

Publication Number Publication Date
TWI687191B true TWI687191B (zh) 2020-03-11
TW202015606A TW202015606A (zh) 2020-05-01

Family

ID=70280777

Family Applications (1)

Application Number Title Priority Date Filing Date
TW107137349A TWI687191B (zh) 2018-10-23 2018-10-23 用於多個清潔裝置之任務區域分配方法以及其系統

Country Status (3)

Country Link
US (1) US10824166B2 (zh)
CN (1) CN111178646B (zh)
TW (1) TWI687191B (zh)

Families Citing this family (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
TWI660275B (zh) * 2018-06-27 2019-05-21 廣達電腦股份有限公司 用於清潔裝置之任務區域分配方法、清潔裝置任務分配系統以及清潔裝置
TWI687191B (zh) * 2018-10-23 2020-03-11 廣達電腦股份有限公司 用於多個清潔裝置之任務區域分配方法以及其系統
CN111563461B (zh) * 2020-05-11 2021-03-12 追创科技(苏州)有限公司 清洁设备的清洁路径获取方法、装置及存储介质
CN111861591B (zh) * 2020-09-24 2020-12-15 武汉木仓科技股份有限公司 一种信息投递的方法及装置
CN115200581A (zh) * 2021-04-09 2022-10-18 美智纵横科技有限责任公司 路径规划方法、装置、清洁机器人及存储介质
CN113219995A (zh) * 2021-06-04 2021-08-06 深圳飞鼠动力科技有限公司 一种路径规划方法及清洁机器人
CN113808023A (zh) * 2021-09-23 2021-12-17 安克创新科技股份有限公司 一种地图数据存储方法、装置、清洁机器人及存储介质
CN115530699B (zh) * 2022-10-09 2023-09-26 深圳市普森斯科技有限公司 洗地机清扫控制方法、装置、计算机设备及存储介质

Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
TW201805748A (zh) * 2016-08-12 2018-02-16 聯潤科技股份有限公司 邊界訊號發射裝置及其制約自走式清潔裝置之方法及依該方法制約之自走式清潔裝置
TW201815343A (zh) * 2016-10-25 2018-05-01 南韓商Ｌｇ電子股份有限公司 清掃機器人及其控制方法
CN108664015A (zh) * 2017-03-29 2018-10-16 北京米文动力科技有限公司 一种机器人行走路径的规划方法和设备
CN108693882A (zh) * 2018-06-05 2018-10-23 北京智行者科技有限公司 一种多模清扫路径生成方法

Family Cites Families (28)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5247608A (en) * 1991-04-01 1993-09-21 At&T Bell Laboratories Method and apparatus for achieving dynamic path control of multiple robots
CN1183427C (zh) * 1997-11-27 2005-01-05 阳光及自动化公司 移动机器人及其控制系统的改进
US6690134B1 (en) * 2001-01-24 2004-02-10 Irobot Corporation Method and system for robot localization and confinement
US7429843B2 (en) * 2001-06-12 2008-09-30 Irobot Corporation Method and system for multi-mode coverage for an autonomous robot
JP2004275468A (ja) * 2003-03-17 2004-10-07 Hitachi Home & Life Solutions Inc 自走式掃除機およびその運転方法
DE102004027944B4 (de) * 2004-06-08 2012-02-16 Kuka Laboratories Gmbh Verfahren zum Schützen eines Roboters gegen Kollisionen
US7389156B2 (en) * 2005-02-18 2008-06-17 Irobot Corporation Autonomous surface cleaning robot for wet and dry cleaning
US9144904B2 (en) * 2008-05-21 2015-09-29 Fanuc Robotics America Corporation Method and system for automatically preventing deadlock in multi-robot systems
KR101686170B1 (ko) * 2010-02-05 2016-12-13 삼성전자주식회사 주행 경로 계획 장치 및 방법
KR20110119118A (ko) * 2010-04-26 2011-11-02 엘지전자 주식회사 로봇 청소기, 및 이를 이용한 원격 감시 시스템
US8639364B2 (en) * 2011-07-13 2014-01-28 KUKA Robotics Corporation Uniform synchronizing robot control and deadlock detection in uniform synchronization
JP5768829B2 (ja) * 2013-03-15 2015-08-26 株式会社安川電機 ロボットシステム、ロボット制御方法及び被加工物の製造方法
KR101883473B1 (ko) * 2013-05-07 2018-07-30 한화지상방산 주식회사 이동로봇의 지도 작성 장치 및 방법
CN104161487B (zh) * 2013-05-17 2018-09-04 恩斯迈电子(深圳)有限公司 移动装置
US9037396B2 (en) * 2013-05-23 2015-05-19 Irobot Corporation Simultaneous localization and mapping for a mobile robot
CH709347A2 (de) * 2014-03-10 2015-09-15 Tecan Trading Ag Verfahren zur Wegfindung in einem automatisierten Handhabungssystem sowie Handhabungssystem mit entsprechendem Kontrollmodul zur Wegfindung.
US9555545B2 (en) * 2014-05-21 2017-01-31 Bot & Dolly, Llc Systems and methods for time-based parallel robotic operation
US10660496B2 (en) * 2014-09-24 2020-05-26 Samsung Electronics Co., Ltd. Cleaning robot and method of controlling the cleaning robot
US10488865B2 (en) * 2014-12-16 2019-11-26 Al Incorporated Methods and systems for robotic surface coverage
TWI557421B (zh) * 2015-04-21 2016-11-11 金寶電子工業股份有限公司 定位輔助方法及其電子移動裝置
US9707681B2 (en) * 2015-07-27 2017-07-18 Siemens Industry Software Ltd. Anti-collision management of overlapping robotic movements
US20190176321A1 (en) * 2015-09-30 2019-06-13 AI Incorporated Robotic floor-cleaning system manager
CN105739504B (zh) * 2016-04-13 2019-02-01 上海物景智能科技有限公司 一种机器人工作区域的排序方法及排序系统
US10168709B2 (en) * 2016-09-14 2019-01-01 Irobot Corporation Systems and methods for configurable operation of a robot based on area classification
CN106564054B (zh) * 2016-10-20 2018-12-04 上海物景智能科技有限公司 一种机器人作业区域的动态分割方法及系统
JP6640777B2 (ja) * 2017-03-17 2020-02-05 株式会社東芝 移動制御システム、移動制御装置及びプログラム
CN107316308A (zh) * 2017-06-27 2017-11-03 苏州大学 一种基于改进的多路谱聚类算法的清洁机器人地图分割方法
TWI687191B (zh) * 2018-10-23 2020-03-11 廣達電腦股份有限公司 用於多個清潔裝置之任務區域分配方法以及其系統

Patent Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
TW201805748A (zh) * 2016-08-12 2018-02-16 聯潤科技股份有限公司 邊界訊號發射裝置及其制約自走式清潔裝置之方法及依該方法制約之自走式清潔裝置
TW201815343A (zh) * 2016-10-25 2018-05-01 南韓商Ｌｇ電子股份有限公司 清掃機器人及其控制方法
TWI660702B (zh) * 2016-10-25 2019-06-01 南韓商Ｌｇ電子股份有限公司 清掃機器人及其控制方法
CN108664015A (zh) * 2017-03-29 2018-10-16 北京米文动力科技有限公司 一种机器人行走路径的规划方法和设备
CN108693882A (zh) * 2018-06-05 2018-10-23 北京智行者科技有限公司 一种多模清扫路径生成方法

Also Published As

Publication number Publication date
US20200125115A1 (en) 2020-04-23
TW202015606A (zh) 2020-05-01
CN111178646A (zh) 2020-05-19
US10824166B2 (en) 2020-11-03
CN111178646B (zh) 2023-04-07

Similar Documents

Publication Publication Date Title
TWI687191B (zh) 用於多個清潔裝置之任務區域分配方法以及其系統
TWI660275B (zh) 用於清潔裝置之任務區域分配方法、清潔裝置任務分配系統以及清潔裝置
Deveci et al. Exploiting geometric partitioning in task mapping for parallel computers
JP4781089B2 (ja) タスク割り当て方法およびタスク割り当て装置
CN103797462A (zh) 一种创建虚拟机的方法和装置
JP6200824B2 (ja) 演算制御装置及び演算制御方法並びにプログラム、ＯｐｅｎＣＬデバイス
JP2008310700A5 (zh)
JP2008516346A (ja) 超並列型スーパーコンピュータでのアプリケーション・レイアウトの最適化
US20160301754A1 (en) Distributed file system using torus network and method for configuring and operating distributed file system using torus network
Ng et al. Defragmentation for efficient runtime resource management in NoC-based many-core systems
KR20160121380A (ko) 토러스 네트워크를 이용하는 분산 파일 시스템 및 토러스 네트워크를 이용하는 분산 파일 시스템의 구성 및 운영 방법
JP6374777B2 (ja) データ処理方法、プログラム及びデータ処理装置
US11665776B2 (en) System and method for synthesis of a network-on-chip for deadlock-free transformation
JP6666553B2 (ja) 情報処理装置、ジョブ管理方法およびジョブ管理プログラム
Albing et al. Scalable node allocation for improved performance in regular and anisotropic 3d torus supercomputers
JP6683046B2 (ja) 並列処理装置、ジョブ管理方法、およびジョブ管理プログラム
CN112257376B (zh) 馈通路径的规划方法及装置、电子设备、存储介质
JP3954253B2 (ja) Ｌｓｉフロアプラン決定装置及び方法並びにプログラム記録媒体
JP2022083886A (ja) 作業経路決定装置
US8595734B2 (en) Reduction of processing time when cache miss occurs
CN113391919A (zh) 一种基于二维胖树网络的计算结点分配方法及装置
JP2016004310A (ja) 並列計算機システム、制御方法およびジョブ管理プログラム
US20150127700A1 (en) Parallel computer system, control unit, and method of controlling parallel computer system
Leung et al. Task Mapping for Non-contiguous Allocations.
KEE Design and performance evaluation of migration-based submesh allocation strategies in mesh multicomputers