关于室内停车场的路径规划算法与导航

赵柯柯 韩雨潇 王晓莹 孟凯

摘要：该研究的目的是确保在一个确定的停车场内，在任何一个可行道路上指定一个起点（人），指定一个终点（车），通过我们的路径规划算法，就能找到一条从该起点到终点的可行的通路。该算法以坐标集合的形式传递数据，结果将在我们自主开发的app上显示出来。该研究为汽车用户提供了便捷的使用平台，具有一定的实际应用价值。

关键词：停车场；路径规划算法；app

中图分类号：TP399 文献标识码：A 文章编号：1009-3044（2018）25-0218-02

近年来，室外定位和基于位置的服务已经成熟，基于GPS和地图的位置服务被广泛应用，并成为各种移动设备被使用最多的应用之一。但对于室内环境，GPS信号就显得极其微弱甚至无影无踪。在室外定位技术已经相当成熟的条件下，却无法解决室内的这一问题，而现在的室内定位技术远远不够完善。随着人民的生活水平的提高，各种机动车数量的迅猛增长，现今在商场、购物中心等大型停车场，停车难和找车难是一般车主十分头疼的两个问题。我们进行的《基于Wifi室内定位技术的停车场应用》项目就是为了最大可能的满足大众这一需求。

人人都可以在搭建过Wifi定位系统的地下停车场，短时间内找到一个地下停车场的空停车位，并精确记录自己的车位所在，从而引导用户返回时快速找到自己的车，省去在迷宫一样的地下停车场停车和找车的烦恼。该系统主要解决用户对室内定位精度，覆盖范围，可靠性，功耗和响应时间五个方面的需求，主要应用场景是大型商场的地下停车场。

该项目中有至关重要的一步，即在已知车和人的位置的情况下，怎样进行路径的规划，寻找可行路径，以更大程度的节约时间。在阅读大量文献和进行了许多次实验的情况下，我们设计了一种相对简单又实用的算法。本文模拟了几组数据，意在说明该算法的正确性和可执行性。数据将以坐标集合的形式给出，规划出可行路径，并将计算出来的路径在我们设计的app上显示出来。

1 算法原理

先选取地图上的关键点，一切都围绕关键点来实施。将每条横主干道以及纵主干道的所有的交汇点（即拐弯点）作为关键点。分析得知所有的可行点都至少在横主干道或者纵主干道上，甚至在横主干道和纵主干道的交汇点即关键点上，所以第一步要将起点以及终点移动到离之最近的关键点上，如果已经在关键点上则不用移动，这样一来我们的起点和终点就都位于关键点上了。第二步是判断这两个关键点的相对位置关系，然后找到他们之间的中间关键点。最后将起点、终点和中间的关键点这几个点连接起来，即找到了可行的通路。

2 算法主要函数解释

路线最终以坐标集合的形式给出。该算法用结构体来表示坐标，采用栈来存储路线的坐标集合，并在路径选择时选择总路径总长度最短的坐标集合。首先需判断起点和终点位置的横、纵坐标哪一个在干路上，再选择离起点最近的两个关键点以及离终点最近的两个关键点，然后用一个结构体来表示这2x2四条路线的长度及坐标。比较这四条路径的长度，选择最短的一条路线压入栈中，即为所求的路线。

用两个一维数组来存储干路上的关键点。用X来存储关键点的横坐标，Y来存储关键点的纵坐标。首先用status SeatJudge（int X[]，int Y[]，postype cur，int lenx，int leny）这个函数来判断起点和终点属于哪种情况，分三种：横坐标在干路上，纵坐标在干路上，横纵坐标都在干路上。然后用postype* RoutChoose（int X[]，int Y[]，postype cur，int lenx，int leny）来选择离起点或终点最近的两个关键点。例如，如果起点的横坐标在干路上，则调用postype* Row_equal（postype cur，int Y[]，int leny）这个函数，cur表示起点，Y表示关键点纵坐标集合，leny表示Y的元素个数；在关键点的纵坐标数组Y中选取离起点最近的两个关键点，并存入坐标结构体数组keypoint中，然后需要将两个关键点的离起点的长度分别存入keypoint的两个结构体元素中，这样做的原因是为了找出最短路径。接下来postype KeyPoint（postype key1，postype key2）这个函数是确定干路上的两个关键点后选择两个关键点之间的转折关键点。最重要的函数是void PrintRoute（int X[]，int Y[]，postype start，postype end，int lenx，int leny），以这个函数来确定最终路径。Start表示起点坐标，end表示终点坐标，lenx和leny分别表示数组X和Y的长度。

算法的优点在于将停车场抽象成一个个小方块，忽略了线路，从而使算法实现起来更容易，而关于停车场路径的扩充，则由路径的模拟来完成。

3 算法流程图

算法流程图如下：

4 App实现原理

使用Android Studio工具开发Android app，配置java环境以及Android studio SDK完成Android Studio的安装。首先根据我们实地考察的停车场，绘制了一个10x8的简易虚拟矩形停车区域，然后通过读取路径规划算法生成的关键点文件来获取关键点坐标从而进行连线，从而达到从起始点到目的地点的路径绘制。

5 开发工具优势

Microsoft Visual Studio2008于2007年11月发布，是第一款用于Windows Presentation Foundation （WPF）的拥有可视化设计器的应用程序，它带有对齐线和事件选项卡，允许进行 RAD 风格的程序开发。它还通过用于 Outlook 和 Fluent 菜单的设计器来支持开发人员在 2007Microsoft Office System 中进行程序开发。对于多专业团队，Visual Studio Team System 提高了可伸缩性，包括支持连续集成。

通过对VS2008的学习和应用，基本了解了VS 的强大功能，其提供的窗口模式、视图模式、编程模式极大地方便了用户的使用， 可以使用 C++、C#、VB、VC 等语言进行编程，为不同用户提供了便捷。通过不同的方法达到了同样的目的，学习编程语言是一个积累的过程， VS2008知识一个工具，利用好它我们就能达到写软件的目的，为自己的编程提供便捷！

6 模拟研究

7 结束语

本文首先对已经存在的相关产品进行了试用和分析，发现在信号并不好的室内停车场几乎没有什么帮助，于是在查找了大量文献和进行了多次实地考察后，我们提出了自己的想法并进行了相关研究。由于在现实生活中，停车场的布局并不单一，所以我们对此进行了简化，并在此基础上做路径规划，进一步开发app将结果显示出来。最后通过几组数据的模拟研究说明该算法的正确性和该app的可用性。但是本文并未对导航的精确度进行深入研究，这将是今后研究的重点。

参考文献：

[1] 谢娟.路径规划算法的研究及应用[D].电子科技大学，2015.

[2] 田明星.路径规划在车辆导航系统中的应用研究[D].北京交通大学，2009.

[3] 杨俊成，李淑霞，蔡增玉.路径规划算法的研究与发展[J].控制工程，2017（9）.

[4] 于珊.Android App快速開发平台设计与实现[D].西安电子科技大学，2013.

[5] 黄永正.Android平台App开发辅助工具的研究与实现[D].北京邮电大学，2015.

[6] 韩雪，丁林花，贺红凯，等.基于Android的城市停车场导航APP[J].电脑编程技巧与维护，2016（7）.

【通联编辑：代影】