掃地機器人的路徑策略

數(shù)學建模小組作業(yè)第10組組員：+ 掃地機器人的路徑優(yōu)化二一四年七月二十三日38 掃地機器人的路徑策略【摘要】我們將掃地機在房間內(nèi)掃垃圾的路徑策略問題抽象為方格化模型，用原始給定數(shù)據(jù)做出垃圾指標矩陣Q300*251,根據(jù)掃地機需要的行走路徑進行程序嵌套，并用線性規(guī)劃的方法來進行最優(yōu)解的求取，然后根據(jù)建立的模型，用Matlab進行仿真演示。最終可以觀察到掃地機在每種情況下的清掃路徑。由于墻角也會存在垃圾，因此一般情況下我們不能實現(xiàn)100%的清掃，所以我們在此規(guī)定清掃完95%的區(qū)域即作為合格的條件。下面我們根據(jù)題目要求進行如下考慮：問題一經(jīng)過分析我們可以將整個清掃區(qū)域劃分成如圖4.1.1所示的小區(qū)域，通過運用矩陣整合函數(shù)，將矩陣Q300*251整合成一維數(shù)組T5，經(jīng)過固定時間間隔的掃描判斷T（1），T(2),T(3),T(4),T(5)MAX所對應(yīng)的區(qū)域，在區(qū)域邊沿隨機選取坐標作為運行起始點，如果檢測到的最大的元素的所在區(qū)域發(fā)生了變化，則根據(jù)當前位置與隨機選好的碰撞點進行路徑轉(zhuǎn)移，按照這種方式運行，直到達到掃地機的結(jié)束條件停止。問題二這時掃地機每次只選擇垃圾總指標最多的路徑，并且每次掃描發(fā)生在掃地機與墻壁發(fā)生碰撞的時。掃描過后，機器人可以任意選擇方向，選擇方向的合適程度將成為掃地機掃地效率的關(guān)鍵，所以我們設(shè)定某一點作為掃地機掃描的起點每次碰撞時的掃描決定下一時刻可能的轉(zhuǎn)彎方向，即某個方向上的垃圾總指標Ck最大的即為下一時刻的轉(zhuǎn)彎方向。問題三設(shè)計智能掃地機路徑，保證掃地機以最短時間達到清掃要求，我們可以選取以下兩種優(yōu)化方向：（1）避免與墻壁進行碰撞，提高機器的靈活性；（2）提高單位長度上清掃垃圾指標總量，即提高清掃效率。比較問題1與問題2問題1中的方案存在其合理性，問題2中則顯得較為高效，比較兩者發(fā)現(xiàn)：改變ST大小可以改變地段掃地機性能。關(guān)鍵詞： 線性規(guī)劃 路徑轉(zhuǎn)移 劃分區(qū)域 清掃效率目 錄1、 問題重述 32、 模型假設(shè) 4 3、 符號說明 44、 模型建立與求解 44.0 問題分析 4 4.0.1 基本模型54.1 問題一：低端掃地機的工作路徑 6 4.1.1 模型:分區(qū)掃描模型 64.2 問題二：智能掃地機的工作路徑 10 4.2.1模型：實時掃描模型114.3 問題三：掃地機的優(yōu)化路徑 13 4.3.1 模型：實時掃描折線模型 13 4.4 模型I與模型II的比較 175、 模型的檢驗186、 模型的評價18參考文獻20附錄211、 問題重述1.1問題背景隨著科學技術(shù)的不斷發(fā)展，掃地機逐步走入平常百姓家，并被越來越多的人所接受，掃地機（也稱掃地機器人）將在不久的將來像白色家電一樣成為每個家庭必不可少的清潔幫手。產(chǎn)品也會由現(xiàn)在的初級智能向著更高程度的智能化程度發(fā)展，逐步取代人工清潔。掃地機是通過電動機的高速旋轉(zhuǎn)，在主機內(nèi)形成真空，利用由此產(chǎn)生的高速氣流，從吸入口吸進垃圾。掃地機一般為半徑0.2米圓盤，、運行速度一般在每秒0.25米左右，只走直線，且碰到墻壁等障礙才可轉(zhuǎn)彎。與傳統(tǒng)的掃地機不同，智能掃地機可以通過微處理器進行現(xiàn)場環(huán)境分析，自動選擇運行路線。遇到障礙發(fā)生碰撞后將重新隨機地選擇路線，逐步進行清掃。智能掃地機具有記憶、存儲功能。利用傳感器掃描現(xiàn)場環(huán)境，設(shè)計運行路徑并存儲。一般不能100%的清掃指定區(qū)域（如墻角部分）。清掃后的垃圾裝進機子尾部的集塵盒，再通過人工清倒垃圾。機器在工作電壓不足時會自動回到充電站充電。1.2目標任務(wù)考慮圖1的工作現(xiàn)場，其中點A（1,5）為掃地機充電站，區(qū)域的垃圾指標見附件1.不考慮再充電情況，有以下問題：問題一：有些低檔的掃地機因為價格低廉，智能程度不高。其工作時的路徑選擇方案是將現(xiàn)場分成若干區(qū)域（例如上下左右4個區(qū)域），并通過傳感器間隔一段時間掃描現(xiàn)場一次，選則垃圾最多區(qū)域清掃。假設(shè)每次掃過的區(qū)域垃圾指標值減少1。針對附件1，估計清掃完給定區(qū)域大致需要的時間（盡量保證每個點的垃圾指標不超過1）。 問題二：智能程度高的掃地機每次可以選擇清掃垃圾指標值最大的地方清掃，每次掃過的區(qū)域垃圾指標值減少1。該機器人需多長時間才能保證清掃完該區(qū)域（區(qū)域內(nèi)指標值不超過1）。比較問題1與問題2，說明問題1中方案的合理性。 問題三：其他條件同2，如何設(shè)計掃地機的路徑，保證掃地機以最短時間清掃完該區(qū)域。 2、 模型的假設(shè)1、 假設(shè)掃地機有充足的電量行駛完全部的軌跡，并且不會發(fā)生任何障礙；2、 假設(shè)路面平坦，不會產(chǎn)生較大程度的偏移或者是翻轉(zhuǎn)；3、 假設(shè)高端的和低端的掃地機有鮮明的特點，并嚴格按自己的特點運行；4、 假設(shè)掃地機掃過單元格一半及以上的面積時，單元格內(nèi)的垃圾指標減少1；5、 假設(shè)題目中給的點A始終為掃地機工作的起點；6、 假設(shè)由于種種環(huán)境因素不會對掃地機速率產(chǎn)生比較大的影響；7、 假設(shè)掃地機工作時沒有人為的影響改變掃地機的軌跡；8、 假設(shè)當每個點的垃圾指標不超過1時掃地機的清掃任務(wù)結(jié)束；9、 假設(shè)掃地機在掃描的過程中沒有額外的占用移動時間，即掃描時間不會影響最終的運動時間。3、 符號說明Y(251，100) 初始垃圾指標矩陣J(251，300) 程序中的垃圾指標矩陣（a,b） 發(fā)生碰撞時刻參考點坐標（A,B） 下一次發(fā)生碰撞時刻參考點坐標ST 間隔掃描行駛路程S 從（a，b）到（A,B）掃地機行駛的路程T(n) 從充電點到第n個碰壁點掃地機行駛的時間CK 經(jīng)過路徑的垃圾總指標PK 經(jīng)過路徑的垃圾指標分布律4、 模型的建立與求解4.0問題分析由問題重述可知，智能的掃地機（不管是低檔還是高檔）都會按0.4米的寬度以0.25米每秒進行直線運行，并且路徑上都選擇與墻壁碰撞后掃描計算出的垃圾指標最高點行駛，這是所有問題的共同點。4.0.1基本模型（1） 清掃區(qū)域直觀圖首先我們建立一個300*251的矩陣Q，并將各個單元里的垃圾指標賦入與二位矩陣組合形成一個三維數(shù)組。如圖4.0.1所示為將題目中給定的附錄1導(dǎo)入矩陣Q后的垃圾指標空間分布圖。（2） 清掃區(qū)域方格化由于掃地機只走直線，碰到墻壁后才會轉(zhuǎn)彎，所以，掃地機與墻壁碰撞之后會有180o的方向選擇。每個指向都對應(yīng)著一個所在方向的垃圾總指標CK，其中k每個方向的路線標志。（3） 路徑的線性規(guī)劃掃地機從碰撞點到下一個碰撞點所掃過的路程如圖4.0.2所示。我們將區(qū)域分割成300*251的矩陣，每個單元存儲著垃圾指標值。通過判斷點坐標是否在路徑中來判斷單元垃圾指標值是否減1.圖4.0.1 垃圾指標分布圖 圖4.0.2 線性規(guī)劃推導(dǎo)條件根據(jù)圖示，可以得到以下約束條件： 且 4.1問題一：低端掃地機的運行路徑對于問題一，低端掃地機需要對區(qū)域進行分區(qū)且不能時刻掃描計算垃圾指標值，總是經(jīng)過一段規(guī)定的時間后，才會重新規(guī)劃路線，沒有進行下次掃描，則在當前判斷垃圾指數(shù)最高的區(qū)域隨機清掃，我們需要將區(qū)域分成幾個小的區(qū)域，低端掃地機在掃描后達到垃圾總指標最高的區(qū)域清掃，清掃隨機選取。4.1.1模型：分區(qū)掃描模型（1） 區(qū)域的劃分通過分析問題一的工作特點，我們得到了一個相對比較合理的分割方式，如圖4.1.1所示，我們進行的是五等分的條形分割，這樣的分割方式可以保證掃地機在掃垃圾指標值最大的分區(qū)過程中，路徑不覆蓋其他分區(qū)。圖4.1.1 分區(qū)分析示意圖（2） 間隔掃描時間的確定在這里我們不妨把間隔掃描時間抽象為間隔掃描行駛路程考慮。設(shè)定參數(shù)間隔掃描行駛路程ST ，并給ST 賦初值（12.5m）。舉個例子，假設(shè)發(fā)生碰撞時刻參考點坐標為(a,b)，掃地機下一次與墻壁發(fā)生碰撞時刻參考點的坐標為(A,B)，則從(a,b)到(A,B)掃地機行駛的路程S 有如下公式：（勾股定理）故充電點到第n個碰壁點掃地機行駛的時間T(n) （3） 模型的建立 在掃地機的行駛過程中，根據(jù)假設(shè)4的條件；根據(jù)區(qū)域所在的位置枚舉出參考點可以到達的點（單元）。在這些點中隨機選取一個作為下一次與墻壁的碰撞點。將這點與參考點相連，即為下一步可能的清掃路徑。為了提高清掃的效率，我們選擇清掃垃圾總數(shù)量最多的路徑。在這里我們引入一個參數(shù)C，稱為經(jīng)過路徑的垃圾總指標值。根據(jù)我們所建立的模型可以列出公式： （其中為直線路徑所經(jīng)過單元的垃圾指標值；N為經(jīng)過區(qū)域的單位總數(shù)）通過計算每條路徑的C 值的大小，判斷出最大的C 值所在路徑的終點，進而得出碰撞后掃地的朝向。由題意，低端掃地機通過傳感器間隔一段時間掃描現(xiàn)場一次，選擇垃圾最多區(qū)域進行清掃。我們可以理解為它不能對區(qū)域進行實時掃描，且在下一次掃描之前清掃區(qū)域始終保持在前一次掃描所判斷出的垃圾總指標最高的區(qū)域內(nèi)進行清掃。為保證清掃路徑保持在前一次掃描所判斷出的垃圾總指標最高的區(qū)域內(nèi)，我們已經(jīng)給出了如圖1.2 所示的區(qū)域分區(qū)方式。下面我們就路徑規(guī)劃的幾種情況給出如下規(guī)定。對于掃描發(fā)生在整個工作區(qū)域，當次掃描先于碰撞的情況回溯到上一次的路徑選擇，我們知道下一次掃地機與墻壁發(fā)生碰撞時參考點的坐標（下一條選擇路徑的起點坐標）即為上一條選擇路徑的終點坐標。下一條路徑的起點坐標已經(jīng)確定，下面我們來討論由該起點引出的多條路徑的優(yōu)化選擇方式。因為掃描發(fā)生在掃地機在區(qū)域內(nèi)的行進途中，即掃描的過程先于碰撞，所以用于路徑選擇判斷的數(shù)據(jù)為掃描時刻的數(shù)據(jù)。因此，我們可以建立一個矩陣保存各個單元的垃圾即時的指標值。碰撞先于掃描的情況對于低端掃地機來說，我們默認其只有在掃描后才能對區(qū)域的垃圾指標進行分析和計算垃圾總指標值最大的路徑。相比于智能度比較高的掃地機，低端掃地機不具有預(yù)測和推算的功能。對此，我們做出這樣的規(guī)定：低端掃地機在上述情況中，將在最新一次掃描所判斷出的垃圾指標值最大的區(qū)域中，隨機選取特有邊界上的一點作為下一條路徑的終點進行清掃。綜上所述，劃分情況的要點是低端掃地機對區(qū)域進行掃描不是實時的，而是間隔一段時間。（4） 程序框圖（5）運算結(jié)果與分析因為掃地機的清掃路徑有一定的隨機性，故同樣的實例模型進行多次試驗肯定會產(chǎn)生不同的清掃路徑，所用時間的不同。為使結(jié)果更具有說服力，我們采用測取6 組數(shù)據(jù)取平均值的方法來計算。具體實驗記錄如表1通過Matlab 對實驗進行可視化演示，得到表1、圖4.1.2區(qū)域行駛路徑示意和圖4.1.3運行路程/m運行時間/sST=12.5m1290.71331162.92374.61461498.53370.77761483.1平均值345.36851381.5表1 模型I數(shù)據(jù)記錄圖4.1.2 模型I掃地機區(qū)域行駛路徑示意圖圖4.1.3 模型I區(qū)域完成清掃后垃圾分布完成清掃后垃圾分布的結(jié)果。根據(jù)實驗結(jié)果，我們可以知道掃地機完成清潔工作的平均時間大約為23min，符合實際，認為是正確的。4.2問題二：智能掃地機的運行路徑 智能程度高的掃地機具有實時掃描的功能，在每一個與墻壁碰撞的瞬間其都會重新掃描。所以如何設(shè)計機器人的清掃路線是本題的關(guān)鍵。掃地機每次與墻壁發(fā)生碰撞的瞬間，掃描整個區(qū)域計算出各個方向上的垃圾指標值，并從中選擇出一條垃圾總指標值最高的路徑（路徑的出發(fā)點為碰撞點）。由于機器人的轉(zhuǎn)彎方向是任意的，如何簡化問題使得機器人在有限的方向（0-180）上計算垃圾的總數(shù)是我們所需要考慮的。在這里我們把掃描此刻的碰撞點作為固定的參考點，連接碰撞點與除去碰撞點所在的墻壁以外的另外三面墻壁上的分割間斷點，做出直線并計算各個直線上的垃圾總指標。比較各個方向上的垃圾總指標的大小，判斷出最大值進而得出轉(zhuǎn)彎方向。4.2.1模型：實時掃描模型(1）區(qū)域的劃分首先我們建立一個251*300的矩陣，并將各個單元里的垃圾指標賦入與二位矩陣組合形成一個三維數(shù)組。由于機器人的半徑為0.2 米（面積為/250.126 ），將區(qū)域分成若干0.1*0.1 的方格?？梢钥闯鰴C器人可以覆蓋大約16 個方格（0.4*0.4）。（2）時刻掃描的抽象處理方法根據(jù)問題重述我們可以知道智能掃地機可以通過微處理器進行現(xiàn)場環(huán)境分析，自動選擇運行路線。遇到障礙發(fā)生碰撞后將重新隨機地選擇路線，逐步進行清掃。智能掃地機具有記憶、存儲功能。利用傳感器掃描現(xiàn)場環(huán)境，設(shè)計運行路徑并存儲。所以我們可以給出：智能程度高的掃地機掃描垃圾計算指標值的過程發(fā)生在與墻壁發(fā)生碰撞的瞬間；(3)模型II 的分析與建立 在掃地機的行駛過程中，我們做出這樣的假設(shè)只要碰到某個（單元？方格？）就算是清掃到了該區(qū)域，即認為垃圾指標值減1。 優(yōu)化路徑選取 為了提高掃地機單位時間內(nèi)的清掃量，我們選擇清掃垃圾總數(shù)量最多的路徑。在這里我們引入一個參數(shù)C，稱為經(jīng)過路徑的垃圾總指標值。根據(jù)我們所建立的模型可以列出公式，通過計算每條路徑的C 值的大小，判斷出最大的C 值所在路徑的終點，進而得出碰撞后掃地的朝向。 最優(yōu)化路徑選取 在前面我們采取的優(yōu)化路徑選取方式是計算出垃圾總指標數(shù)最大的路徑進行清掃。但是考慮到不同的路徑有不同的長短，垃圾總指標數(shù)最大的路徑不一定是效率最高的，即相同的時間內(nèi)清掃的垃圾個數(shù)不一定是最高的。顯然，以垃圾總指標數(shù)為路徑選擇判斷的依據(jù)是不夠優(yōu)化的。于是，我們將引入經(jīng)過路徑的垃圾指標分布律Pk進行進一步優(yōu)化的路徑選擇。（4） 運算思路框圖（5） 運算結(jié)果與分析 通過Matlab 對實驗進行可視化演示，得到表2、圖4.2.1 區(qū)域行駛路徑示意和圖4.2.2完成清掃后垃圾分布的結(jié)果。數(shù)據(jù)記錄運行路程/m194.1670運行時間/s776.6680表2 實時掃描模型數(shù)據(jù)記錄圖4.2.1 實時掃描模型掃地機區(qū)域行駛路徑示意圖圖4.2.2 實時掃描模型掃地機區(qū)域完成清掃后垃圾分布 根據(jù)實驗結(jié)果，我們可以知道掃地機完成清潔工作的時間大約為13min，符合實際，認為是正確的。與傳統(tǒng)的掃地機不同，智能掃地機實時可以通過微處理器進行現(xiàn)場環(huán)境分析，自動選擇運行路線。4.3 問題三：掃地機的優(yōu)化路徑 關(guān)于設(shè)計掃地機的路徑保證其以最短的時間清掃完該區(qū)域（問題三）的關(guān)鍵在于提高單位長度上清掃垃圾指標的數(shù)量。4.3.1模型：實時掃描折線模型 與傳統(tǒng)的掃地機不同，智能掃地機實時可以通過微處理器進行現(xiàn)場環(huán)境分析，自動選擇運行路線。（1）區(qū)域的劃分 同4.2.1(1）（2）時刻掃描的抽象處理方法 時刻掃描區(qū)域現(xiàn)場，參考點每移動一個單元都要進行實時的監(jiān)控掃描。（3）模型III 的分析與建立優(yōu)化路徑選取 在模型II 中，我們選擇C 最大的路徑作為下一步的清掃路徑。再深一步考慮，我們可以猜想到會有以下幾種情況的發(fā)生。 存在兩個以上的長度相等的路徑同時為C 的最大值所在路徑； 存在兩個以上的長度不等的路徑同時為C 的最大值所在路徑； 存在一個長度較短的路徑( l1)其垃圾總指標為C1、一個長度較長的路徑（l 2 ）其垃圾總指標為C2，而有的條件為了提高清掃的效率，我們選擇單位長度上垃圾指標值最高的路徑。在這里我們引入一個參數(shù)P，稱垃圾指標分布律。根據(jù)我們所建立的模型可以列出公式：（其中mi為直線路徑所經(jīng)過單元的垃圾指標值；N為經(jīng)過區(qū)域的單位總數(shù)） 通過計算每條路徑的值的大小，判斷出最大的值所在路徑的終點，進而得出碰撞后掃地的朝向。計算出每個方向的并進行比較,判斷出最大的方向并選定其為下一次路徑。如題目要求，機器人每次經(jīng)過一個單位，則該方格垃圾指標值減1，即矩陣中的相應(yīng)元素減1。為了控制掃地機工作的結(jié)束，我們認為掃地機在每次與墻壁發(fā)生碰撞的瞬間都會計算此時所有單元垃圾指標值是否都不大于1？直到碰到墻壁后計算出此時所有單元垃圾指標值都不大于 1 時，掃地機自行回到充電站并停止工作。否則再次進行判斷繼續(xù)向下一個值最大的路徑行進。（4） 程序框圖（5） 計算結(jié)果與分析 通過Matlab 對實驗進行可視化演示，得到表3、圖8.5.1 區(qū)域行駛路徑示意和圖8.5.2完成清掃后垃圾分布的結(jié)果。數(shù)據(jù)記錄運行路程/m39.4065運行時間/s157.6260表3 實時掃描折線模型數(shù)據(jù)記錄圖4.3.1 模型優(yōu)化后清掃垃圾路徑示意圖圖4.3.2 模型優(yōu)化后清掃垃圾示意圖 根據(jù)實驗結(jié)果，我們可以知道掃地機完成清潔工作的時間大約為3min，符合實際，認為是正確的。4.4 模型與模型的比較 比較問題1 與問題2，說明問題1 中方案的合理性。數(shù)據(jù)比較分析模型I模型II運行路程/m345.3685194.1670運行時間/s1381.5776.6680從上面的分析可以看出，低端掃地機從性能上來講要比智能掃地機差，但是低端機就必然有其存在的價值。也會有一定的優(yōu)越性。兩者的共性是完成掃地的時間相差不是很懸殊。從試用人群來講低端掃地機相比于智能掃地機在價格上要低很多，大多數(shù)的消費者還是普通的收入水平，因此低端掃地機可以滿足更多人的消費需求，更利于掃地機的普及以及推廣。不同的人對清掃垃圾的指標有不同的要求，低端機綜合以上兩點，會在市場中占有一席之地。從耐用程度來講低端機的掃描以及內(nèi)部的程序相對比較簡單，而智能掃地機為實現(xiàn)其高度的智能化，掃描的過程及其程序要相對比較復(fù)雜。因此，在機器的維護上，低端機要比智能掃地機簡單的多，假設(shè)兩臺機器配備相同的電池，智能掃地機由于要進行相對較頻繁的掃描，以及對內(nèi)部復(fù)雜程序的供電支持，因此智能機的耗電量要大一些，這個道理類似于手機當中的智能機與普通機。綜合以上的分析，我們可以得出一個結(jié)論，低端掃地機的壽命要高于智能機的使用壽命。從開發(fā)編程著想通過對整個區(qū)域進行劃分，即對區(qū)域內(nèi)的單元進行分區(qū)，將多個單元合并成一個小區(qū)域進行考慮大大減少了運算是的數(shù)據(jù)總量，進而縮短運算運行時間，達到提高效率的目的。另外，一方面若是要提高低端掃地機的效用，可以通過優(yōu)化計算出最合理的掃描時間。進而達到縮短清掃時間的效果。五、模型的檢驗我們采取如圖4.1.1所示的區(qū)域分割方式，這樣的分割方式可以保證掃地機在掃垃圾指標值最大的分區(qū)過程中，路徑不覆蓋其他分區(qū)。認為是比較合理， 但是，不可否認這樣的分割區(qū)域方式不是最合理的。通過 Matlab 對實驗進行可視化演示，得到表 1、圖4.1.2 區(qū)域行駛路徑示意和圖4.1.3 完成清掃后垃圾分布的結(jié)果。 根據(jù)實驗結(jié)果，我們可以知道掃地機完成清潔工作的時間大約為23min，符合實際，認為是正確的，模型是正確的。再者又可得到表2、圖4.2.1區(qū)域行駛路徑示意和圖 4.2.2 完成清掃后垃圾分布的結(jié)果。根據(jù)實驗結(jié)果，我們可以知道掃地機完成清潔工作的時間大約為 13min，符合實際，認為是正確的，即模型是合理的。 通過得到的表3、圖4.3.1區(qū)域行駛路徑圖和圖4.3.2完成清掃后垃圾分布的結(jié)果。根據(jù)實驗結(jié)果，我們可以知道掃地機完成清潔工作的時間大約為3min，符合實際，認為是正確的。六、模型的評價在本文中，我們采用了區(qū)域抽象化、柵格和線性規(guī)劃模型求解，并且通過Matlab軟件仿真模型進行驗證，具有以下優(yōu)點： （1）采取區(qū)域抽象化，并采取一定的手段讓問題透明化，使問題變得更簡單，容易理解。 （2） 通過柵格模型，對問題進行具體化，使對問題的分析更明確和清晰。 （3）采用線性規(guī)劃模型，使問題層次更鮮明，有利于問題的解決。 不可否認，模型也存在著如下缺點： （1）掃地機柵格化之后，使得本該掃不到的地方（如墻角）也納入清掃范圍。這樣的后果是使得清掃率的計算存在誤差。但是，由于題設(shè)的要求是盡量保證每個點的垃圾指標不超過1， 我們可以認為誤差是在允許的范圍內(nèi)的 。 （2）計算機器人行進過程中清掃到的區(qū)域時，由于機器人實際上是圓形的，而計算時以方格為單位，有一定的誤差。參考文獻1王仲民，移動機器人路徑規(guī)劃及軌跡跟蹤問題研究，河北工業(yè)大學，2006年3月。2陳恩水、王峰，數(shù)學建模與實驗，科學出版社，2008年6月第一版。3 毛保華.線性規(guī)劃的若干算法研究D.2010.4智能掃地機器人工作原理解析，豆丁網(wǎng)，2014,7.20.附錄：MATLAB源代碼：問題一：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; %轉(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)生邊界枚舉點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; 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 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 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; else J(x,y)=0; end end end end end end else for x=1:251 for y=1:300 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; else J(x,y)=0; end end end end end end end else if b1>=b for x=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 J(x,y)=J(x,y)-1; else J(x,y)=0; end end end end end end else 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 J(x,y)=J(x,y)-1; else J(x,y)=0; end; end; end; end; end; 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; end; %在限定區(qū)域內(nèi)隨機選擇路徑 sumtime=0; if MAX2<MAX1 %判斷是否達標 break; end; MAX2=0;end; Sumtime1 Sumline問題二：Y=C: J=zeros(251,300);for i=1:251 for j=1:100 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 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; 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) 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; 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(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,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) 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 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,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=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; 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) 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; 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)/(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; 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) 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=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); 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 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; 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;