基本信息
- 项目名称：
- 区域精准导航系统
- 来源：
- 第十二届“挑战杯”省赛作品
- 小类：
- 信息技术
- 大类：
- 自然科学类学术论文
- 简介：
- 针对现有GPS导航系统在区域内部精准导航方面的欠缺，本项目从现实出发，实现了区域内部任意两个地点之间的精确导航。同时考虑到区域内存在“路障”、“阶梯”等特殊物体，本项目提供了“人行”和“车行”两种行走模式。除了可以用文字对行走过程加以描述之外，本项目设计了专门的图形用户界面，可以更加直观的显示出行走的路线以及提供其他辅助功能。
- 详细介绍：
- 全球定位导航系统（global positioning system）用于陆、海、空三大领域，提供实时、全天候和全球性的导航服务，并用于情报收集、核爆监测和应急通讯等一些军事目的，在特定领域发挥着中重要的作用。随着汽车工业的蓬勃发展，卫星导航定位的应用也日益普及。目前常用的导航系统有美国的GPS，欧洲的伽利略，中国的北斗等。以目前使用最广泛的GPS导航为例，GPS导航的理论背景是通过把我国的一些常见地理位置标注为“点”，然后把位置与位置之间的路径定义为“边”，进而把整个国家抽象为一个很大的“图”，然后利用图论中的最短路径和其他相关算法就能够计算出一个地理位置到另外一个地理位置之间的最优路径。这些标注点在GPS导航模块中被“同等对待”，比如说一个占地几百平方米的酒店和一个占地几平方公里的大学都被抽象为图中的一个点，也就是这些标注点并不能够反映他们所代表相应地理位置的实际规模。这样做的一个后果是，当目的地是一个规模较小的地理位置时（比如说酒店），GPS能够顺利的导航至目的地。但是当目的地是一个规模较大的区域内部的某个地理位置时（比如说某个大学的物理楼），此时要到达目的地只能分为“两步走”。第一步就是借助GPS导航到达将此区域设置为标注点的那个相应地理位置（比如说大门）；第二步就是通常借助人工咨询的方式到达目的地，也就是说此时GPS不能直接从出发点导航至目的地。一个可能的解决方案是将规模较大的区域内部的所有地理位置都设置为标注点，但是这样做的后果是标注点的数据库将呈十倍甚至百倍的增加，从而导致计算数据库中任意两个标注点之间的路径将花费很长的时间，从而满足不了导航系统所要求的最基本的“实时性”的要求，这也正是目前导航系统将规模较大区域只设置为其外围的一个或者几个标注点的原因。因此该方案只具有理论上的可能性，而不具备任何现实意义。 本项目的提出正是为了解决上述“两步走”中的“第二步”，也就是解决规模较大区域内部任意两个位置之间的路径规划问题。同时考虑到区域内部有“路障”和“台阶”等特殊物体的存在，本项目提供了“人行”、“车行”和两种行走模式，此外还考虑到某些道路可能因为临时施工而无法通行的情况，本项目还将某些路径标注为“临时施工”状态。因此从本质上可以认为我们的项目为区域“专有”或者“特定”导航（region-specific navigation）。这样我们的项目就解决了此区域内的“路径询问”这一重大需求问题，比如当区域为一个大学时，本项目可以解决每年开学期间大量新生和家长的问路咨询问题；而当此区域为一个风景区时，本项目可以解决旅游高峰时期大量游客需要的景点路径咨询问题。除了提供最基本的路径导航之外，为了给区域内部人员提供更多便利，本项目还提供了基本设施的使用查询，例如学校内部自动提款机的位置查询和手机营业厅的查询等。因此本项目具有较强的实用性和推广性。 在程序具体实现的过程中，首先要确定寻径算法的正确性以及数据录入的准确性，保证输出的一定是两点之间的最优路径；其次要考虑寻径算法的时间复杂度，以及地名的查找速度，避免给用户造成过长的等待时间；第三要准确生动，图文并茂的描绘出路径信息，避免信息含糊误导行人；第四要考虑程序的可扩展性和可移植性，尽量使程序能够较广泛的应用于相关领域；最后程序要拥有友好的用户界面，用户通过最基本、最简单的操作，就能获得导航信息。 从上述需求出发，本项目基于基本的图论算法，并辅以几种数据结构的支持，从而实现点对点的精确导航。其中核心算法为Dijkstra算法，用于计算出起始点到图中所有点的距离，其性能直接与点集的表示方法有关，为了优化寻径算法，本项目利用优先级队列来改进寻径算法，在保证准确性的前提下实现图的高效搜索。在实地考察的过程中，发现大部分的区域在抽象以后都是稀疏图，为了保证算法效率，程序采用邻接表结构来保存图中信息。由于程序最终的输出并非仅仅是数据结构的图中的路径信息，本文又对算法计算出的路径信息加以润色，同时结合图中边的通行属性（即该边是否能通车，以及是否正在施工）筛选出最优路径。为了节约存储空间，有关点的所有信息（如点的坐标，点的名称等）都存储在同一个数组之中，目的是便于维护和节省空间，边信息也做类似处理，目的相同。程序内部各数据结构只需相互传递点的id号，因为通过id号就可以快速索引到对应该id的点的所有信息，这样做使得程序内部的信息交互更为简洁。为实现地点名称到结点id的快速映射，本项目采用高效哈希算法，将映射操作的时间复杂度控制在O（1），并解决了“一地对多名”的问题。为了准确的描述导航信息，除了提供导航图之外，本项目还为用户提供两点之间的具体行走方法，并且不要求用户在每次行走时都判断东、南、西、北地理方位，而是根据用户当前的朝向自动确定下一次的转向，并以更易确定的前、后、左、右等逻辑方位来描述具体的转向方位。描述导航文字信息的难点主要在于：点与点之间的地理方向（东南西北）是固定不变的，而其逻辑方向是随着行人朝向的不同而变化的，程序需要针对行人的朝向，确定下一步的逻辑方向（前后左右）。为了克服这一问题，本文提出了一种解决方案，其机理是利用数组模拟罗盘，从而模拟行人的行走过程，根据行人的行走确定下一步的逻辑方位。绘制导航图的难点在于：不同区域的数据文件所基于的坐标系可能不同，程序应能根据整张图的边界点的横纵坐标来确定图像实际显示的大小，该问题在本项目中已用特定算法解决。为符合软件工程的基本思想，本项目严格按照模块化程序设计的标准，对程序模块进行了严格的分类。本项目可划分为计算部分，界面部分，和接口模块。其中，计算部分又可划分为四大模块，其主要功能是实现主要数据结构和基本算法，并利用算法获得准确的导航信息，计算部分和界面部分又以接口模块连接起来。将计算部分与界面部分分离是为了获得更好的扩展性，即使是将该项目移植到其它平台上，也只需重写界面部分，并将接口稍加修改，而计算部分可以被完全复用，本项目的数据文件模块、图形显示模块之间和接口模块之间相互独立，满足了模型-视图-控制器设计模式，具有良好的可扩展性，比如说本项目以青岛大学为例，可以实现青岛大学任意两个位置之间的路径规划。当数据文件模块更改为海尔工业园中的相应位置信息时，就可以实现海尔工业园区中任意两个位置之间的导航。在保证程序正确与高效运行的同时，还要尽可能的节约存储资源，以便程序可以适应嵌入式工程所需要的苛刻条件。故在本项目中，最要求效率的计算部分采用C语言编写，而对效率要求较低的界面部分用MFC实现，平衡了程序运行速度和界面的友好性。 为检测上述功能，本项目基于实际数据进行了大量测试，已能够准确的描述导航信息。对于给定的数据文件，程序能准确的将各点位置绘制在导航屏上，并以各边所具备的不同属性将边进行分类，然后以不同的颜色和线条将导航屏上的相应点正确连接起来。根据本项目中程序所提供的帮助信息，用户看图即知各路径的属性，以及该区域中各地点的大致分布，再结合程序给出的导航信息，便可轻松的获知到达目的地点的详细走法。除了实现基本的点对点导航功能之外，本项目也已实现对基础设施的查找功能，程序能够根据用户当前所在的地点，自动从若干基础设施中选择用户最易到达的一个，同时输出从当前地点到该基础设施的导航路径及详细走法。其中，查找基础设施的导航路径颜色和进行普通导航时不同，目的是让用户对当前进行的是何种导航一目了然，所在地点和目的地点被用特殊颜色标注，并被在图上放大，以便用户在图中迅速定位。此外，用户可以根据自己的实际需求，选择进行车行导航或是人行导航，本项目将针对用户的具体选择给出合适的导航路线。若用户已位于目的地点，或是已在想要查找的基础设施附近，程序将给出正确的提示信息，提醒用户在原地仔细查找。对于较大的区域，往往无法将所有点一次全部显示在导航屏中，用户可以用鼠标滚轮对地图进行放缩，也可用鼠标右键移动地图，便于用户详细观察导航图。本项目中数据的录入较为简洁，只需逐行向文本文件中添加点、边信息即可，且基础设施可以依用户需求任意指定，且不受数量限制。
作品图片
作品专业信息
撰写目的和基本思路
- 撰写目的：填补目前导航系统对较大规模区域内部的导航精准性的不足，提出可行的解决方案，并编写软件，解决规模较大区域内部任意两个位置之间的路径规划问题。 基本思路：首先对项目进行需求考察和分析，并按此需求对项目软件进行设计和规划，同时列出项目计划书的基本框架，严格按照模块化程序设计要求编写各软件各模块，在此过程中逐步完善项目计划书。
科学性、先进性及独特之处
- 本项目的理论依据是经典的图论算法，该算法确保了项目中寻径的准确性。在准确的基础中，本项目丰富了图中边的属性，可以针对人行，车行，以及临时道路施工三种情况给出最可行的导航路径。此外，本项目还具有较好的可扩展性，对效率要求较高的核心算法和数据结构部分采用C语言编写，对用户友好性要求较高的界面部分采用MFC编写，核心部分和界面部分又以接口连接。可以较方便的移植到其他设备上，具有较好的可扩展性。
应用价值和现实意义
- 本项目解决了规模较大区域内部任意两个位置之间的路径规划问题。同事考虑到区域内部有“路障”和“台阶”等特殊物体的存在，本项目提供了“人行”和车型两种行走模式，此外还考虑到某些道路可能因为临时施工而无法通行的情况，本项目还将某些路径标注为“临时施工”状态。这样就解决了区域内部的“路径询问”这一需求问题。此外，由于本项目采用模块化程序设计，可以较方便的移植到其它平台，可扩展性较好。
学术论文摘要
- 针对现有GPS导航系统在区域内部精准导航方面的欠缺，本项目从现实出发，实现了区域内部任意两个地点之间的精确导航。整个区域被抽象为一个图的数据结构，区域内的每个地点表示为图中的一个顶点，而任意两个地点之间的路径以图中所对应点的有向边来表示。选择区域内部的任意两点，利用改进的Dijkstra算法就可以计算出它们之间的最优路径。同时考虑到区域内存在“路障”、“阶梯”等特殊物体，本项目提供了“人行”和“车行”两种行走模式。除了可以用文字对行走过程加以描述之外，本项目设计了专门的图形用户界面，可以更加直观的显示出行走的路线以及提供其他辅助功能。本项目的数据文件模块、图形显示模块之间和操作接口模块之间相互独立，满足了模型-视图-控制器设计模式，具有良好的可扩展性。
获奖情况
- 无
鉴定结果
- 无
参考文献
- 1、Ellis Horowitz,Sartaj Sahni,Susan Anderson-Freed著,朱仲涛 译 数据结构基础（C语言版）（第二版）北京：清华大学出版社 2009 2、K.N.King著 吕秀锋 黄倩 译 C语言程序设计：现代方法（第二版） 北京：人民邮电出版社，2010 3、王晓东 编著 计算机算法设计与分析（第三版） 北京：电子工业出版社 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
同类课题研究水平概述
- 全球定位导航系统（global positioning system）用于陆、海、空三大领域，提供实时、全天候和全球性的导航服务，并用于情报收集、核爆监测和应急通讯等一些军事目的，在特定领域发挥着中重要的作用。随着汽车工业的蓬勃发展，卫星导航定位的应用也日益普及。目前常用的导航系统有美国的GPS，欧洲的伽利略，中国的北斗等。以目前使用最广泛的GPS导航为例，GPS导航的理论背景是通过把我国的一些常见地理位置标注为“点”，然后把位置与位置之间的路径定义为“边”，进而把整个国家抽象为一个很大的“图”，然后利用图论中的最短路径和其他相关算法就能够计算出一个地理位置到另外一个地理位置之间的最优路径。这些标注点在GPS导航模块中被“同等对待”，比如说一个占地几百平方米的酒店和一个占地几平方公里的大学都被抽象为图中的一个点，也就是这些标注点并不能够反映他们所代表相应地理位置的实际规模。这样做的一个后果是，当目的地是一个规模较小的地理位置时（比如说酒店），GPS能够顺利的导航至目的地。但是当目的地是一个规模较大的区域内部的某个地理位置时（比如说某个大学的物理楼），此时要到达目的地只能分为“两步走”。第一步就是借助GPS导航到达将此区域设置为标注点的那个相应地理位置（比如说大门）；第二步就是通常借助人工咨询的方式到达目的地，也就是说此时GPS不能直接从出发点导航至目的地。一个可能的解决方案是将规模较大的区域内部的所有地理位置都设置为标注点，但是这样做的后果是标注点的数据库将呈十倍甚至百倍的增加，从而导致计算数据库中任意两个标注点之间的路径将花费很长的时间，从而满足不了导航系统所要求的最基本的“实时性”的要求，这也正是目前导航系统将规模较大区域只设置为其外围的一个或者几个标注点的原因。因此该方案只具有理论上的可能性，而不具备任何现实意义。
