基本信息
- 項目名稱：
- 區(qū)域精準導航系統(tǒng)
- 小類：
- 信息技術(shù)
- 大類：
- 自然科學類學術(shù)論文
- 簡介：
- 針對現(xiàn)有GPS導航系統(tǒng)在區(qū)域內(nèi)部精準導航方面的欠缺，本項目從現(xiàn)實出發(fā)，實現(xiàn)了區(qū)域內(nèi)部任意兩個地點之間的精確導航。同時考慮到區(qū)域內(nèi)存在“路障”、“階梯”等特殊物體，本項目提供了“人行”和“車行”兩種行走模式。除了可以用文字對行走過程加以描述之外，本項目設計了專門的圖形用戶界面，可以更加直觀的顯示出行走的路線以及提供其他輔助功能。
- 詳細介紹：
- 全球定位導航系統(tǒng)（global positioning system）用于陸、海、空三大領域，提供實時、全天候和全球性的導航服務，并用于情報收集、核爆監(jiān)測和應急通訊等一些軍事目的，在特定領域發(fā)揮著中重要的作用。隨著汽車工業(yè)的蓬勃發(fā)展，衛(wèi)星導航定位的應用也日益普及。目前常用的導航系統(tǒng)有美國的GPS，歐洲的伽利略，中國的北斗等。以目前使用最廣泛的GPS導航為例，GPS導航的理論背景是通過把我國的一些常見地理位置標注為“點”，然后把位置與位置之間的路徑定義為“邊”，進而把整個國家抽象為一個很大的“圖”，然后利用圖論中的最短路徑和其他相關(guān)算法就能夠計算出一個地理位置到另外一個地理位置之間的最優(yōu)路徑。這些標注點在GPS導航模塊中被“同等對待”，比如說一個占地幾百平方米的酒店和一個占地幾平方公里的大學都被抽象為圖中的一個點，也就是這些標注點并不能夠反映他們所代表相應地理位置的實際規(guī)模。這樣做的一個后果是，當目的地是一個規(guī)模較小的地理位置時（比如說酒店），GPS能夠順利的導航至目的地。但是當目的地是一個規(guī)模較大的區(qū)域內(nèi)部的某個地理位置時（比如說某個大學的物理樓），此時要到達目的地只能分為“兩步走”。第一步就是借助GPS導航到達將此區(qū)域設置為標注點的那個相應地理位置（比如說大門）；第二步就是通常借助人工咨詢的方式到達目的地，也就是說此時GPS不能直接從出發(fā)點導航至目的地。一個可能的解決方案是將規(guī)模較大的區(qū)域內(nèi)部的所有地理位置都設置為標注點，但是這樣做的后果是標注點的數(shù)據(jù)庫將呈十倍甚至百倍的增加，從而導致計算數(shù)據(jù)庫中任意兩個標注點之間的路徑將花費很長的時間，從而滿足不了導航系統(tǒng)所要求的最基本的“實時性”的要求，這也正是目前導航系統(tǒng)將規(guī)模較大區(qū)域只設置為其外圍的一個或者幾個標注點的原因。因此該方案只具有理論上的可能性，而不具備任何現(xiàn)實意義。 本項目的提出正是為了解決上述“兩步走”中的“第二步”，也就是解決規(guī)模較大區(qū)域內(nèi)部任意兩個位置之間的路徑規(guī)劃問題。同時考慮到區(qū)域內(nèi)部有“路障”和“臺階”等特殊物體的存在，本項目提供了“人行”、“車行”和兩種行走模式，此外還考慮到某些道路可能因為臨時施工而無法通行的情況，本項目還將某些路徑標注為“臨時施工”狀態(tài)。因此從本質(zhì)上可以認為我們的項目為區(qū)域“專有”或者“特定”導航（region-specific navigation）。這樣我們的項目就解決了此區(qū)域內(nèi)的“路徑詢問”這一重大需求問題，比如當區(qū)域為一個大學時，本項目可以解決每年開學期間大量新生和家長的問路咨詢問題；而當此區(qū)域為一個風景區(qū)時，本項目可以解決旅游高峰時期大量游客需要的景點路徑咨詢問題。除了提供最基本的路徑導航之外，為了給區(qū)域內(nèi)部人員提供更多便利，本項目還提供了基本設施的使用查詢，例如學校內(nèi)部自動提款機的位置查詢和手機營業(yè)廳的查詢等。因此本項目具有較強的實用性和推廣性。 在程序具體實現(xiàn)的過程中，首先要確定尋徑算法的正確性以及數(shù)據(jù)錄入的準確性，保證輸出的一定是兩點之間的最優(yōu)路徑；其次要考慮尋徑算法的時間復雜度，以及地名的查找速度，避免給用戶造成過長的等待時間；第三要準確生動，圖文并茂的描繪出路徑信息，避免信息含糊誤導行人；第四要考慮程序的可擴展性和可移植性，盡量使程序能夠較廣泛的應用于相關(guān)領域；最后程序要擁有友好的用戶界面，用戶通過最基本、最簡單的操作，就能獲得導航信息。 從上述需求出發(fā)，本項目基于基本的圖論算法，并輔以幾種數(shù)據(jù)結(jié)構(gòu)的支持，從而實現(xiàn)點對點的精確導航。其中核心算法為Dijkstra算法，用于計算出起始點到圖中所有點的距離，其性能直接與點集的表示方法有關(guān)，為了優(yōu)化尋徑算法，本項目利用優(yōu)先級隊列來改進尋徑算法，在保證準確性的前提下實現(xiàn)圖的高效搜索。在實地考察的過程中，發(fā)現(xiàn)大部分的區(qū)域在抽象以后都是稀疏圖，為了保證算法效率，程序采用鄰接表結(jié)構(gòu)來保存圖中信息。由于程序最終的輸出并非僅僅是數(shù)據(jù)結(jié)構(gòu)的圖中的路徑信息，本文又對算法計算出的路徑信息加以潤色，同時結(jié)合圖中邊的通行屬性（即該邊是否能通車，以及是否正在施工）篩選出最優(yōu)路徑。為了節(jié)約存儲空間，有關(guān)點的所有信息（如點的坐標，點的名稱等）都存儲在同一個數(shù)組之中，目的是便于維護和節(jié)省空間，邊信息也做類似處理，目的相同。程序內(nèi)部各數(shù)據(jù)結(jié)構(gòu)只需相互傳遞點的id號，因為通過id號就可以快速索引到對應該id的點的所有信息，這樣做使得程序內(nèi)部的信息交互更為簡潔。為實現(xiàn)地點名稱到結(jié)點id的快速映射，本項目采用高效哈希算法，將映射操作的時間復雜度控制在O（1），并解決了“一地對多名”的問題。為了準確的描述導航信息，除了提供導航圖之外，本項目還為用戶提供兩點之間的具體行走方法，并且不要求用戶在每次行走時都判斷東、南、西、北地理方位，而是根據(jù)用戶當前的朝向自動確定下一次的轉(zhuǎn)向，并以更易確定的前、后、左、右等邏輯方位來描述具體的轉(zhuǎn)向方位。描述導航文字信息的難點主要在于：點與點之間的地理方向（東南西北）是固定不變的，而其邏輯方向是隨著行人朝向的不同而變化的，程序需要針對行人的朝向，確定下一步的邏輯方向（前后左右）。為了克服這一問題，本文提出了一種解決方案，其機理是利用數(shù)組模擬羅盤，從而模擬行人的行走過程，根據(jù)行人的行走確定下一步的邏輯方位。繪制導航圖的難點在于：不同區(qū)域的數(shù)據(jù)文件所基于的坐標系可能不同，程序應能根據(jù)整張圖的邊界點的橫縱坐標來確定圖像實際顯示的大小，該問題在本項目中已用特定算法解決。為符合軟件工程的基本思想，本項目嚴格按照模塊化程序設計的標準，對程序模塊進行了嚴格的分類。本項目可劃分為計算部分，界面部分，和接口模塊。其中，計算部分又可劃分為四大模塊，其主要功能是實現(xiàn)主要數(shù)據(jù)結(jié)構(gòu)和基本算法，并利用算法獲得準確的導航信息，計算部分和界面部分又以接口模塊連接起來。將計算部分與界面部分分離是為了獲得更好的擴展性，即使是將該項目移植到其它平臺上，也只需重寫界面部分，并將接口稍加修改，而計算部分可以被完全復用，本項目的數(shù)據(jù)文件模塊、圖形顯示模塊之間和接口模塊之間相互獨立，滿足了模型-視圖-控制器設計模式，具有良好的可擴展性，比如說本項目以青島大學為例，可以實現(xiàn)青島大學任意兩個位置之間的路徑規(guī)劃。當數(shù)據(jù)文件模塊更改為海爾工業(yè)園中的相應位置信息時，就可以實現(xiàn)海爾工業(yè)園區(qū)中任意兩個位置之間的導航。在保證程序正確與高效運行的同時，還要盡可能的節(jié)約存儲資源，以便程序可以適應嵌入式工程所需要的苛刻條件。故在本項目中，最要求效率的計算部分采用C語言編寫，而對效率要求較低的界面部分用MFC實現(xiàn)，平衡了程序運行速度和界面的友好性。 為檢測上述功能，本項目基于實際數(shù)據(jù)進行了大量測試，已能夠準確的描述導航信息。對于給定的數(shù)據(jù)文件，程序能準確的將各點位置繪制在導航屏上，并以各邊所具備的不同屬性將邊進行分類，然后以不同的顏色和線條將導航屏上的相應點正確連接起來。根據(jù)本項目中程序所提供的幫助信息，用戶看圖即知各路徑的屬性，以及該區(qū)域中各地點的大致分布，再結(jié)合程序給出的導航信息，便可輕松的獲知到達目的地點的詳細走法。除了實現(xiàn)基本的點對點導航功能之外，本項目也已實現(xiàn)對基礎設施的查找功能，程序能夠根據(jù)用戶當前所在的地點，自動從若干基礎設施中選擇用戶最易到達的一個，同時輸出從當前地點到該基礎設施的導航路徑及詳細走法。其中，查找基礎設施的導航路徑顏色和進行普通導航時不同，目的是讓用戶對當前進行的是何種導航一目了然，所在地點和目的地點被用特殊顏色標注，并被在圖上放大，以便用戶在圖中迅速定位。此外，用戶可以根據(jù)自己的實際需求，選擇進行車行導航或是人行導航，本項目將針對用戶的具體選擇給出合適的導航路線。若用戶已位于目的地點，或是已在想要查找的基礎設施附近，程序?qū)⒔o出正確的提示信息，提醒用戶在原地仔細查找。對于較大的區(qū)域，往往無法將所有點一次全部顯示在導航屏中，用戶可以用鼠標滾輪對地圖進行放縮，也可用鼠標右鍵移動地圖，便于用戶詳細觀察導航圖。本項目中數(shù)據(jù)的錄入較為簡潔，只需逐行向文本文件中添加點、邊信息即可，且基礎設施可以依用戶需求任意指定，且不受數(shù)量限制。
作品圖片
作品專業(yè)信息
撰寫目的和基本思路
- 撰寫目的：填補目前導航系統(tǒng)對較大規(guī)模區(qū)域內(nèi)部的導航精準性的不足，提出可行的解決方案，并編寫軟件，解決規(guī)模較大區(qū)域內(nèi)部任意兩個位置之間的路徑規(guī)劃問題。 基本思路：首先對項目進行需求考察和分析，并按此需求對項目軟件進行設計和規(guī)劃，同時列出項目計劃書的基本框架，嚴格按照模塊化程序設計要求編寫各軟件各模塊，在此過程中逐步完善項目計劃書。
科學性、先進性及獨特之處
- 本項目的理論依據(jù)是經(jīng)典的圖論算法，該算法確保了項目中尋徑的準確性。在準確的基礎中，本項目豐富了圖中邊的屬性，可以針對人行，車行，以及臨時道路施工三種情況給出最可行的導航路徑。此外，本項目還具有較好的可擴展性，對效率要求較高的核心算法和數(shù)據(jù)結(jié)構(gòu)部分采用C語言編寫，對用戶友好性要求較高的界面部分采用MFC編寫，核心部分和界面部分又以接口連接?？梢暂^方便的移植到其他設備上，具有較好的可擴展性。
應用價值和現(xiàn)實意義
- 本項目解決了規(guī)模較大區(qū)域內(nèi)部任意兩個位置之間的路徑規(guī)劃問題。同事考慮到區(qū)域內(nèi)部有“路障”和“臺階”等特殊物體的存在，本項目提供了“人行”和車型兩種行走模式，此外還考慮到某些道路可能因為臨時施工而無法通行的情況，本項目還將某些路徑標注為“臨時施工”狀態(tài)。這樣就解決了區(qū)域內(nèi)部的“路徑詢問”這一需求問題。此外，由于本項目采用模塊化程序設計，可以較方便的移植到其它平臺，可擴展性較好。
學術(shù)論文摘要
- 針對現(xiàn)有GPS導航系統(tǒng)在區(qū)域內(nèi)部精準導航方面的欠缺，本項目從現(xiàn)實出發(fā)，實現(xiàn)了區(qū)域內(nèi)部任意兩個地點之間的精確導航。整個區(qū)域被抽象為一個圖的數(shù)據(jù)結(jié)構(gòu)，區(qū)域內(nèi)的每個地點表示為圖中的一個頂點，而任意兩個地點之間的路徑以圖中所對應點的有向邊來表示。選擇區(qū)域內(nèi)部的任意兩點，利用改進的Dijkstra算法就可以計算出它們之間的最優(yōu)路徑。同時考慮到區(qū)域內(nèi)存在“路障”、“階梯”等特殊物體，本項目提供了“人行”和“車行”兩種行走模式。除了可以用文字對行走過程加以描述之外，本項目設計了專門的圖形用戶界面，可以更加直觀的顯示出行走的路線以及提供其他輔助功能。本項目的數(shù)據(jù)文件模塊、圖形顯示模塊之間和操作接口模塊之間相互獨立，滿足了模型-視圖-控制器設計模式，具有良好的可擴展性。
獲獎情況
- 無
鑒定結(jié)果
- 無
參考文獻
- 1、Ellis Horowitz,Sartaj Sahni,Susan Anderson-Freed著,朱仲濤 譯 數(shù)據(jù)結(jié)構(gòu)基礎（C語言版）（第二版）北京：清華大學出版社 2009 2、K.N.King著 呂秀鋒 黃倩 譯 C語言程序設計：現(xiàn)代方法（第二版） 北京：人民郵電出版社，2010 3、王曉東 編著 計算機算法設計與分析（第三版） 北京：電子工業(yè)出版社 2010 4、Thomas H. Cormen ,Charles E. Leiserson Ronald L. Rivest,Clifford Stein, Introduction to Algorithms(Third Edition),2009 5、Shimon Even.Graph Algorithms.Computer Science Press,1979
同類課題研究水平概述
- 全球定位導航系統(tǒng)（global positioning system）用于陸、海、空三大領域，提供實時、全天候和全球性的導航服務，并用于情報收集、核爆監(jiān)測和應急通訊等一些軍事目的，在特定領域發(fā)揮著中重要的作用。隨著汽車工業(yè)的蓬勃發(fā)展，衛(wèi)星導航定位的應用也日益普及。目前常用的導航系統(tǒng)有美國的GPS，歐洲的伽利略，中國的北斗等。以目前使用最廣泛的GPS導航為例，GPS導航的理論背景是通過把我國的一些常見地理位置標注為“點”，然后把位置與位置之間的路徑定義為“邊”，進而把整個國家抽象為一個很大的“圖”，然后利用圖論中的最短路徑和其他相關(guān)算法就能夠計算出一個地理位置到另外一個地理位置之間的最優(yōu)路徑。這些標注點在GPS導航模塊中被“同等對待”，比如說一個占地幾百平方米的酒店和一個占地幾平方公里的大學都被抽象為圖中的一個點，也就是這些標注點并不能夠反映他們所代表相應地理位置的實際規(guī)模。這樣做的一個后果是，當目的地是一個規(guī)模較小的地理位置時（比如說酒店），GPS能夠順利的導航至目的地。但是當目的地是一個規(guī)模較大的區(qū)域內(nèi)部的某個地理位置時（比如說某個大學的物理樓），此時要到達目的地只能分為“兩步走”。第一步就是借助GPS導航到達將此區(qū)域設置為標注點的那個相應地理位置（比如說大門）；第二步就是通常借助人工咨詢的方式到達目的地，也就是說此時GPS不能直接從出發(fā)點導航至目的地。一個可能的解決方案是將規(guī)模較大的區(qū)域內(nèi)部的所有地理位置都設置為標注點，但是這樣做的后果是標注點的數(shù)據(jù)庫將呈十倍甚至百倍的增加，從而導致計算數(shù)據(jù)庫中任意兩個標注點之間的路徑將花費很長的時間，從而滿足不了導航系統(tǒng)所要求的最基本的“實時性”的要求，這也正是目前導航系統(tǒng)將規(guī)模較大區(qū)域只設置為其外圍的一個或者幾個標注點的原因。因此該方案只具有理論上的可能性，而不具備任何現(xiàn)實意義。
