Abstract
In modern society，Outdoor road perplexing，Inside the building is also changing。when one of us is away，We are more and more cannot do without the help of a navigation system In a strange or familiar place. The outdoor navigation system has been quite mature, But the indoor navigation system not been applied for the study of indoor navigation, The key point is that modeling and indoor navigation algorithm for indoor positioning, Until now, the indoor positioning has not been able to use the mature scheme; The indoor map does not form a unified standard; At the same time indoor navigation algorithms need to be designed for a particular situation, These are worthy of further investigation and verification of the part. Aiming at the above problem, we put forward a kind of path planning algorithm in space, and the path planning system from the map building algorithm optimization and Implementation.
Aiming at the problem in path planning，In this paper, the space structure of the minimum unit location in the room is simulated by the simplified room profile diagram. Using Delaunay triangulation to determine the path points outside the room, the special adjacency table storage map is designed, which provides the data for the algorithm. On this basis, using A* algorithm as the basic algorithm of indoor path planning; According to the speed of convergence of nodes and different functions, the H (n)
is determined, and the value function of the target node is h (n) when the distance is small. The data structure and storage of the OPEN and CLOSED table are optimized and the algorithm efficiency is improved. At the same time, according to the principle of the outdoor highway network, this paper presents a multi story path planning algorithm, and analyzes its algorithm. With the premise of the full connection between floors, the algorithm can plan the route of the starting point to the destination more efficiently.
Finally, taking the laboratory project as an example, the practical application of the path planning algorithm is carried out. The path planning of indoor and multi - layered indoor is preliminarily realized. The empirical results show that the optimization path planning algorithm is real and feasible.
Keywords：Indoor path planning；Indoor map；triangulation；A* algorithm
目录
摘要................................................................................................................. .II 1 绪论
1.3 本文的组织结构 (4)
2 室内导航关键技术研究
2.1 室内定位 (6)
2.2 室内地图建模 (9)
3 室内导航的地图与算法设计
3.1 室内地图的构建和存储 (18)
3.2 基于单层空间的算法优化 (25)
3.3 基于多层空间的算法优化 (32)
3.4 总结 (37)
4 室内路径规划的实现
1.4 路径规划的相关网络接口 (38)
1.5 路径规划的客户端实现 (39)
1.6 路径规划的服务器实现 (42)
1.7 路径规划结果分析 (47)
5 结论与展望
2.4 结论 (49)
2.5 工作展望 (49)
致谢 (51)
参考文献 (52)
1 绪论
1.8研究背景与意义
现代社会中，户外路况错综复杂，建筑的内部情况也不断变化。出门在外，来到一个陌生或熟悉的地方，我们越来越离不开导航系统的帮助。传统意义上的导航通常是通过实际地图和网络查询进行，信息的爆炸凸显出传统导航方式的低效率。有效的导航可以是一种高效的信息查询和传递，可极大的提升个人的办事效率，有效提高社会生产力。
现存的导航系统主要为室外导航系统[1]和室内导航系统。室外导航系统已经相当成熟，如室外车载的导航系统凯立德、高德地图，万利达导航地图等等[2]。以上的导航方式广泛的采用了以基于全球定位系统（GPS）[3]的导航，有的同时在蜂窝无线网络可以覆盖到的地方辅助以蜂窝无线定位（Celluar wireless location）[4]。GPS 定位系统是美国从 20 世纪70 年代开始，由美国三军研制的军用定位系统，在几十年的发展之后转向民用开放。它的定位的原理，是根据已知的用户到卫星之间的距离，运用三边的测量方法获得用户与卫星之间的距离。GPS 的定位精度在室外民用可以达到 5m。蜂窝无线定位系统分为基于网络的定位系统，基于移动台的定位系统和混合定位系统。在人们生活中常见的是基于移动台的系统，它的原理和 GPS 系统相类似，是以确定的移动台位置来定位用户。
随着手机等个人设备的扩展，室内建筑的复杂化加深，人们对室内导航的需求迅速增大。特别在一些复杂的室内环境，如大型商场、复杂写字楼、大型购物中心、展览馆等，用户常常需要知道在室内的
位置，并知晓如何到达另一个确定的位置。室内的拓扑结构复杂，情况多变，不便于建模，这都是室内导航系统需要克服的难点。
现有常见的室内导航系统的核心包括室内地图信息建模，室内导航算法，室内定位技术。由于室内导航的特殊性，室外导航的技术无法直接照搬于室内导航：
首先在定位方面，室外导航系统往往依赖于室外良好的网络与数据基础，但是GPS 和蜂窝信号进入室内之后会有严重的衰减，同时会有严重的多径效应产生，定位精度非常低。室内定位的网络与测量数据需要独立的系统加以支撑。
其次在地图信息建模方面，建筑内的导航和路网之上的导航是完全不同的。以车载系统为主的室外导航中，用户是只能行驶在路网上的；而以个人为用户的室内导航系统中，人是有可以自由移动的区域的，行动路径的抽象不能如同公路网一般简单实用点和线的连接。地图的抽象和建模需要结合室内情况进行，有的室内建筑可以提供平面的建筑图纸，而有的完全需要人为测量绘制，需要具体问题具体分析。
最后，在导航算法与路径表示方面，由于信息获取和地图定义方式的不同，需要独立的寻路算法和对路径的优化方式，无法直接照搬现有的系统。室内地图在空间结构上有其独特的组织结构，空间上的分层性质、相互层次的独立和连接性质都是其结构特点，也是可以算法针对优化的地方。
室内导航的定位近些年是研究热点，基于 RADAR 的室内 wifi 定位[5]、RFID 定位[6]、基于iBeacon 的蓝牙定位[7]、地磁定位[8]方式等等层出不穷，但是其中的大多数定位方式有着极大的局限性，部署困难，使用准备周期长；对于室内路径导航系统研究较少，更多还是集中于机器人在有限条件下的路径导航；国内室内地图的制作和研究还处于起步阶段，室内地图建模还未形成统一规范的制作标准；以及在室内导航中的路径规划算法。这些都是值得进一步研究和验证的部分。
1.9室内导航系统的国内外研究现状
当前，对于室内导航系统的研究主要集中在两大课题的探讨：一是对室内定位系统的研发，以室内感知系统、智能教室为典型代表；二是通过移动机器人实现导航任务，该领域的研究重点是对机器人自身性能的不断改进，而对于导航功能的完善则相对滞后。
对于室内定位而言，较早的室内定位研究有英国剑桥ORL 在 1992 年研发的基于蜂窝单元的 Active Badge 定位导航系统[9]，它的主要技术是利用红外线作为收发工具，其优点在于可以省去具体的测距环节，但同时也受到其他干扰光线的影响，在
