由于未改进的Dijkstra算法搜索得到的数据中有相当一部分是无用的，因此，为了解决其效率低的问题，从另一方面，A*算法作为一种启发式算法被提出。A*算法在广度优先的基础上加入了一个估价函数。
5.1A*算法原理
对于A*算法，其核心在于估价函数的设计上：
其中,为耗散函数，表示从起始节点到节点的实际代价；为启发函数，表示从节点到目标节点的估计代价；表示从起始节点经由节点到目标节点的估计代价。
图1：启发函数的值对搜索空间的影响对比
与Dijkstra算法相类似，A*算法也维持一个了表。表中节点的优先级是根据的大小来排列的，其值越小，被搜索到的优先级就越高。因此，为了保证能够搜索到最优解，启发函数不能太大，不能大于节点到目标节点的实际代价；但如果，则A*算法就退化为Dijkstra算法，虽能保证得到最优路径，但算法效率低；如果恰好等于节点到目标节点的实际代价，则A*算法探索的节点恰好就是最优路径上的节点。所以的取值直接影响算法的速度和精确度，常见的的取值有两点之间的欧几里得距离和曼哈顿距离等。
5.2A*算法应用及结果分析
图2：A*算法运行结果
图中左下角红块为起点，右上角红块为终点，蓝色线条为规划路径。
结果分析：从运行过程来看，A*算法运行较快，效率较高。与Dijkstra算法搜索过程相比，A*算法起点搜索一直沿着向终点的方向搜索前进，而不是像Dijkstra算法那样大范围地搜索环境地图，判断环境信息，A*算法的搜索更有目的性、方向性。但由于A*算法搜索方向较为单一，刚开始时搜索即会确定一个单一的搜索方向，如果该方向出错，可能会偏离终点位置，进而搜索失败。
5.3A*算法改进--双向探索A*算法
5.3.1双向探索A*算法思路
A*算法本身搜索速度快、效率高，其最终探索的路径虽然是最短的，但速度并不一定是最快的，因此我们采用与双向探索Dijkstra算法相似的原理，使其搜索时同时从起、终点开始，对于A*算法，搜索就由原来单一的方向变成了双向，且基于A*算法本身高精度的特点，选择双向搜索结果中较好的一个，规划路径将会更加准确可靠。
双向探索A*算法思路如下：
图3：双向探索A*算法思路
5.3.2双向探索A*算法结果及分析
改进算法后运行结果如下：
图4：可能运行结果1
图5：可能运行结果2
图6：可能运行结果3
图中，蓝线为从起点开始搜索得到的规划路径，绿线为从终点开始搜索得到的规划路径，每次运行环境地图将会发生一定变化，进而导致规划路径结果也会有一定变化，这也对应了不断变化的实际环境条件。
结果分析：从图4得出，在其环境地图中，从起、终点开始搜索，两者的搜索速度相同，因此同时都得到了路径规划结果，我们就可以从中选取一条合适的路径作为最终结果；从图5可以看出，当起点搜索结束时，终点搜索还在继续，显然起点的搜索速度比终点快；从图6可以看出，当终点搜索结束时，起点搜索还在继续，显然终点的搜索速度比起点快。
算法特点：能够适应不同的环境地图，实际适用性更强。以双向探索A*算法进行路径规划，不管是何种地图环境（两点之间无路径除外），都可以得到至少一条用时最短的最优路径，从而加快了探寻最短的路径的速度。
附：代码
1、主程序
%%基于A*算法的全局路径规划clcclear%%%建立地图和设置目标点%设置地图的长和宽map_XYMAX=20;map=zeros(map_XYMAX,map_XYMAX);%绘制地图fori=1:map_XYMAX+1line([-0.5,map_XYMAX-0.5],[i-1.5,i-1.5]);line([i-1.5,i-1.5],[-0.5,map_XYMAX-0.5]);holdonend%设置起点和终点map_start=[0,0];map_goal=[19,19];%绘制起点和终点plot(map_start(1),map_start(2),or);holdonplot(map_goal(1),map_goal(2),ob);holdon%%%随机生成障碍物obstacle=[];obstacle_number=;ob=floor(rand([obstacle_number,2])*map_XYMAX);removeInd=[];forio=1:length(ob(:,1))if(isequal(ob(io,:),map_start)
isequal(ob(io,:),map_goal))removeInd=[removeInd;io];endendob(removeInd,:)=[];obstacle=[obstacle;ob];forz=1:map_XYMAX+2obstacle=[obstacle;-1z-2];obstacle=[obstacle;z-2-1];obstacle=[obstacle;20z-2];obstacle=[obstacle;z-];end%将障碍物填充颜色fori=1:length(obstacle(:,1))x=obstacle(i,1);y=obstacle(i,2);X=[x-0.5,x+0.5,x+0.5,x-0.5];Y=[y-0.5,y-0.5,y+0.5,y+0.5];fill(X,Y,k);holdon;end%%%路径规划%创建存储路径path=[];%此列表是从map_start向map_goal方向搜寻的路径列表path_1=[];%此列表是从map_goal向map_start方向搜寻的路径列表%创建open列表open=[];%此列表是从map_start向map_goal方向搜寻open列表open_1=[];%此列表是从map_goal向map_start方向搜寻open列表%创建close列表close=[];%此列表是从map_start向map_goal方向搜寻close列表close_1=[];%此列表是从map_goal向map_start方向搜寻close列表%用于判断while循环是否结束findFlag=false;%计算起始点和目标点之间的距离dis=10*abs(map_start(1)-map_goal(1))+10*abs(map_start(2)-map_goal(2));%将起始点添加到open列表中去open=[map_start(1),map_start(2),0+dis,0,0,0];%将目标点添加到open_1列表中去open_1=[map_goal(1),map_goal(2),0+dis,0,0,0];%进入循环while~findFlag%%从map_start向map_goal搜寻路径%判断open列表是否为空ifisempty(open(:,1))disp(Nopath!);return;end%判断目标点是否在open列表中fori=1:length(open(:,1))ifisequal(map_goal(1:2),open(i,1:2))disp(FindGoal!);close=[open(i,:);close];findFlag=true;break;endend%将F值进行排序[Y,I]=sort(open(:,3));open=open(I,:);%将此时open列表中的第一行移除，添加到close列表中close=[open(1,:);close];current=open(1,:);open(1,:)=[];%计算更新后的8个节点的F值next=[-1,1,14;0,1,10;1,1,14;-1,0,10;...1,0,10;-1,-1,14;0,-1,10;1,-1,14];forj=1:length(next(:,1))%下一个节点参数m=[current(1,1)+next(j,1),current(1,2)+next(j,2),0,0,0,0];%从当前节点到下一个节点的G值m(4)=current(4)+next(j,3);%从当前节点到下一个节点的H值H=10*abs(m(1)-map_goal(1))+10*abs(m(2)-map_goal(2));%从当前节点到下一个节点的F值m(3)=m(4)+H;%判断当前节点是否为障碍物,如果是障碍物则忽略ifisObstacle(m,obstacle)continue;end%判断下一节点所在列表[flag,targetInd]=FindList(m,open,close);%case_1:在close列表中ifflag==1continue;%case_2:不在列表中elseifflag==2m(5:6)=[current(1,1),current(1,2)];%将当前节点作为其父节点open=[open;m];%case_3:在open列表中elseifm(3)open(targetInd,3)%将当前节点作为其父节点m(5:6)=[current(1,1),current(1,2)];open(targetInd,:)=m;endendpause(0.01);%将open列表和close列表填充颜色fori=1:length(close(:,1))x=close(i,1);y=close(i,2);X=[x-0.5,x+0.5,x+0.5,x-0.5];Y=[y-0.5,y-0.5,y+0.5,y+0.5];fill(X,Y,r);end%%从map_goal向map_start方向搜寻路径%判断open——1列表是否为空ifisempty(open_1(:,1))disp(Nopath!);return;end%判断起始点是否在open_1列表中fori=1:length(open_1(:,1))ifisequal(map_start(1:2),open_1(i,1:2))disp(FindGoal!);close_1=[open_1(i,:);close_1];findFlag=true;break;endend%将F值进行排序[Y,I]=sort(open_1(:,3));open_1=open_1(I,:);%将此时open_1列表中的第一行移除，添加到close_1列表中close_1=[open_1(1,:);close_1];current_1=open_1(1,:);open_1(1,:)=[];%计算更新后的8个节点的F值next=[-1,1,14;0,1,10;1,1,14;-1,0,10;...1,0,10;-1,-1,14;0,-1,10;1,-1,14];forj=1:length(next(:,1))%下一个节点参数n=[current_1(1,1)+next(j,1),current_1(1,2)+next(j,2),0,0,0,0];%从当前节点到下一个节点的G值n(4)=current_1(4)+next(j,3);%从当前节点到下一个节点的H1值H1=10*abs(n(1)-map_start(1))+10*abs(n(2)-map_start(2));%从当前节点到下一个节点的F值n(3)=n(4)+H1;%判断当前节点是否为障碍物,如果是障碍物则忽略ifisObstacle(n,obstacle)continue;end%判断下一节点所在列表[flag,targetInd]=FindList(n,open_1,close_1);%case_1:在close_1列表中ifflag==1continue;%case_2:不在列表中elseifflag==2n(5:6)=[current_1(1,1),current_1(1,2)];%将当前节点作为其父节点open_1=[open_1;n];%case_3:在open_1列表中elseifn(3)open_1(targetInd,3)%将当前节点作为其父节点n(5:6)=[current_1(1,1),current_1(1,2)];open_1(targetInd,:)=n;endendpause(0.01);%将open_1列表和close_1列表填充颜色fori=1:length(close_1(:,1))x=close_1(i,1);y=close_1(i,2);X=[x-0.5,x+0.5,x+0.5,x-0.5];Y=[y-0.5,y-0.5,y+0.5,y+0.5];fill(X,Y,y);endend%%%绘制path路线ind=1;whiletruepath=[path;close(ind,1:2)];ifisequal(close(ind,1:2),map_start)break;endfori3=1:length(close(:,1))ifisequal(close(i3,1:2),close(ind,5:6))ind=i3;break;endendendiflength(path)=1plot(path(:,1),path(:,2),-c,LineWidth,5);enddisp("Thelineofcyanisfromstarttogoal.")%绘制path_1路线ind=1;whiletruepath_1=[path_1;close_1(ind,1:2)];ifisequal(close_1(ind,1:2),map_goal)break;endfori3=1:length(close_1(:,1))ifisequal(close_1(i3,1:2),close_1(ind,5:6))ind=i3;break;endendendiflength(path_1)=1plot(path_1(:,1),path_1(:,2),-g,LineWidth,5);enddisp("Thelineofgreenisfromgoaltostart.")%%%判断两条路径用时的长短Flag=false;while~Flagfork1=1:length(close(:,1))ifisequal(map_goal(1:2),close(k1,1:2))disp("Thelineofcyanusedlesstime.")Flag=true;breakelsecontinueendendfork2=1:length(close_1(:,1))ifisequal(map_start(1:2),close_1(k2,1:2))disp("Thelineofgreenusedlesstime.")Flag=true;breakelsecontinueendendendaxis([-2map_XYMAX+1-2map_XYMAX+1])
2、FindList.m
function[flag,targetInd]=FindList(m,open,close)%如果open为空，则一定不在open列表中ifisempty(open)flag=2;targetInd=[];%open不为空时，需要检查是否在open列表中elseforio=1:length(open(:,1))%在Open列表中ifisequal(m(1:2),open(io,1:2))flag=3;targetInd=io;return;%不在Open列表中elseflag=2;targetInd=[];endendend%在Close列表中foric=1:length(close(:,1))ifisequal(m(1:2),close(ic,1:2))%flag=1;targetInd=ic;return;%在Closelist中直接returnendendend
3、isObstacle.m
functionflag=isObstacle(m,obstacle)%判断节点m是否为障碍点，如果是就返为true，不是就返回falseforio=1:length(obstacle(:,1))ifisequal(obstacle(io,:),m(1:2))flag=true;return;endendflag=false;end
本文编辑：佚名
转载请注明出地址 http://www.smartcarf.com/smartcarxn/8430.html
