掃地機器人的路徑優(yōu)化解決方案
來源：日期：2015-05-27 16:36:11點擊：5480次
問題背景
隨著科學技術的不斷發(fā)展，掃地機逐步走入平常百姓家，并被越來越多的人所接受，掃地機（也稱掃地機器人）將在不久的將來像白色家電一樣成為每個家庭必不可少的清潔幫手。產(chǎn)品也會由現(xiàn)在的初級智能向著更高程度的智能化程度發(fā)展，逐步取代人工清潔。
智能掃地機器人是通過電動機的高速旋轉，在主機內(nèi)形成真空，利用由此產(chǎn)生的高速氣流，從吸入口吸進垃圾。掃地機一般為半徑0.2米圓盤，、運行速度一般在每秒0.25米左右，只走直線，且碰到墻壁等障礙才可轉彎。與傳統(tǒng)的掃地機不同，智能掃地機可以通過微處理器進行現(xiàn)場環(huán)境分析，自動選擇運行路線。遇到障礙發(fā)生碰撞后將重新隨機地選擇路線，逐步進行清掃。智能掃地機具有記憶、存儲功能。利用傳感器掃描現(xiàn)場環(huán)境，設計運行路徑并存儲。一般不能100%的清掃指定區(qū)域（如墻角部分）。清掃后的垃圾裝進機子尾部的集塵盒，再通過人工清倒垃圾。機器在工作電壓不足時會自動回到充電站充電。
目標任務
考慮圖1的工作現(xiàn)場，其中點A（1,5）為掃地機充電站，區(qū)域的垃圾指標見附件1.不考慮再充電情況，有以下問題：
問題一：有些低檔的掃地機因為價格低廉，智能程度不高。其工作時的
路徑選擇方案是將現(xiàn)場分成若干區(qū)域（例如上下左右4個區(qū)域），并通過傳感器間隔一段時間掃描現(xiàn)場一次，選則垃圾最多區(qū)域清掃。假設每次掃過的區(qū)域垃圾指標值減少1。針對附件1，估計清掃完給定區(qū)域大致需要的時間（盡量保證每個點的垃圾指標不超過1）。
問題二：智能程度高的掃地機每次可以選擇清掃垃圾指標值最大的地方清掃，每次掃過的區(qū)域垃圾指標值減少1。該機器人需多長時間才能保證清掃完該區(qū)域（區(qū)域內(nèi)指標值不超過1）。比較問題1與問題2，說明問題1中方案的合理性。
問題三：其他條件同2，如何設計掃地機的路徑，保證掃地機以最短時間清掃完該區(qū)域。
點擊下載隨著科學技術的不斷發(fā)展，掃地機逐步走入平常百姓家，并被越來越多的人所接受，掃地機（也稱掃地機器人）將在不久的將來像白色家電一樣成為每個家庭必不可少的清潔幫手。產(chǎn)品也會由現(xiàn)在的初級智能向著更高程度的智能化程度發(fā)展，逐步取代人工清潔。
智能掃地機器人是通過電動機的高速旋轉，在主機內(nèi)形成真空，利用由此產(chǎn)生的高速氣流，從吸入口吸進垃圾。掃地機一般為半徑0.2米圓盤，、運行速度一般在每秒0.25米左右，只走直線，且碰到墻壁等障礙才可轉彎。與傳統(tǒng)的掃地機不同，智能掃地機可以通過微處理器進行現(xiàn)場環(huán)境分析，自動選擇運行路線。遇到障礙發(fā)生碰撞后將重新隨機地選擇路線，逐步進行清掃。智能掃地機具有記憶、存儲功能。利用傳感器掃描現(xiàn)場環(huán)境，設計運行路徑并存儲。一般不能100%的清掃指定區(qū)域（如墻角部分）。清掃后的垃圾裝進機子尾部的集塵盒，再通過人工清倒垃圾。機器在工作電壓不足時會自動回到充電站充電。
目標任務
考慮圖1的工作現(xiàn)場，其中點A（1,5）為掃地機充電站，區(qū)域的垃圾指標見附件1.不考慮再充電情況，有以下問題：
問題一：有些低檔的掃地機因為價格低廉，智能程度不高。其工作時的
路徑選擇方案是將現(xiàn)場分成若干區(qū)域（例如上下左右4個區(qū)域），并通過傳感器間隔一段時間掃描現(xiàn)場一次，選則垃圾最多區(qū)域清掃。假設每次掃過的區(qū)域垃圾指標值減少1。針對附件1，估計清掃完給定區(qū)域大致需要的時間（盡量保證每個點的垃圾指標不超過1）。
問題二：智能程度高的掃地機每次可以選擇清掃垃圾指標值最大的地方清掃，每次掃過的區(qū)域垃圾指標值減少1。該機器人需多長時間才能保證清掃完該區(qū)域（區(qū)域內(nèi)指標值不超過1）。比較問題1與問題2，說明問題1中方案的合理性。
問題三：其他條件同2，如何設計掃地機的路徑，保證掃地機以最短時間清掃完該區(qū)域。
