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