掃地機(jī)器人的路徑策略

《掃地機(jī)器人的路徑策略》由會(huì)員分享，可在線閱讀，更多相關(guān)《掃地機(jī)器人的路徑策略（40頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、 數(shù)學(xué)建模小組作業(yè) 第10組組員： +++ ——掃地機(jī)器人的路徑優(yōu)化 二〇一四年七月二十三日 38 掃地機(jī)器人的路徑策略 【摘要】 我們將掃地機(jī)在房間內(nèi)掃垃圾的路徑策略問(wèn)題抽象為方格化模型，用原始給定數(shù)據(jù)做出垃圾指標(biāo)矩陣Q[300*251],根據(jù)掃地機(jī)需要的行走路徑進(jìn)行程序嵌套，并用線性規(guī)劃的方法來(lái)進(jìn)行最優(yōu)解的求取，然后根據(jù)建立的模型，用Mat

2、lab進(jìn)行仿真演示。最終可以觀察到掃地機(jī)在每種情況下的清掃路徑。由于墻角也會(huì)存在垃圾，因此一般情況下我們不能實(shí)現(xiàn)100%的清掃，所以我們?cè)诖艘?guī)定清掃完95%的區(qū)域即作為合格的條件。下面我們根據(jù)題目要求進(jìn)行如下考慮： 問(wèn)題一 經(jīng)過(guò)分析我們可以將整個(gè)清掃區(qū)域劃分成如圖4.1.1所示的小區(qū)域，通過(guò)運(yùn)用矩陣整合函數(shù)，將矩陣Q[300*251]整合成一維數(shù)組T[5]，經(jīng)過(guò)固定時(shí)間間隔的掃描判斷{T（1），T(2),T(3),T(4),T(5)}MAX所對(duì)應(yīng)的區(qū)域，在區(qū)域邊沿隨機(jī)選取坐標(biāo)作為運(yùn)行起始點(diǎn)，如果檢測(cè)到的最大的元素的所在區(qū)域發(fā)生了變化，則根據(jù)當(dāng)前位置與隨機(jī)選好的碰撞點(diǎn)進(jìn)行路徑轉(zhuǎn)移，按照這種方

3、式運(yùn)行，直到達(dá)到掃地機(jī)的結(jié)束條件停止。 問(wèn)題二 這時(shí)掃地機(jī)每次只選擇垃圾總指標(biāo)最多的路徑，并且每次掃描發(fā)生在掃地機(jī)與墻壁發(fā)生碰撞的時(shí)。掃描過(guò)后，機(jī)器人可以任意選擇方向，選擇方向的合適程度將成為掃地機(jī)掃地效率的關(guān)鍵，所以我們?cè)O(shè)定某一點(diǎn)作為掃地機(jī)掃描的起點(diǎn)每次碰撞時(shí)的掃描決定下一時(shí)刻可能的轉(zhuǎn)彎方向，即某個(gè)方向上的垃圾總指標(biāo)Ck最大的即為下一時(shí)刻的轉(zhuǎn)彎方向。 問(wèn)題三 設(shè)計(jì)智能掃地機(jī)路徑，保證掃地機(jī)以最短時(shí)間達(dá)到清掃要求，我們可以選取以下兩種優(yōu)化方向：（1）避免與墻壁進(jìn)行碰撞，提高機(jī)器的靈活性；（2）提高單位長(zhǎng)度上清掃垃圾指標(biāo)總量，即提高清掃效率。 比較問(wèn)題1與問(wèn)題2 問(wèn)題1中的方案存在其

4、合理性，問(wèn)題2中則顯得較為高效，比較兩者發(fā)現(xiàn)：改變ST大小可以改變地段掃地機(jī)性能。 關(guān)鍵詞： 線性規(guī)劃 路徑轉(zhuǎn)移 劃分區(qū)域 清掃效率 目 錄 1、 問(wèn)題重述………………………………………………………………… 3 2、 模型假設(shè)………………………………………………………………… 4 3、 符號(hào)說(shuō)明………………………………………………………………… 4 4、 模型建立與求解………………………………………………………… 4 4.0 問(wèn)題分析…………………………………………………………… 4 4.0.1 基本模型…………………………………………………………5 4

5、.1 問(wèn)題一：低端掃地機(jī)的工作路徑………………………………… 6 4.1.1 模型:分區(qū)掃描模型…………………………………………… 6 4.2 問(wèn)題二：智能掃地機(jī)的工作路徑………………………………… 10 4.2.1模型：實(shí)時(shí)掃描模型……………………………………………11 4.3 問(wèn)題三：掃地機(jī)的優(yōu)化路徑……………………………………… 13 4.3.1 模型：實(shí)時(shí)掃描折線模型…………………………………… 13 4.4 模型I與模型II的比較…………………………………………… 17 5、 模型的檢驗(yàn)………………………………………………………………18 6、 模型的評(píng)

6、價(jià)………………………………………………………………18 參考文獻(xiàn)………………………………………………………………………20 附錄……………………………………………………………………………21 1、 問(wèn)題重述 1.1問(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米圓盤，、運(yùn)行速度一

7、般在每秒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)回到充電站充電。 1.2目標(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à)格低廉，智能程度不高。其

8、工作時(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ū)域。 2、 模型的假設(shè) 1、 假設(shè)

9、掃地機(jī)有充足的電量行駛完全部的軌跡，并且不會(huì)發(fā)生任何障礙； 2、 假設(shè)路面平坦，不會(huì)產(chǎn)生較大程度的偏移或者是翻轉(zhuǎn)； 3、 假設(shè)高端的和低端的掃地機(jī)有鮮明的特點(diǎn)，并嚴(yán)格按自己的特點(diǎn)運(yùn)行； 4、 假設(shè)掃地機(jī)掃過(guò)單元格一半及以上的面積時(shí)，單元格內(nèi)的垃圾指標(biāo)減少1； 5、 假設(shè)題目中給的點(diǎn)A始終為掃地機(jī)工作的起點(diǎn)； 6、 假設(shè)由于種種環(huán)境因素不會(huì)對(duì)掃地機(jī)速率產(chǎn)生比較大的影響； 7、 假設(shè)掃地機(jī)工作時(shí)沒(méi)有人為的影響改變掃地機(jī)的軌跡； 8、 假設(shè)當(dāng)每個(gè)點(diǎn)的垃圾指標(biāo)不超過(guò)1時(shí)掃地機(jī)的清掃任務(wù)結(jié)束； 9、 假設(shè)掃地機(jī)在掃描的過(guò)程中沒(méi)有額外的占用移動(dòng)時(shí)間，即掃描時(shí)間不會(huì)影響最終的運(yùn)動(dòng)時(shí)間。 3

10、、 符號(hào)說(shuō)明 Y(251，100) 初始垃圾指標(biāo)矩陣 J(251，300) 程序中的垃圾指標(biāo)矩陣 （a,b） 發(fā)生碰撞時(shí)刻參考點(diǎn)坐標(biāo) （A,B） 下一次發(fā)生碰撞時(shí)刻參考點(diǎn)坐標(biāo) ST 間隔掃描行駛路程 S 從（a，b）到（A,B）掃地機(jī)行駛的路程 T(n) 從充電點(diǎn)到第n個(gè)碰壁點(diǎn)掃地機(jī)行駛的時(shí)間 CK 經(jīng)過(guò)路徑的垃圾總指標(biāo) PK

11、 經(jīng)過(guò)路徑的垃圾指標(biāo)分布律 4、 模型的建立與求解 4.0問(wèn)題分析 由問(wèn)題重述可知，智能的掃地機(jī)（不管是低檔還是高檔）都會(huì)按0.4米的寬度以0.25米每秒進(jìn)行直線運(yùn)行，并且路徑上都選擇與墻壁碰撞后掃描計(jì)算出的垃圾指標(biāo)最高點(diǎn)行駛，這是所有問(wèn)題的共同點(diǎn)。 4.0.1基本模型 （1） 清掃區(qū)域直觀圖 首先我們建立一個(gè)300*251的矩陣Q，并將各個(gè)單元里的垃圾指標(biāo)賦入與二位矩陣組合形成一個(gè)三維數(shù)組。如圖4.0.1所示為將題目中給定的附錄1導(dǎo)入矩陣Q后的垃圾指標(biāo)空間分布圖。 （2） 清掃區(qū)域方格化 由于掃地機(jī)只走直線，碰到墻壁后才會(huì)轉(zhuǎn)彎，所以，掃地機(jī)

12、與墻壁碰撞之后會(huì)有180o的方向選擇。每個(gè)指向都對(duì)應(yīng)著一個(gè)所在方向的垃圾總指標(biāo)CK，其中k每個(gè)方向的路線標(biāo)志。 （3） 路徑的線性規(guī)劃 掃地機(jī)從碰撞點(diǎn)到下一個(gè)碰撞點(diǎn)所掃過(guò)的路程如圖4.0.2所示。我們將區(qū)域分割成300*251的矩陣，每個(gè)單元存儲(chǔ)著垃圾指標(biāo)值。通過(guò)判斷點(diǎn)坐標(biāo)是否在路徑中來(lái)判斷單元垃圾指標(biāo)值是否減1. 圖4.0.1 垃圾指標(biāo)分布圖 圖4.0.2 線性規(guī)劃推導(dǎo)條件 根據(jù)圖示，可以得到以下約束條件： 且 4.1問(wèn)題一：低端掃地機(jī)的運(yùn)行路徑 對(duì)于問(wèn)題一，低端掃地機(jī)需要對(duì)區(qū)域進(jìn)行分區(qū)且不能時(shí)刻掃描計(jì)算垃圾指標(biāo)值，

13、總是經(jīng)過(guò)一段規(guī)定的時(shí)間后，才會(huì)重新規(guī)劃路線，沒(méi)有進(jìn)行下次掃描，則在當(dāng)前判斷垃圾指數(shù)最高的區(qū)域隨機(jī)清掃，我們需要將區(qū)域分成幾個(gè)小的區(qū)域，低端掃地機(jī)在掃描后達(dá)到垃圾總指標(biāo)最高的區(qū)域清掃，清掃隨機(jī)選取。 4.1.1模型：分區(qū)掃描模型 （1） 區(qū)域的劃分 通過(guò)分析問(wèn)題一的工作特點(diǎn)，我們得到了一個(gè)相對(duì)比較合理的分割方式，如圖4.1.1所示，我們進(jìn)行的是五等分的條形分割，這樣的分割方式可以保證掃地機(jī)在掃垃圾指標(biāo)值最大的分區(qū)過(guò)程中，路徑不覆蓋其他分區(qū)。 圖4.1.1 分區(qū)分析示意圖 （2） 間隔掃描時(shí)間的確定 在這里我們不妨把間隔掃描時(shí)間抽象為間隔掃描行駛路程考慮。設(shè)定參數(shù)——間隔掃描行駛

14、路程ST ，并給ST 賦初值（12.5m）。舉個(gè)例子，假設(shè)發(fā)生碰撞時(shí)刻參考點(diǎn)坐標(biāo)為(a,b)，掃地機(jī)下一次與墻壁發(fā)生碰撞時(shí)刻參考點(diǎn)的坐標(biāo)為(A,B)，則從(a,b)到(A,B)掃地機(jī)行駛的路程S 有如下公式： （勾股定理） 故充電點(diǎn)到第n個(gè)碰壁點(diǎn)掃地機(jī)行駛的時(shí)間T(n) （3） 模型的建立 在掃地機(jī)的行駛過(guò)程中，根據(jù)假設(shè)4的條件；根據(jù)區(qū)域所在的位置枚舉出參考點(diǎn)可以到達(dá)的點(diǎn)（單元）。在這些點(diǎn)中隨機(jī)選取一個(gè)作為下一次與墻壁的碰撞點(diǎn)。將這點(diǎn)與參考點(diǎn)相連，即為下一步可能的清掃路徑。為了提高清掃的效率，我們選擇清掃垃圾總數(shù)量最多的路徑。在這里我們引入一個(gè)參數(shù)C，稱為經(jīng)過(guò)路徑的垃

15、圾總指標(biāo)值。根據(jù)我們所建立的模型可以列出公式： （其中為直線路徑所經(jīng)過(guò)單元的垃圾指標(biāo)值；N為經(jīng)過(guò)區(qū)域的單位總數(shù)） 通過(guò)計(jì)算每條路徑的C 值的大小，判斷出最大的C 值所在路徑的終點(diǎn)，進(jìn)而得出碰撞后掃地的朝向。由題意，低端掃地機(jī)通過(guò)傳感器間隔一段時(shí)間掃描現(xiàn)場(chǎng)一次，選擇垃圾最多區(qū)域進(jìn)行清掃。我們可以理解為它不能對(duì)區(qū)域進(jìn)行實(shí)時(shí)掃描，且在下一次掃描之前清掃區(qū)域始終保持在前一次掃描所判斷出的垃圾總指標(biāo)最高的區(qū)域內(nèi)進(jìn)行清掃。為保證清掃路徑保持在前一次掃描所判斷出的垃圾總指標(biāo)最高的區(qū)域內(nèi)，我們已經(jīng)給出了如圖1.2 所示的區(qū)域分區(qū)方式。下面我們就路徑規(guī)劃的

16、幾種情況給出如下規(guī)定。 ①對(duì)于掃描發(fā)生在整個(gè)工作區(qū)域，當(dāng)次掃描先于碰撞的情況 回溯到上一次的路徑選擇，我們知道下一次掃地機(jī)與墻壁發(fā)生碰撞時(shí)參考點(diǎn)的坐標(biāo)（下一條選擇路徑的起點(diǎn)坐標(biāo)）即為上一條選擇路徑的終點(diǎn)坐標(biāo)。下一條路徑的起點(diǎn)坐標(biāo)已經(jīng)確定，下面我們來(lái)討論由該起點(diǎn)引出的多條路徑的優(yōu)化選擇方式。因?yàn)閽呙璋l(fā)生在掃地機(jī)在區(qū)域內(nèi)的行進(jìn)途中，即掃描的過(guò)程先于碰撞，所以用于路徑選擇判斷的數(shù)據(jù)為掃描時(shí)刻的數(shù)據(jù)。因此，我們可以建立一個(gè)矩陣保存各個(gè)單元的垃圾即時(shí)的指標(biāo)值。 ②碰撞先于掃描的情況 對(duì)于低端掃地機(jī)來(lái)說(shuō)，我們默認(rèn)其只有在掃描后才能對(duì)區(qū)域的垃圾指標(biāo)進(jìn)行分析和計(jì)算垃圾總指標(biāo)值最大的路徑。相比于智能度比

17、較高的掃地機(jī)，低端掃地機(jī)不具有預(yù)測(cè)和推算的功能。對(duì)此，我們做出這樣的規(guī)定：低端掃地機(jī)在上述情況中，將在最新一次掃描所判斷出的垃圾指標(biāo)值最大的區(qū)域中，隨機(jī)選取特有邊界上的一點(diǎn)作為下一條路徑的終點(diǎn)進(jìn)行清掃。綜上所述，劃分情況的要點(diǎn)是低端掃地機(jī)對(duì)區(qū)域進(jìn)行掃描不是實(shí)時(shí)的，而是間隔一段時(shí)間。 （4） 程序框圖 （5）運(yùn)算結(jié)果與分析 因?yàn)閽叩貦C(jī)的清掃路徑有一定的隨機(jī)性，故同樣的實(shí)例模型進(jìn)行多次試驗(yàn)肯定會(huì)產(chǎn)生不同的清掃路徑，所用時(shí)間的不同。為使結(jié)果更具有說(shuō)服力，我們采用測(cè)取6 組數(shù)據(jù)取平均值的方法來(lái)計(jì)算。具體實(shí)驗(yàn)記錄如表1通過(guò)Matlab 對(duì)實(shí)驗(yàn)進(jìn)行可視化演示，得到表1、圖4.1.2區(qū)域行駛路徑示

18、意和圖4.1.3 運(yùn)行路程/m 運(yùn)行時(shí)間/s ST=12.5m 1 290.7133 1162.9 2 374.6146 1498.5 3 370.7776 1483.1 平均值 345.3685 1381.5 表1 模型I數(shù)據(jù)記錄 圖4.1.2 模型I掃地機(jī)區(qū)域行駛路徑示意圖 圖4.1.3 模型I區(qū)域完成清掃后垃圾分布 完成清掃后垃圾分布的結(jié)果。根據(jù)實(shí)驗(yàn)結(jié)果，我們可以知道掃地機(jī)完成清潔工作的平均時(shí)間大約為23min，符合實(shí)際，認(rèn)為是正確的。 4.2問(wèn)題二：智能掃地機(jī)的運(yùn)行路徑 智能程度高的掃地機(jī)具有實(shí)時(shí)掃描的功能，在每一

19、個(gè)與墻壁碰撞的瞬間其都會(huì)重新掃描。所以如何設(shè)計(jì)機(jī)器人的清掃路線是本題的關(guān)鍵。掃地機(jī)每次與墻壁發(fā)生碰撞的瞬間，掃描整個(gè)區(qū)域計(jì)算出各個(gè)方向上的垃圾指標(biāo)值，并從中選擇出一條垃圾總指標(biāo)值最高的路徑（路徑的出發(fā)點(diǎn)為碰撞點(diǎn)）。由于機(jī)器人的轉(zhuǎn)彎方向是任意的，如何簡(jiǎn)化問(wèn)題使得機(jī)器人在有限的方向（0-180）上計(jì)算垃圾的總數(shù)是我們所需要考慮的。在這里我們把掃描此刻的碰撞點(diǎn)作為固定的參考點(diǎn)，連接碰撞點(diǎn)與除去碰撞點(diǎn)所在的墻壁以外的另外三面墻壁上的分割間斷點(diǎn)，做出直線并計(jì)算各個(gè)直線上的垃圾總指標(biāo)。比較各個(gè)方向上的垃圾總指標(biāo)的大小，判斷出最大值進(jìn)而得出轉(zhuǎn)彎方向。 4.2.1模型：實(shí)時(shí)掃描模型 (1）區(qū)域的劃分 首

20、先我們建立一個(gè)251*300的矩陣，并將各個(gè)單元里的垃圾指標(biāo)賦入與二位矩陣組合形成一個(gè)三維數(shù)組。由于機(jī)器人的半徑為0.2 米（面積為π/25≈0.126 ㎡），將區(qū)域分成若干0.1*0.1 ㎡的方格。可以看出機(jī)器人可以覆蓋大約16 個(gè)方格（0.4*0.4㎡）。 （2）時(shí)刻掃描的抽象處理方法 根據(jù)問(wèn)題重述我們可以知道智能掃地機(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ǔ)。所以我們可以給出：智能程度高的掃地機(jī)掃描垃圾計(jì)算指標(biāo)值的過(guò)程發(fā)生在與墻壁發(fā)生碰撞的瞬間；

21、 (3)模型II 的分析與建立 在掃地機(jī)的行駛過(guò)程中，我們做出這樣的假設(shè)只要碰到某個(gè)（單元？方格？）就算是清掃到了該區(qū)域，即認(rèn)為垃圾指標(biāo)值減1。 ① 優(yōu)化路徑選取 為了提高掃地機(jī)單位時(shí)間內(nèi)的清掃量，我們選擇清掃垃圾總數(shù)量最多的路徑。在這里我們引入一個(gè)參數(shù)C，稱為經(jīng)過(guò)路徑的垃圾總指標(biāo)值。根據(jù)我們所建立的模型可以列出公式，通過(guò)計(jì)算每條路徑的C 值的大小，判斷出最大的C 值所在路徑的終點(diǎn)，進(jìn)而得出碰撞后掃地的朝向。 ② 最優(yōu)化路徑選取 在前面我們采取的優(yōu)化路徑選取方式是計(jì)算出垃圾總指標(biāo)數(shù)最大的路徑進(jìn)行清掃。但是考慮到不同的路徑有不同的長(zhǎng)短，垃圾總指標(biāo)數(shù)最大的路徑不一

22、定是效率最高的，即相同的時(shí)間內(nèi)清掃的垃圾個(gè)數(shù)不一定是最高的。顯然，以垃圾總指標(biāo)數(shù)為路徑選擇判斷的依據(jù)是不夠優(yōu)化的。于是，我們將引入經(jīng)過(guò)路徑的垃圾指標(biāo)分布律Pk進(jìn)行進(jìn)一步優(yōu)化的路徑選擇。 （4） 運(yùn)算思路框圖 （5） 運(yùn)算結(jié)果與分析 通過(guò)Matlab 對(duì)實(shí)驗(yàn)進(jìn)行可視化演示，得到表2、圖4.2.1 區(qū)域行駛路徑示意和圖4.2.2完成清掃后垃圾分布的結(jié)果。 數(shù)據(jù)記錄 運(yùn)行路程/m 194.1670 運(yùn)行時(shí)間/s 776.6680 表2 實(shí)時(shí)掃描模型數(shù)據(jù)記錄 圖4.2.1 實(shí)時(shí)掃描模型掃地機(jī)區(qū)域行駛路徑示意圖 圖4.2.2 實(shí)時(shí)掃描模型掃地機(jī)區(qū)域完成清掃

23、后垃圾分布 根據(jù)實(shí)驗(yàn)結(jié)果，我們可以知道掃地機(jī)完成清潔工作的時(shí)間大約為13min，符合實(shí)際，認(rèn)為是正確的。與傳統(tǒng)的掃地機(jī)不同，智能掃地機(jī)實(shí)時(shí)可以通過(guò)微處理器進(jìn)行現(xiàn)場(chǎng)環(huán)境分析，自動(dòng)選擇運(yùn)行路線。 4.3 問(wèn)題三：掃地機(jī)的優(yōu)化路徑 關(guān)于設(shè)計(jì)掃地機(jī)的路徑保證其以最短的時(shí)間清掃完該區(qū)域（問(wèn)題三）的關(guān)鍵在于提高單位長(zhǎng)度上清掃垃圾指標(biāo)的數(shù)量。 4.3.1模型：實(shí)時(shí)掃描折線模型 與傳統(tǒng)的掃地機(jī)不同，智能掃地機(jī)實(shí)時(shí)可以通過(guò)微處理器進(jìn)行現(xiàn)場(chǎng)環(huán)境分析，自動(dòng)選擇運(yùn)行路線。 （1）區(qū)域的劃分 同4.2.1(1） （2）時(shí)刻掃描的抽象處理方法 時(shí)刻掃描區(qū)域現(xiàn)場(chǎng)，參

24、考點(diǎn)每移動(dòng)一個(gè)單元都要進(jìn)行實(shí)時(shí)的監(jiān)控掃描。 （3）模型III 的分析與建立——優(yōu)化路徑選取 在模型II 中，我們選擇C 最大的路徑作為下一步的清掃路徑。再深一步考慮，我們可以猜想到會(huì)有以下幾種情況的發(fā)生。 ①存在兩個(gè)以上的長(zhǎng)度相等的路徑同時(shí)為C 的最大值所在路徑； ②存在兩個(gè)以上的長(zhǎng)度不等的路徑同時(shí)為C 的最大值所在路徑； ③存在一個(gè)長(zhǎng)度較短的路徑( l1)其垃圾總指標(biāo)為C1、一個(gè)長(zhǎng)度較長(zhǎng)的路徑（l 2 ）其垃圾總指標(biāo)為C2，而有的條件為了提高清掃的效率，我們選擇單位長(zhǎng)度上垃圾指標(biāo)值最高的路徑。在這里我們引入一個(gè)參數(shù)P，稱垃圾指標(biāo)分布律。根據(jù)我們

25、所建立的模型可以列出公式： （其中mi為直線路徑所經(jīng)過(guò)單元的垃圾指標(biāo)值；N為經(jīng)過(guò)區(qū)域的單位總數(shù)） 通過(guò)計(jì)算每條路徑的值的大小，判斷出最大的值所在路徑的終點(diǎn)，進(jìn)而得出碰撞后掃地的朝向。計(jì)算出每個(gè)方向的并進(jìn)行比較,判斷出最大的方向并選定其為下一次路徑。如題目要求，機(jī)器人每次經(jīng)過(guò)一個(gè)單位，則該方格垃圾指標(biāo)值減1，即矩陣中的相應(yīng)元素減1。為了控制掃地機(jī)工作的結(jié)束，我們認(rèn)為掃地機(jī)在每次與墻壁發(fā)生碰撞的瞬間都會(huì)計(jì)算此時(shí)所有單元垃圾指標(biāo)值是否都不大于1？直到碰到墻壁后計(jì)算出此時(shí)所有單元垃圾指標(biāo)值都不大于 1 時(shí)，掃地機(jī)自行回到充電站并停止工作。否則再次進(jìn)行判斷繼續(xù)向下一個(gè)值最大的路徑行進(jìn)。

26、 （4） 程序框圖 （5） 計(jì)算結(jié)果與分析 通過(guò)Matlab 對(duì)實(shí)驗(yàn)進(jìn)行可視化演示，得到表3、圖8.5.1 區(qū)域行駛路徑示意和圖8.5.2完成清掃后垃圾分布的結(jié)果。 數(shù)據(jù)記錄 運(yùn)行路程/m 39.4065 運(yùn)行時(shí)間/s 157.6260 表3 實(shí)時(shí)掃描折線模型數(shù)據(jù)記錄 圖4.3.1 模型Ⅲ優(yōu)化后清掃垃圾路徑示意圖 圖4.3.2 模型Ⅲ優(yōu)化后清掃垃圾示意圖 根據(jù)實(shí)驗(yàn)結(jié)果，我們可以知道掃地機(jī)完成清潔工作的時(shí)間大約為3min，符合實(shí)際，認(rèn)為是正確的。 4.4 模型Ⅰ與模型Ⅱ的比較 比較問(wèn)題1 與問(wèn)題2，說(shuō)明問(wèn)題1 中方案的合

27、理性。 數(shù)據(jù)比較分析 模型I 模型II 運(yùn)行路程/m 345.3685 194.1670 運(yùn)行時(shí)間/s 1381.5 776.6680 從上面的分析可以看出，低端掃地機(jī)從性能上來(lái)講要比智能掃地機(jī)差，但是低端機(jī)就必然有其存在的價(jià)值。也會(huì)有一定的優(yōu)越性。兩者的共性是完成掃地的時(shí)間相差不是很懸殊。 ①?gòu)脑囉萌巳簛?lái)講 低端掃地機(jī)相比于智能掃地機(jī)在價(jià)格上要低很多，大多數(shù)的消費(fèi)者還是普通的收入水平，因此低端掃地機(jī)可以滿足更多人的消費(fèi)需求，更利于掃地機(jī)的普及以及推廣。不同的人對(duì)清掃垃圾的指標(biāo)有不同的要求，低端機(jī)綜合以上兩點(diǎn)，會(huì)在市場(chǎng)中占有一席之地。 ②從耐用程度來(lái)講 低端

28、機(jī)的掃描以及內(nèi)部的程序相對(duì)比較簡(jiǎn)單，而智能掃地機(jī)為實(shí)現(xiàn)其高度的智能化，掃描的過(guò)程及其程序要相對(duì)比較復(fù)雜。因此，在機(jī)器的維護(hù)上，低端機(jī)要比智能掃地機(jī)簡(jiǎn)單的多，假設(shè)兩臺(tái)機(jī)器配備相同的電池，智能掃地機(jī)由于要進(jìn)行相對(duì)較頻繁的掃描，以及對(duì)內(nèi)部復(fù)雜程序的供電支持，因此智能機(jī)的耗電量要大一些，這個(gè)道理類似于手機(jī)當(dāng)中的智能機(jī)與普通機(jī)。綜合以上的分析，我們可以得出一個(gè)結(jié)論，低端掃地機(jī)的壽命要高于智能機(jī)的使用壽命。 ③從開(kāi)發(fā)編程著想 通過(guò)對(duì)整個(gè)區(qū)域進(jìn)行劃分，即對(duì)區(qū)域內(nèi)的單元進(jìn)行分區(qū)，將多個(gè)單元合并成一個(gè)小區(qū)域進(jìn)行考慮大大減少了運(yùn)算是的數(shù)據(jù)總量，進(jìn)而縮短運(yùn)算運(yùn)行時(shí)間，達(dá)到提高效率的目的。另外，一方面若是要提高低

29、端掃地機(jī)的效用，可以通過(guò)優(yōu)化計(jì)算出最合理的掃描時(shí)間。進(jìn)而達(dá)到縮短清掃時(shí)間的效果。 五、模型的檢驗(yàn) 我們采取如圖4.1.1所示的區(qū)域分割方式，這樣的分割方式可以保證掃地機(jī)在掃垃圾指標(biāo)值最大的分區(qū)過(guò)程中，路徑不覆蓋其他分區(qū)。認(rèn)為是比較合理， 但是，不可否認(rèn)這樣的分割區(qū)域方式不是最合理的。 通過(guò) Matlab 對(duì)實(shí)驗(yàn)進(jìn)行可視化演示，得到表 1、圖4.1.2 區(qū)域行駛路徑示意和圖4.1.3 完成清掃后垃圾分布的結(jié)果。 根據(jù)實(shí)驗(yàn)結(jié)果，我們可以知道掃地機(jī)完成清潔工作的時(shí)間大約為23min，符合實(shí)際，認(rèn)為是正確的，模型是正確的。 再者又可得到表2、圖4.2.1區(qū)域行駛路徑示意和圖 4.2.2

30、 完成清掃后垃圾分布的結(jié)果。根據(jù)實(shí)驗(yàn)結(jié)果，我們可以知道掃地機(jī)完成清潔工作的時(shí)間大約為 13min，符合實(shí)際，認(rèn)為是正確的，即模型是合理的。 通過(guò)得到的表3、圖4.3.1區(qū)域行駛路徑圖和圖4.3.2完成清掃后垃圾分布的結(jié)果。根據(jù)實(shí)驗(yàn)結(jié)果，我們可以知道掃地機(jī)完成清潔工作的時(shí)間大約為3min，符合實(shí)際，認(rèn)為是正確的。 六、模型的評(píng)價(jià) 在本文中，我們采用了區(qū)域抽象化、柵格和線性規(guī)劃模型求解，并且通過(guò)Matlab軟件仿真模型進(jìn)行驗(yàn)證，具有以下優(yōu)點(diǎn)： （1）采取區(qū)域抽象化，并采取一定的手段讓問(wèn)題透明化，使問(wèn)題變得更簡(jiǎn)單，容易理解。 （2） 通過(guò)柵格模型，對(duì)問(wèn)題進(jìn)行具體化

31、，使對(duì)問(wèn)題的分析更明確和清晰。 （3）采用線性規(guī)劃模型，使問(wèn)題層次更鮮明，有利于問(wèn)題的解決。 不可否認(rèn)，模型也存在著如下缺點(diǎn)： （1）掃地機(jī)柵格化之后，使得本該掃不到的地方（如墻角）也納入清掃范圍。這樣的后果是使得清掃率的計(jì)算存在誤差。但是，由于題設(shè)的要求是盡量保證每個(gè)點(diǎn)的垃圾指標(biāo)不超過(guò)1， 我們可以認(rèn)為誤差是在允許的范圍內(nèi)的 。 （2）計(jì)算機(jī)器人行進(jìn)過(guò)程中清掃到的區(qū)域時(shí)，由于機(jī)器人實(shí)際上是圓形的，而計(jì)算時(shí)以方格為單位，有一定的誤差。 參考文獻(xiàn) [1]王仲民，移動(dòng)機(jī)器人路徑規(guī)劃及軌跡跟蹤問(wèn)題研究，河北工業(yè)大

32、學(xué)，2006年3月。 [2]陳恩水、王峰，數(shù)學(xué)建模與實(shí)驗(yàn)，科學(xué)出版社，2008年6月第一版。 [3] 毛保華.線性規(guī)劃的若干算法研究[D].2010. [4]智能掃地機(jī)器人工作原理解析，豆丁網(wǎng)，2014,7.20. 附錄： MATLAB源代碼： 問(wèn)題一： Y=C:\ %原數(shù)據(jù)矩陣 J=zeros(251,300); for i=1:251 for j=1:100 J(i,(j*3-2):(j*3))=Y(i,j); end; end;

33、 %轉(zhuǎn)換矩陣 d1=zeros(5,5); for i=1:5 for j=1:5 d1(i,j)=10*j+60*(i-1)+10; end; end; %產(chǎn)生邊界枚舉點(diǎn) a=1; b=50; m=0; sumtime=0; sumtime1=0; sumline=0; MAX1=sum(sum(J))*0.02; %設(shè)定常數(shù) for v=1:1000 maxa=0; MAX=0;

34、 for k=1:5 si=0; for i=1:251 for j=1:60 si=si+J(i,(j+60*(k-1))); end; end; MAX=MAX+si; if si>maxa maxa=si; m=k; end; end; %找出最優(yōu)區(qū)域 for c=1:1000

35、 b1=d1(m,fix(rand(1)*5)+1); if a<100 a1=231; else a1=1; end; sumtime=sumtime+ sqrt((a-a1)^2+(b-b1)^2)/12.5; sumline=sumline+sqrt((a-a1)^2+(b-b1)^2)/50; if a1>=a if b1>=b for x=1:251

36、 for y=1:300 if(x>=a && x<=a1+20) if(y<=b1 && y>=b-20) if(y<=(b1-b)*(x-a)/(a1-a)+b && y>=(b1-b)*(x-a-20)/(a1-a)+b-20) if J(x,y)>1 J(x,y)=J(x,y)-1;

37、 else J(x,y)=0; end end end end end end else for x=1:251 for y=1:300

38、 if(x>=a && x<=a1+20) if(y>=b1-20 && y<=b) if(y<=(b-b1)*(x-a-20)/(a-a1)+b && y>=(b-b1)*(x-a1)/(a-a1)+b1-20) if J(x,y)>1 J(x,y)=J(x,y)-1

39、; else J(x,y)=0; end end end end end end end else if b1>=b for x=

40、1:251 for y=1:300 if(x>=a1 && x<=a+20) if(y<=b1 && y>=b-20) if(y<=(b-b1)*(x-a-20)/(a-a1)+b && y>=(b-b1)*(x-a)/(a-a1)+b-20) if J(x,y)>1

41、 J(x,y)=J(x,y)-1; else J(x,y)=0; end end end end end end els

42、e for x=1:251 for y=1:300 if(x>=a1 && x<=a+20) if(y>=b1-20 && y<=b) if(y<=(b1-b)*(x-a)/(a1-a)+b && y>=(b1-b)*(x-a-20)/(a1-a)+b-20) if J(x,y)>1

43、 J(x,y)=J(x,y)-1; else J(x,y)=0; end; end; end; end; e

44、nd; end; end; end; figure(1) line([a a1],[b b1]); hold on figure(2) imagesc(J); MAX2=sum(sum(J)); a=a1; b=b1; if sumtime>50 %掃描間隔 sumtime1=sumtime1+sumtime; break; end;

45、 end; %在限定區(qū)域內(nèi)隨機(jī)選擇路徑 sumtime=0; if MAX2

46、 J(i,(j*3-2):(j*3))=Y(i,j); end; end; a0=200; b0=20; a=a0; b=b0; sum_time=0; sum_line=0; J2=zeros(251,300); s=zeros(251,300); a1=0; b1=0; MAX=sum(sum(J))*0.02; for c=1:1000 if (a==1) for A=1:231 B=300; for x=1:251

47、 for y=1:300 if( x<=A+20 && x>=a ) if(y>=b-20 && y<=300) if(y<=(B-b)*(x-a)/(A-a)+b && y>=(B-b)*(x-a-20)/(A-a)+b-20) J2(x,y)=J(x,y); end;

48、 end; end; end; end; s(A,B)=sum(J2(:)); J2=zeros(251,300); end; for B=b:300 A=231; for x=1:251 for y=1:300 if( x<=A+20 && x>=a)

49、 if(y>=b-20 && y<=B) if(y<=(B-b)*(x-a)/(A-a)+b && y>=(B-b)*(x-a-20)/(A-a)+b-20) J2(x,y)=J(x,y); end; end; end; end;

50、 end; s(A,B)=sum(J2(:)); J2=zeros(251,300); end; for B=20:b-1 A=231; for x=1:251 for y=1:300 if(x>=a && x<=A+20) if(y>=B-20 && y<=b) if

51、(y<=(b-B)*(x-a-20)/(a-A)+b && y>=(b-B)*(x-a)/(a-A)+b-20) J2(x,y)=J(x,y); end; end; end; end; end; s(A,B)=sum(J2(:)); J2=zeros(251,

52、300); end; for A=1:240 B=20; for x=1:251 for y=1:300 if(x>=a && x<=A+20) if(y>=B-20 && y<=b) if(y<=(b-B)*(x-a-20)/(a-A)+b && y>=(b-B)*(x-a)/(a-A)+b-20)

53、 J2(x,y)=J(x,y); end; end; end; end; end; s(A,B)=sum(J2(:)); J2=zeros(251,300); end; end; if (a==231) for A=1:231

54、 B=300; for x=1:251 for y=1:300 if( x<=a+20 && x>=A ) if(y>=b-20 && y<=300) if(y<=(B-b)*(x-a)/(A-a-20)+b && y>=(B-b)*(x-a)/(A-a)+b-20) J2(x,y)=J(x,

55、y); end; end; end; end; end; s(A,B)=sum(J2(:)); J2=zeros(251,300); end; for B=b:300 A=1; for x=1:251 for y=

56、1:300 if( x<=a+20 && x>=A ) if(y>=b-20 && y<=B) if(y<=(B-b)*(x-a)/(A-a-20)+b && y>=(B-b)*(x-a)/(A-a)+b-20) J2(x,y)=J(x,y); end; end;

57、 end; end; end; s(A,B)=sum(J2(:)); J2=zeros(251,300); end; for B=20:b-1 A=1; for x=1:251 for y=1:300 if(x>=1 && x<=a+20)

58、 if(y>=B-20 && y<=b) if(y<=(B-b)*(x-a)/(A-a)+b && y>=(B-b)*(x-a-20)/(A-a)+b-20) J2(x,y)=J(x,y); end; end; end; end; end;

59、 s(A,B)=sum(J2(:)); J2=zeros(251,300); end; for A=1:231 B=20; for x=1:251 for y=1:300 if(x>=A && x<=a+20) if(y>=1 && y<=b) if(y<=(B-b)*(x-a)/(

60、A-a)+b && y>=(B-b)*(x-a-20)/(A-a)+b-20) J2(x,y)=J(x,y); end; end; end; end; end; s(A,B)=sum(J2(:)); J2=zeros(251,300); end

61、; end; if (b==300) for B=20:300 A=231; for x=1:251 for y=1:300 if( x<=251 && x>=a ) if(y>=B-20 && y<=300) if(y<=(b-B)*(x-a-20)/(a-A)+b &&y>=(b-B)*(x-a)/(a-A)+b-20

62、) J2(x,y)=J(x,y); end; end; end; end; end; s(A,B)=sum(J2(:)); J2=zeros(251,300); end; for A=a:231 B=

63、20; for x=1:251 for y=1:300 if( x<=A+20 && x>=a ) if(y>=1 && y<=300) if(y<=(b-B)*(x-a-20)/(a-A)+b && y>=(b-B)*(x-a)/(a-A)+b-20) J2(x,y)=J(x,y);

64、 end; end; end; end; end; s(A,B)=sum(J2(:)); J2=zeros(251,300); end; for A=1:a-1 B=20; for x=1:251 for y=1:300

65、 if(x>=A && x<=a+20) if(y>=1 && y<=300) if(y<=(B-b)*(x-a)/(A-a)+b && y>=(B-b)*(x-a-20)/(A-a)+b-20) J2(x,y)=J(x,y); end; end;

66、 end; end; end; s(A,B)=sum(J2(:)); J2=zeros(251,300); end; for B=20:300 A=1; for x=1:251 for y=1:300 if(x>=1 && x<=a+20) if(y>=B-20 && y<=300) if(y<=(B-b)*(x-a)/(A-a)+b && y>=(B-b)*(x-a-20)/(A-a)+b-20) J2(x,y)=J(x,y); end;