數(shù)學(xué)建模機(jī)器人避障論文

.z承諾書我們仔細(xì)閱讀了中國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽的競(jìng)賽規(guī)則.我們完全明白，在競(jìng)賽開場(chǎng)后參賽隊(duì)員不能以任何方式〔包括、電子、網(wǎng)上咨詢等〕與隊(duì)外的任何人〔包括指導(dǎo)教師〕研究、討論與賽題有關(guān)的問題。我們知道，抄襲別人的成果是違反競(jìng)賽規(guī)則的,如果引用別人的成果或其他公開的資料〔包括網(wǎng)上查到的資料〕，必須按照規(guī)定的參考文獻(xiàn)的表述方式在正文引用處和參考文獻(xiàn)中明確列出。我們*重承諾，嚴(yán)格遵守競(jìng)賽規(guī)則，以保證競(jìng)賽的公正、公平性。如有違反競(jìng)賽規(guī)則的行為，我們將受到嚴(yán)肅處理。我們參賽選擇的題號(hào)是〔從A/B/C/D中選擇一項(xiàng)填寫〕： 我們的參賽報(bào)名號(hào)為〔如果賽區(qū)設(shè)置報(bào)名號(hào)的話〕：所屬學(xué)?！舱?qǐng)?zhí)顚懲暾娜常簠①愱?duì)員(打印并簽名)：1.2.3.指導(dǎo)教師或指導(dǎo)教師組負(fù)責(zé)人(打印并簽名)：日期：年月日編號(hào)專用頁賽區(qū)評(píng)閱編號(hào)〔由賽區(qū)組委會(huì)評(píng)閱前進(jìn)展編號(hào)〕：賽區(qū)評(píng)閱記錄〔可供賽區(qū)評(píng)閱時(shí)使用〕：評(píng)閱人評(píng)分備注全國(guó)統(tǒng)一編號(hào)〔由賽區(qū)組委會(huì)送交全國(guó)前編號(hào)〕：全國(guó)評(píng)閱編號(hào)〔由全國(guó)組委會(huì)評(píng)閱前進(jìn)展編號(hào)〕：機(jī)器人避障問題摘要針對(duì)題中機(jī)器人避障最短路徑問題，文章使用簡(jiǎn)化后建立的最短路徑的數(shù)學(xué)模型來解決此類問題。對(duì)于問題1，我們matlab中自帶函數(shù)graphshortestpath函數(shù)求解最短路徑的數(shù)學(xué)模型。其主要思想是：首先先證明出兩點(diǎn)之間的最短路徑是由兩條線段和以中間點(diǎn)為圓心的圓的一段圓弧組成，然后證明圓弧的半徑為定值10。然后對(duì)模型簡(jiǎn)化使模型化為標(biāo)準(zhǔn)的最短路徑模型，最后用graphshortestpath函數(shù)對(duì)模型求解。針對(duì)問題2，我們建立了優(yōu)化模型。在問題1的根底上，我們對(duì)兩種行走方案進(jìn)展分析，根據(jù)轉(zhuǎn)彎弧的半徑變化對(duì)速度的影響我們鎖定到一條路徑，然后利用lingo對(duì)優(yōu)化模型進(jìn)展求解。關(guān)鍵詞：graphshortestpath函數(shù)、最短路徑、避障問題1、問題重述：在以下圖中原點(diǎn)O(0,0)點(diǎn)處有一個(gè)機(jī)器人，它只能在該平面場(chǎng)景*圍內(nèi)活動(dòng)。圖中有12個(gè)區(qū)域是機(jī)器人不能與之發(fā)生碰撞的障礙物。在機(jī)器人的行走中，要求機(jī)器人行走路徑只能是以下兩種：由與直線路徑相切的一段圓弧組成、由兩個(gè)或多個(gè)相切的圓弧路徑組成。不能沿著折線轉(zhuǎn)彎。轉(zhuǎn)彎的圓弧半徑最小為10個(gè)單位，并且機(jī)器人與障礙物至少距離10個(gè)單位。在速度方面，機(jī)器人直線行走的最大速度為個(gè)單位/秒。機(jī)器人轉(zhuǎn)彎的最大轉(zhuǎn)彎速度為，其中是轉(zhuǎn)彎半徑。問題1：求機(jī)器人從O(0,0)出發(fā)，O→A、O→B、O→C和O→A→B→C→O的最短路徑。問題2：求機(jī)器人從O(0,0)出發(fā)，到達(dá)A的最短時(shí)間路徑。2、模型假設(shè)假設(shè)機(jī)器人抽象成點(diǎn)來分析假設(shè)機(jī)器人在改變路徑時(shí)能在瞬間將速度調(diào)整過來3、符號(hào)說明 符號(hào)符號(hào)說明TθLVR機(jī)器人到達(dá)目的地所用的時(shí)間轉(zhuǎn)彎角度轉(zhuǎn)彎的弧長(zhǎng)轉(zhuǎn)彎速度直線行走最大速度轉(zhuǎn)彎圓弧的半徑4、模型的建立與求解4.1首先證明以下猜想：兩點(diǎn)之間假設(shè)間隔有障礙物，兩點(diǎn)之間的最短路徑是由兩局部組成。第一局部是自然最短直線段，第二局部是限定局部的邊界弧。這兩局部是相切并且互相連接的。證明：如圖A,B兩點(diǎn)，它們之間有一個(gè)半徑為1的半圓形障礙物。現(xiàn)在要求出A到B的最短路徑。分析1：兩點(diǎn)之間的最短路徑應(yīng)是連接兩點(diǎn)的線段，但是由于障礙物的存在，現(xiàn)在改為繞過障礙物的折線〔用于證明方便〕，設(shè)動(dòng)點(diǎn)C點(diǎn)坐標(biāo)設(shè)為〔0，y〕，折線ACB的長(zhǎng)度為，當(dāng)c點(diǎn)豎直向下移動(dòng)時(shí)，折線ACB的長(zhǎng)度會(huì)減小，當(dāng)C點(diǎn)移動(dòng)到C1〔0，y1〕點(diǎn)時(shí)ACB的長(zhǎng)度最小，最小長(zhǎng)度為。其中C1是過點(diǎn)A,B與圓弧相切的切線交點(diǎn)。又由于滿足0<α<的角滿足α<tanα，所以弧度EF小于EF的長(zhǎng)。記線段AE，弧度EF，線段FB這樣的路徑為AEFB，則從A到B繞過障礙物的最短路徑為AEFB。分析2：當(dāng)考慮從A到B的路徑全為圓弧線段組成時(shí)，如圖A到B的弧線。假設(shè)a=2，則這段弧線所對(duì)應(yīng)的圓為經(jīng)過A(-2，0)，B(2，0)，(0，1)三點(diǎn)的圓的一局部。此圓的一般方程為：，則這段圓弧路徑的長(zhǎng)度為2π。假設(shè)用分析1中的折線與弧線相交并相切的方法計(jì)算，路徑長(zhǎng)度為≈4.51小于圓弧方案的長(zhǎng)度。綜上所述，方案AEFB滿足題中最短路徑的要求。4.2切線和弧線的公式推導(dǎo)如圖，在4.1的根底上用解析幾何方法計(jì)算出兩條切線和一段圓弧的長(zhǎng)度。假設(shè)起點(diǎn)終點(diǎn)為A〔*1，y1〕和C〔*3，y3〕，障礙物的頂點(diǎn)為B(*2，y2〕，D,E為兩條線段與圓弧的切點(diǎn)，圓弧的半徑為10個(gè)單位?，F(xiàn)在求解線段AD，CE及圓弧DE的長(zhǎng)度。因?yàn)槿切蜛BD和CBE是直角三角形，我們可以利用余弦函數(shù)來解出∠DBA和∠EBC。COS∠DBA==，①COS∠EBC==，②然后再利用余弦定理在三角形ABC中找出與∠ABC有關(guān)系的等式，COS∠ABC=，③由①②③三式再根據(jù)周角為2π可以解出角DBE的弧度數(shù)，由于后面編程需要，需要將弧度數(shù)轉(zhuǎn)化成角度數(shù)，利用公式，然后再利用公式求得弧DE的長(zhǎng)度。而對(duì)于線段AD,CE，我們可以直接根據(jù)勾股定理可以求得具體長(zhǎng)度。程序見1。4.3模型簡(jiǎn)化模型的中心思想是利用Dijkstra算法來求解出最短路徑的方案，由于兩點(diǎn)間路徑是由線段和弧線組成的，為了化為標(biāo)準(zhǔn)的最短路徑模型，需要將模型進(jìn)展簡(jiǎn)化。在這里以4.2的模型根底上進(jìn)展示*。首先令A(yù),B,C分別為起點(diǎn)、中間點(diǎn)、末點(diǎn)。我們將路線ADEC分成兩個(gè)局部，第一局部是線段AD和弧線DE組成的，第二局部是線段EC。又由于弧線的長(zhǎng)度會(huì)隨著末點(diǎn)的變化而變化，所以我們?nèi)』【€的平均值作為弧線DE的長(zhǎng)度。第一局部表示起點(diǎn)到中間點(diǎn)的距離。在此題中主要不是如4.2中的簡(jiǎn)單模型?，F(xiàn)在以以下圖模型進(jìn)展進(jìn)一步說明。此模型涉及到兩個(gè)障礙物，根據(jù)以上簡(jiǎn)化思想，A到H的最短路徑應(yīng)該是簡(jiǎn)化為三局部。第一局部為線段AD與弧線〔弧線DE的平均值〕，表示A到B的距離。易知線段EC和線段BF的長(zhǎng)度是相等的，第二局部為線段BF與弧線，表示B到C的距離。第三局部為線段GH，表示路徑的最后一段距離，如果目標(biāo)點(diǎn)不是H，則下一局部應(yīng)是線段CH加上下一段圓弧，以此類推。此算法命名為算法1。根據(jù)以上的算法1的簡(jiǎn)化，我們將此題中的機(jī)器人避障最短路徑模型簡(jiǎn)化為標(biāo)準(zhǔn)最短路徑模型，并且對(duì)可能會(huì)用到的點(diǎn)加以編號(hào)，得到如以下圖。4.4模型的求解對(duì)于問題1：根據(jù)簡(jiǎn)化使用的算法1，對(duì)機(jī)器人所有可行走的路徑利用4.2推導(dǎo)的公式用matlab進(jìn)展計(jì)算，程序見1，得到所有以三點(diǎn)為一組的各個(gè)路徑的長(zhǎng)度，主要有線段1，圓弧，線段2。具體結(jié)果見2。因?yàn)橹虚g點(diǎn)到末點(diǎn)具有多條路徑，即有不同的圓弧長(zhǎng)，所以對(duì)同一中間點(diǎn)所對(duì)應(yīng)的所有圓弧長(zhǎng)求平均值，將模型簡(jiǎn)化為最短路徑模型，就能得出鄰接矩陣，鄰接矩陣見3。最后利用matlab自帶函數(shù)graphshortestpath和鄰接矩陣對(duì)模型求解得到最短路徑。程序見4。運(yùn)行結(jié)果為：〔用編號(hào)表示〕O—A：35—1—30O—B：35—2—3—4—5—6—31O—C：35—24—22—20—17—15—32O--A--B--C--O：35—1—30—5—6—31—9—10—11—12—32—15—17—20—22—24—35具體的路徑見以下圖：對(duì)于問題2：?jiǎn)栴}2需要求出行走時(shí)間最短的路徑，從圖中易知從O到A的路線有兩條，一條是35—1—30方案，簡(jiǎn)稱方案1。另一條是35—24—30方案，簡(jiǎn)稱方案2。由問題1解決結(jié)果知，方案1比方案2的路徑要短，又由計(jì)算知，在增加圓的半徑的情況下，對(duì)于長(zhǎng)度較長(zhǎng)的方案2所用時(shí)間也相應(yīng)較多。所以，對(duì)問題2的討論中，我們?cè)趩栴}1結(jié)果的根底上研究方案1中圓弧變化對(duì)時(shí)間的影響。對(duì)于最短時(shí)間模型，我們使用了最優(yōu)化模型。由于半徑會(huì)影響機(jī)器人在轉(zhuǎn)彎弧上的速度，當(dāng)半徑增大時(shí)，機(jī)器人在轉(zhuǎn)彎弧上的速度也會(huì)增大，此時(shí)機(jī)器人所走的直線段會(huì)變短，而時(shí)間=，我們要求最短時(shí)間，就要使+最小。其中：第一條直線段長(zhǎng)度為；第二條直線段長(zhǎng)度為；轉(zhuǎn)彎弧所對(duì)的圓心角為：；轉(zhuǎn)彎弧長(zhǎng)為：；轉(zhuǎn)彎速度為：模型的數(shù)學(xué)表達(dá)式如下：S.T.=然后利用lingo軟件，對(duì)模型進(jìn)展求解，其lingo程序見5。運(yùn)算結(jié)果為：轉(zhuǎn)彎弧半徑R=11.50350弧長(zhǎng)L=10.52502轉(zhuǎn)彎速度V=4.810298所用時(shí)間T=94.55726即，用時(shí)最少的路徑為從O出發(fā)，沿切線到達(dá)在以5號(hào)正方形左上角為圓心，以11.5035為半徑的圓上，再沿另一條切線到達(dá)A點(diǎn)。5、模型結(jié)果的分析與檢驗(yàn)本文模型中的檢驗(yàn)主要是針對(duì)題中給出的機(jī)器人與障礙物之間保持10個(gè)單位的距離這一要求，在所得到的路徑中，可能存在著*直線段與*障礙物的間隔距離小于10個(gè)單位，所以在得到運(yùn)算結(jié)果的前提上，從中找到以下需要檢驗(yàn)的檢驗(yàn)點(diǎn)：27號(hào)〔對(duì)應(yīng)1—30路徑〕、7號(hào)〔對(duì)應(yīng)31—9路徑〕、1