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