ai/report.tex

%\documentclass[a4paper,12pt,UTF8,titlepage]{ctexart}

\documentclass[12pt,a4paper,titlepage]{article}
\usepackage{xltxtra,fontspec,xunicode}
\usepackage[slantfont,boldfont]{xeCJK}

\setmainfont{STSong} % 设置文档默认字体

\usepackage{setspace}%使用间距宏包
\usepackage{indentfirst}
\setlength{\parindent}{2em}


\usepackage{subfig}
\usepackage{titlesec}
\titleformat*{\section}{\centering\huge\bfseries}

%页边距
\usepackage{geometry}
\geometry{left=2.0cm,right=2.0cm,top=2.5cm,bottom=2.5cm}

%页眉
\usepackage{fancyhdr}
\pagestyle{fancy}
\lhead{李志星 15060025 } 
\date{2016年7月6日}
\chead{人工智能实验报告}
\rhead{\leftmark}

%文档信息/同时也用于生成报告封面
\author{李志星\\ 15060025}
\title{\Huge 人工智能实验报告\\ \Large 科大校园交通规划}


\usepackage{graphicx}

\DeclareGraphicsExtensions{.eps,.ps,.jpg,.bmp,.gif,.png}

\usepackage{pythonhighlight}


\begin{document}
\begin{spacing}{1.5}
\maketitle

\section{实验内容}
\subsection{实验要求}
运用人工智能课程涉及到的算法，求解交通规划问题。在本次实验中我实现了以下的功能：
\begin{itemize}
\item 数据渲染：给定一个新的地理区域，能够识别各种地形，并且以图形化方式展示该区域的地形和各种建筑物等分布。 

\item 最短路径：给定区域内的任意两个地点，能够利用相关算法求解两个地点之间的最短路径，同时以图形化方式展示出来。

\item 道路规划：按照实际交通要求（例如人群量分布等）对该区域进行道路规划，为该区域内指定的各个地点提供优质交通服务。

\item 站点规划：在规划得到的交通线路上，能够根据相关要求和约束对公交站点进行合理的规划。
\end{itemize}

\subsection{实验环境}
实验中使用的地图数据是我根据科大校园地理环境自行绘制的，主要包括我平时经常涉及到的一些场所，集中体现在跨线桥以北以及东门，有些地方为了方便处理做了相应的调整，但大体上和实际环境是差不多的。

在相关具体实现中，我选择Python实现具体算法，通过Python自带图形工具包Tkinter对实验数据构建的模型以及解决方案进行可视化。

\section{实验过程}


\subsection{数据渲染}

如前所述，我的地图数据是根据科大校园的地理环境绘制的，生成过程为：先在Excel表格中进行模拟绘制，最小单位是一个单元格；把绘制的地图数据导成CSV格式的；最后程序的输入就是该CSV文件。


数据渲染首先从文件中加载数据，然后调用Tkinter进行绘制，其中的关键点是画布与地图数据的动态协调：能够根据数据规模动态地协调各元素的表示位置和尺寸。其具体过程如下图所示。
\begin{figure}[h!] 
\centering
\includegraphics[width=18cm]{draw_map.jpg}
\caption{数据渲染过程}
\label{draw_map}
\end{figure}

地图数据是一个规模为23*18的矩阵，如下图所示。其中元素点的含义：0 - 围墙，1 - 道路，2 - 建筑物，3 - 训练场，4 - 大门，5 - 草坪/操场，6 - 其他非道路区域。在这些元素中，只有道路是可以通过的，其他都可以看做"障碍物"，不可通行。

\begin{figure}[h!] 
\centering
\includegraphics[width=10cm]{csv.jpg}
\caption{地形数据}
\label{knn}
\end{figure}

另外，为了更好的显示的显示部分建筑物以及更直观的可视化，我还对大部分的建筑物做了标记，这些数据也是存放在csv文件中，格式是<名称,坐标>。其中为了简化处理过程，还做了如下的假设：
\begin{itemize}
\item 为便于定位和识别建筑物，我标记了一些建筑物用来做测试，这些建筑物假设只占一个格子，这样方便判断和确定其位置。如果一个建筑物占据了多个格子，那在确认它的时候需要做一些额外的繁琐的判断，但是对于基本的核心算法是没有影响的，因此在这里做了个一个简化性的假设。
\item 建筑物只要挨着道路，那任何方向都是通的，不再设置哪个方向有门哪个方向没有门。理由和上面的是一样的，也是为了简化一些不必要的计算和判断。
\end{itemize}

\begin{figure}[h!] 
\centering
\includegraphics[width=18cm]{map.jpg}
\caption{地图模型}
\label{knn}
\end{figure}



\subsection{最短路径}
在求解区域内两个建筑物间最短路径的问题中，我应用了A*算法。算法的大题思路是参考的教科书上的过程，只不过在具体实现中有很多的细节和优化的地方需要考虑而已。

在该模型中，最短路径问题可形式化为：
\begin{itemize}
\item 初始状态为“起始节点”，目标状态是“终止节点”，地图中每一个道路节点都可以看做是一个状态，其它元素节点不会出现在最后的路径中出现，但是会影响状态的可用动作集合；
\item 在某一个状态可用的动作集合我定义为{“上”、“下”、“左”、“右”}，也就是某个节点上下左右相邻的四个方向，但是如果该方向有前面定义的“障碍物”的话，此方向便不可通过；
\item 路径代价设置的是每移动一个方格耗费一个单元的值。
\end{itemize}

为了方便交互，我在界面中添加了文本框用以输入起始点和终止点，其次我在程序中做了转换，因此输入的数据直接是建筑物名字即可，对照着图形中的标注，可以很方便的进行测试。
\begin{figure}[h!] 
\centering
\includegraphics[width=12cm]{btn_path.jpg}
\caption{路径起始点输入框}
\label{btn_path}
\end{figure}

在输入起始节点和终止节点之后，算法的处理流程如下所示。
\begin{figure}[h!] 
\centering
\includegraphics[width=10cm]{sp.jpg}
\caption{最短路径处理流程图}
\label{sp}
\end{figure}
为了清晰表达大致思路，在该流程中有一些子过程pop\_frontier、get\_neighbors和get\_solution等没有画出，他们的作用为：
\begin{itemize}
\item pop\_frontier：用于在frontiers里面选择一个进行判断和扩展，在该函数中会利用f(n) = g(n) + h(n)对节点进行评估，g(n)就是从初始节点到当前节点的路径代价，由前面模型的形式化可知g（n）也是走过的方格数，因此再展开新的frontier时直接递增即可；而对于启发函数h(n)来说，它的选择比较重要，常见的有欧几里得距离也就是直线距离，或者曼哈顿距离。在本实验中，这两种方法我都试过了，在我试的几个测试用例中，它们俩的表现是相同的，没有发现有太大的差别。
\item get\_neighbors函数用于获取一个节点的相邻接点，这与模型规定的可用动作是一致的，它做的主要判断有两类：是否是合法的节点，也就是是否超过了给定的地图边界；其次是该节点是否是有效节点，有效节点是那些道路所处的节点，其它的节点不能出现在路径中。
\item get\_solution是为了获得解的路径，因此我对每个节点对应一个father指针，它指向展开它的节点，也就是最后路径上处于它上一个的节点。因此这个函数利用链表倒序就可以把解路径求出。
\end{itemize}

具体的测试会在实验结果中给出。

\subsection{线路规划}
现在设想这样一种场景：为了方便师生在校园内的交通，现在想要开辟一个环校线路提供校车服务。在前面章节地图中标出的地点表明是主要地点，该线路应该尽可能使得这些地点的师生方便乘车，其次图书馆和北门是必须要经过的，因为这两个地方人流量是最大的。现在先不考虑站点停靠，可以先考虑成招手上车、随时停车，站点规划问题会在下一节中考虑。由上可得该线路的目标有：
\begin{itemize}
\item 路径长度短：从实际情况出发，该目标也是现实的，规划的路线越短越经济，效益越高。
\item 方便人们上车：地图中指定的地点都是分散的，规划出的线路要使各个地方的人们上车距离尽可能小，使人们不要走太长的路就能走到该线路上等车或者乘车。
\item 考虑人群量：另外还要考虑一个因素，那就是这些地方的人群量是不同的，有些地方人数较多，线路就应该忘这些地方倾斜，满足更多人的需求，也使得线路的吞吐量大一些。
\end{itemize}

通过分析该问题可以理解为：寻找一条路径使得地图中各点到该路线的加权距离越小越好，并且该路径越短越好。另外，要求必须通过图书馆和北门，因此可以使这个问题分为两部分来规划，其实这也是我为了简化问题故意设定的场景。对处于图书馆和北门之上和之下的建筑分别规划出同样目的的路径，因为这两条路径的起始点和终止点是重叠的，所以最后可以连成一条路径，通过用这样的分治法先规划出子问题来解决复杂的问题。

由以上需求，结合A*算法，其f(n) = g(n) + h(n)中的g(n)和求最短路径一样，还是起始节点到当前节点的路径长度。而h（n)就需要好好设计了。一开始我是算的各个地点到当前节点的直线距离然后配上其人群量权重，h(n)是这样计算的：\\
\begin{figure}[h!] 
\centering
\includegraphics[width=8cm]{line_dis.jpg}
\label{linedis}
\end{figure}

其中p是对需要规划的所有地点进行遍历，w是其对应的人群量的权重，该值越大说明该地点人数越多。由这种方式规划出来的效果非常不好，后来我分析，不能计算地点到当前节点的距离，如果路径已经规划出一部分了，那么应该计算地点到该路径,也就是从起始点到当前节点的这段路上，其最短距离才对。因为如果一个地点到该路径的最短距离不是当前节点，而是其之前的某一个节点，则该地点不应该影响对这个节点的选择才对。因此此时的h(n)是这样的：\\
\begin{figure}[h!] 
\centering
\includegraphics[width=8cm]{min_dis.jpg}
\label{linedis}
\end{figure}


path(p)表示从起始节点到当前节点的路径，min\_dis(a,p)指p到路径a上最短距离。通过这种方式后，效果比之前的要好了一些，但是对于一些地点它还是会处理的不好，比如对于位于底部的博餐来说，如果距离函数用的还是直线距离，那么当算法走到位于其左上角的丁字路口时，无论是直走还是右拐，其值不变，但是对于其他值来说右拐似乎更好，因此路径就会被诱导的右拐了，即使博餐的人群量再大，在这个路口也不会直走。因此我就想着如何规避这个陷阱 ，最后决定用A*算法算出的最短路径来代替直线距离，这样的h(n)更能反映真实的距离。这样一来这个算法有点贪心算法的性质，并且直观上讲起效率有点低下。在这里我进行了优化，利用动态规划后的思想对地点到路径节点的最短路径值进行缓存，这样的做法大大的提高了效率，实验对比会在实验结果中给出。


\subsection{站点规划}
为更有效的运行该线路，可以在上一节得到的线路中，对其设置一些校车停靠点，这个问题相对来说比较好解决些。其目标就是要让各地点的人到停靠点的距离越小越好。同样这个问题也要考虑人群量的影响。我的解决思路是利用深度优先遍历取最优值。比如想要设置8个站点，除去图书馆和北门外，两个子问题得到的线路各自应该有3个站点。在该子路线中按照深度优先的策略对每三个节点进行测试，计算各个地点到该规划站点的距离，其计算公式为：\\
\begin{figure}[h!] 
\centering
\includegraphics[width=8cm]{sdis.jpg}
\label{sdis}
\end{figure}

stops是规划得到的停靠点集合，min\_sdis(stops,p)用来计算p到stops中每个站点的最短路径的最小值。因为在线路规划中最短路径值都已经缓存过了，因此这里的计算速度还可以。因为我一开始设计的站点数k是可以动态设计的，因此这部分的难点在于如何高效率动态地遍历出所有k个节点的组合，多层for循环是不现实的，因为k是变化的，我用了一个类似数值逐位求余的思想组合的，代码效果还可以。

\section{实验结果}
数据渲染效果已经在前面有所展示了，下面的章节从剩余的三个方面给出实验结果。

\subsection{最短路径}
限于篇幅，报告中以“图书馆到17栋”、“17栋到博餐”和“八队到图书馆”为例展示结果。由于我在介面中提供了交互控件，因此更改初始点和终止点进行不同的测试是很方便的。

\begin{figure}[h!] 
\centering
\includegraphics[width=16cm]{1.jpg}
\caption{图书馆到17栋的最短路径}
\label{sdis}
\end{figure}
\begin{figure}[h!] 
\centering
\includegraphics[width=16cm,height=10cm]{3.jpg}
\caption{17栋到博餐最短路径}
\label{sdis}
\end{figure}

\begin{figure}[h!] 
\centering
\includegraphics[width=16cm,height=10cm]{6.jpg}
\caption{八队到图书馆最短路径}
\label{sdis}
\end{figure}
从以上结果可以看出，该算法较好地实现了两点之间最短路径的问题，能够对任意两个建筑物之间求出其最短的路径。

\subsection{路线规划}
如前所述，我们会考虑人群量的因素，因此这里分别给出不同人群量分布对路线的影响。
下面四个图分别是：人群分布都一样；增大601人群分布；继续增大pdl人群分布；继续增大博餐人群分布；

\begin{figure}[h!] 
\centering
\includegraphics[width=16cm,height=10cm]{p1.jpg}
\caption{人群分布一样时的线路规划}
\label{sdis}
\end{figure}

\begin{figure}[h!] 
\centering
\includegraphics[width=16cm,height=10cm]{p2.jpg}
\caption{增大601食堂人群分布时的规划线路}
\label{sdis}
\end{figure}


\begin{figure}[h!] 
\centering
\includegraphics[width=16cm,height=10cm]{p3.jpg}
\caption{继续增大pdl人群分布时的规划线路}
\label{sdis}
\end{figure}

\begin{figure}[h!] 
\centering
\includegraphics[width=16cm,height=10cm]{p4.jpg}
\caption{继续增大博餐人群分布时的规划线路}
\label{sdis}
\end{figure}



\subsection{站点规划}
下图分别是人群重点分布在601、博餐以及办公楼和人群重点分布在教学楼、餐饮以及PDL的站点规划图，其中黄色表示公交站。
\begin{figure}[h!] 
\centering
\includegraphics[width=16cm,height=10cm]{s.jpg}
\caption{人群重点分布在601、博餐和办公楼时的站点规划}
\label{sdis}
\end{figure}

\begin{figure}[h!] 
\centering
\includegraphics[width=16cm,height=10cm]{s2.jpg}
\caption{人群重点分布在教学楼、餐饮以及PDL的站点规划}
\label{sdis}
\end{figure}


\section{实验总结}

在本次实验中，我设计了交通规划算法， 以科大校园为基础创建了地图模型，分别完成了地图模型渲染、最短路径求解、考虑人群量因素影响的环校公交线路规划以及校车站点停靠这几个问题，并取得了较好的实验结果。

通过这次实验，我加深了对搜索算法的理解，也增强了动手能力，收获了很多。
\begin{itemize}
\item 之前对算法的理解只是局限于从书本上了解到的内容，没有具体实现过。自己动手实现才知道有很多细节需要处理，有很多地方需要进行效率的优化。本以为很简单的程序，具体实现起来可能需要上百行代码，就拿这次实验为例，总的加起来400多行，虽然其中很大原因是因为自己编程水平有限造成的，但是仍然说明了从抽象层面去理解算法和具体去实现算法有很大的区别的。
\item 模型一开始考虑的很难得话，会给实现造成困难，因此不要一开始就把问题考虑的很复杂，要由浅入深，先把模型简单化，得到初步的思路和解决方案，然后慢慢的给模型加东西，这样一步步来才更有助于解决问题。
\item 通过这次实验能够把之前学到的很多东西都融会贯通了，比如当我看到计算速度太慢的时候，我就分析瓶颈在哪里，然后用代码调试来验证，当知道原因之后，借鉴了之前本科学过的动态规划缓存记忆历史的思路进行了优化，结果大大提高了计算速度。这种实践活动很好地把我的知识体系串了起来。
\end{itemize}

但是在实验过程中仍有很多地方值得改进和完善。
\begin{itemize}
\item 为了简化问题，我把要处理的建筑物都当成是一个矩阵点来看待的，但这是不现实的，实际情况中，一个建筑物占地往往是不规则的。后续的实验中可以丰富建筑物的形态，并且能够正确分辨出其实际方位和格局等。
\item 一些试验参数设置的过于简单，比如在第一章路线规划图中，当各个地点的人群量分布是一样的时候，规划得到的线路并不是太好，因为她为了避免过长的路径，而放弃了把路径延伸到更远的地点去。这应该是代价函数和启发函数的参数没有设置好，如果能够根据一些现实数据来设置参数的话效果应该会更好一些。
\end{itemize}

最后，要感谢祝老师的教导，通过这门课我学到了很多有用也很有趣的知识，对于我以后的研究都有很大的启发和帮助。尤其是这个实验作业对我改变最大，我一直以来对算法问题都有很大的抵触心态，感觉很枯燥，因此以前都是尽力避开这方面的研究。但是通过这次试验，我发现任何的算法都有其具体的应用场景，而任何的现实问题，都可以通过建模然后应用相应的算法来求解。并且在不断尝试和不断优化问题的解决方案的过程中，能够学到很多有用的东西。
\end{spacing}
\end{document}