人工智能学习之基于A*算法的机器人路径规划优化

前言

大三下学期，学习了人工智能，因为要备研，上课基本上没怎么听，故也就没怎么学，这是一门考查课，最后要完成布置的大作业，作为算分的依据，就选一个简单的完成吧。主要是A*算法的模拟。

本文原创，创作不易，转载请注明！！！
源码下载：
链接：https://pan.baidu.com/s/1HjCfUqT3yaRiBP2fBXAjWQ?pwd=Lin2
提取码：Lin2
白嫖虽好，学到东西才是真！

Qt入门系列：
Qt学习之C++基础
Qt学习之Qt安装
Qt学习之Qt基础入门(上)
Qt学习之Qt基础入门(中)
Qt学习之Qt基础入门(下)

题目

题目分析

机器人路径规划优化。

问题描述：机器人路径规划是移动机器人导航最基本的环节，指的是机器人在有障碍物的工作环境中，如何找到一条从起点到终点适当的运动路径，使机器人在运动过程中能安全、无碰撞地绕过所有障碍物。设机器人对环境已经，并且以进行了网格化处理 ，设1表示该网格为障碍物，0表示该网格无障碍物，机器人只可以前后左右四个方向移动，环境中包含一个起点和终点，请设计一个算法实现机器人从起点到终点的路径规划，路径越短约好。

要实现的选题如上，因为人工智能基本上没怎么听，就选择一个比较简单的题目实现模拟，主要是涉及到GUI图形界面和A*算法，故选择编程语言为C++，做一些简单的算法模拟比较简单，然后GUI选择Qt，有关Qt的学习可见我的如下博客：

Qt入门系列：
Qt学习之C++基础
Qt学习之Qt安装
Qt学习之Qt基础入门(上)
Qt学习之Qt基础入门(中)
Qt学习之Qt基础入门(下)

结果演示

首先选择一个方块，设置起点，然后再选择一个方块，设置终点，然后设置0个等若干个障碍物，就可以点击开始寻路了。

设置起点：选择一个方块设置为起点，默认为蓝色。
设置终点：选择一个方块设置为终点，默认为红色。
设置障碍：选择若干个方块设置为障碍物，可多选也可不选，默认为灰色。
清除还原：清空所有界面上的方块状态，将方块还原为初始态。
设置毫秒：设置每一步寻路的时延，默认为50ms。
开始寻路：设置好起点与终点之后即可开始寻路。
所有快捷键可用，同时按钮上存在功能提示！

A*算法

接下来对A*算法进行简单的说明。

简介

A*算法，被广泛应用于游戏中的自动寻路功能，A*算法是一种结合了前面两种算法优点的算法，在A*算法中，我们对节点按以下的方式进行排序：F = G + H，其中，G为从初始状态到当前状态所花费的代价；H为从当前状态到最终状态可能要付出的代价，H的值的计算由程序员来估算，同时H的估计算法越准确，算法所需要遍历的节点就越少；F为两者的和。A*算法是一种有序搜索算法，其特点在于对估价函数的定义上。对于一般的有序搜索，总是选择F值最小的节点作为扩展节点。因此，F是根据需要找到一条最小代价路径的观点来估算节点的。可考虑每个节点n的估计函数值为两个分量：从起始节点到节点n的代价以及从节点n到目标节点的代价。

代码设计

本次机器人路径规划优化采用A*算法，同时将采用动画GUI的方式显示寻路过程，所以采用Qt开发，A*算法寻路方式如下：

  1. 把起点加入 open list 。
  2. 重复如下过程：
    a. 遍历open list，查找 F 值最小的节点，把它作为当前要处理的节点。
    b. 把这个节点移到close list。
    c. 对当前方格的 8 个相邻方格的每一个方格。
    · 如果它是不可抵达的或者它在close list中，忽略它。否则，做如下操作。
    · 如果它不在 open list 中，把它加入open list，并且把当前方格设置为它的父亲，记录该方格的F，G和H值。
    · 如果它已经在open list中，检查这条路径（即经由当前方格到达它那里）是否更好，用G值作参考。更小的G值表示这是更好的路径。如果是这样，把它的父亲设置为当前方格，并重新计算它的G和F值。如果你的open list是按F值排序的话，改变后你可能需要重新排序。
    d. 停止，当你把终点加入到了open list中，此时路径已经找到了，或者查找终点失败，并且open list是空的，此时没有路径。
  3. 保存路径。从终点开始，每个方格沿着父节点移动直至起点，便是路径。

程序设计

A*算法模拟

在A*算法中，按照上述的流程框图设计程序，需要注意的特殊情况为当用户设置了一个闭合区域的路径，即不存在路径从起点到终点，则需要弹出来一个对话框提示用户，路径不可达，如下图，同时停止A *算法的寻路过程，还原界面状态。

同时本程序设置的默认模式是，寻路过程中，是可以直接跨过“墙角”的，这样路径会更加灵活，但是存在一个问题是当两个障碍物在对角时，它会判断为可过，如下图，路径①和路径②均为一个障碍物的“墙角”，路径①为A至B，同时在中心块的左上角存在一个障碍物，路径②为C至D，不存在障碍物。这样的话，如果不做处理，程序在考虑中心块时，会将①和②视为同等路径且可以直接穿过，不符合逻辑。

综上情况，要增加特判，在考虑路径是否能通过时，还要考虑对角，例如，图4.5，当A在考虑B的时候，同时要特判A的上方和A的左侧是否存在障碍物，如果存在，则不允许通过，即不允许A至B，其他A至C、A至D、A至E同理，这四种情况都是不允许通过的情况。

同时还设置了每个格子所花费的代价，也就是Gx的代价，代码如下：

#define COST_DIET 10//定义一格花费10#define COST_LINE 14//对角线花费14

为了取整，设置上下左右代价为10，走对角代价为√2，换算为14，最后根据A*算法的流程图模拟实现即可。

编程

界面设计是一个难题，再次分析需求，设置一个起点，设置一个终点，设置若干个障碍物，根据A*算法，从起点找到一条可以到达终点的路径，因此，需要一个比较大的二维网格图，然后有设置起点、设置终点、设置障碍和路径显示的功能，据此，设计GUI界面和逻辑功能，同时根据模块化思想，故设计多个类，文件结构如下图，接下来详细说明各个部分的代码逻辑。

根据开发工程模块化的思想，使用MVC框架开发，M是指Model业务模型，V是指View用户界面，C则是Controller控制器，使用MVC的目的是将M和V的实现代码分离，从而使同一个程序可以使用不同的表现形式。在图4.6中，View为Forms目录下的两个ui文件，做主要界面设计，astarcellwidget.ui是一个单元格的界面，mainwindow.ui是程序主界面；Controller为astarcellwidget.cpp和mainwindow.cpp文件，前者是单元格的控制器，后者是主界面的控制器；Model是astarcell.cpp，这是单元格的主要数据结构；最后是Resources目录下的res.qrc文件，这个主要是程序要用到的图片，例如程序的头像。

首先是每一个格子的说明，对应代码文件中的astarcellwidget.cpp和astarcell.cpp，在astarcell.cpp中定义了AStarCell类的主要数据结构；

class AStarCell : public QObject{Q_OBJECTpublic:explicit AStarCell(QObject *parent = nullptr);int parent_x = -1;int parent_y = -1;QString printAStar();void initCell();void setGx(int gx);void setHx(int hx);int getGx();int getHx();int getFx();signals:void changeGx();void changeHx();private:int gx;int hx;int fx;public slots:};

成员变量一共五个，分别是：gx、hx、fx、parent_x和parent_y，前三个对应A*算法中的g(x)、h(x)和f(x)，均为私有变量，后两个是为了最后的寻路而定义的变量，成员方法有initCell()方法，用来初始化一个格子的数据，printAStar()方法，用来打印输出g(x)、h(x)和f(x)的值，然后还有getter和setter，因为F=G+H，故没有setFx()方法，fx的值在hx和gx中的setter中同步更新。然后就是View的astarcellwidget.ui，主要是Gx、Hx和Fx值的显示。最后是Controller的astarcellwidget.cpp，定义了AStarCellWidget类，此类内容较多，首先要说明的是，单元格的类型，根据需求，可以总结出，一个单元格的类型有：初始、起点、终点、障碍物、路径候补点、路径点、用户选中这7类，定义一个枚举类型如下：

enum CellType{Null = 0,Start = 1,Barrier = 2,End = 3,Candidate = 4,Path = 5,Selected=6} type;

然后就是根据不同的类型设置单元格的颜色，因为格子比较小，为了更好的显示信息，关闭了界面尺寸调节，同时设置了悬浮tips提示，将鼠标放在单元格的格子上，就会显示当前格子的Gx、Hx和Fx值。最后因为一个单元格有固有属性是此单元格在表格的哪个位置，所以设置了pos_x和pos_y来记录当前格子的位置，同时定义了每个格子的大小，表格中单元格的格式：

#define COLUMN_COUNT 24#define ROW_COUNT 16#define COLUMN_WIDTH 50#define ROW_HEIGHT 50

单元格构建完毕之后，就是主界面的设计，主界面因为只有一个A*算法的模拟过程是属于模型，故不再另新建文件，将Controller和Model融合都放在mainwindow.cpp文件中的MainWindow类里。这是主界面的视图，接下来简述此部分代码逻辑。
主界面的按钮一共有5个，别是设置起点、设置终点、设置障碍、清除还原、开始寻路。设置起点按钮，选中一个单元格之后，点击设置起点或者按键盘上的B，即可把当前单元格设置为起点，内部的逻辑为，当用户选中一个单元格的时候，AStarCellWidget类会向MainWindow类发送一个信号，告诉后者用户选中那个单元格，然后用户点击设置起点按钮之后，MainWindow就会提取当前选中的点，如果有多选或者未选则提示错误，如果无错误，就将当前的格子设置为起点，然后调用AStarCellWidget的setCellType()方法设置类型。
设置终点、设置障碍按钮逻辑同理，清除还原是将当前界面的所有的单元格的类型都设置为初始，同时清空MainWindow类中保存的选中的点。
开始寻路按钮较为特殊，当点击之后，会检测是否选择了起点、是否选择了终点，然后会封锁一些控件防止用户误操作影响结果，然后初始化整个表格，然后开始运行A*算法寻找路径，当找完，还原被封锁的控件，如图4.9。还有一个控件是文本框，主要是用来设置寻路过程中每一步的速度，只能输入整数，如果不是整数的话，就会按照默认的50ms执行。
在MainWindow类中还定义了一个aStarFinishEvent()方法，这个方法是当A*算法找到了终点的时候执行，用来从终点出发按照搜索过程中设置的parent显示路径，然后将封锁的控件重新还原打开。

总结

本次实验遇到的棘手的问题一个是A*算法的模拟过程，查询了很多资料，最终理解了之后才编码模拟，第二个是Qt中的子Widget和父Widget的事件监听，因为想要实现子Widget（单元格）的鼠标点击事件监听，同时还要监听父Widget（主界面）的键盘事件，在Qt中默认优先子控件，然后父控件被过滤，查询了很多的资料和官方的API后，在子Widget用一句：

this->setAttribute(Qt::WA_KeyboardFocusChange,true);

来设置窗口焦点的获取，最后理清Qt事件处理的逻辑顺利关系，最终实现了子Widget鼠标监听和主界面的快捷键功能。

关于本次实验，学习了人工智能中的A*算法，相比在数据结构中学到的常见的搜索算法，非常具有优势，个人认为，A*算法的灵活在于H(x)的计算方法，本次实验中，本人主要用是曼哈顿距离计算H(x)，一种理想化简单化的计算方法，在实际应用过程中，可以根据业务逻辑的要求，选择不同H(x)计算方法，来获得更好的、更智能的路径规划。
本次实验设计，基于Qt、A*算法实现的机器人路径规划优化，学到了很多东西，获益匪浅，但本实验中还存在很多优化，例如，处于closeList中的节点同样可以拿出来考虑，由于时间有限，资料查阅有限，故选择了一种简单的实现方式，其次，界面的友好性可以继续优化，例如方便用户一键多选等等，还有很大的优化和进步空间。

的、更智能的路径规划。
本次实验设计，基于Qt、A*算法实现的机器人路径规划优化，学到了很多东西，获益匪浅，但本实验中还存在很多优化，例如，处于closeList中的节点同样可以拿出来考虑，由于时间有限，资料查阅有限，故选择了一种简单的实现方式，其次，界面的友好性可以继续优化，例如方便用户一键多选等等，还有很大的优化和进步空间。

总而言之吧，获益匪浅，=w=