## A list,

The “D* algorithm” is named after Dynamic A Star, originally introduced by Anthony Stentz in Optimal and Efficient Path Planning for Partially Known Environments. It is a heuristic path search algorithm, suitable for the unknown surrounding environment or dynamic change of the surrounding environment.

Similar to algorithm A, D-STAR searches the path nodes in the scene by maintaining A priority queue (OpenList). The difference is that D does not start the search from the starting point, but from the target point, and starts the search by placing the target point in the OpenList. Until the node of the current position of the robot is out of the queue (of course, if the state of a node in the middle changes dynamically, it needs to find the path again, so it is a dynamic path finding algorithm).

2.1 Symbols This part mainly introduces some symbols used in this paper and their meanings. In this paper, waypoints in the map are represented by states, and each State contains the following information:

Backpointer: pointer to a previous state that is the parent of the current state. The current state is called the descendant of the pointer to state. The target state has no Backpointer. (After the path search is completed, the robot can move step by step to the GoalState through backpointer and the state where the robot is located. GoalState is later represented by G), B (X) =Y indicates that X’s father is Y.

Tag: indicates the state status, including New, Open, and Closed. New indicates that the state has never been added to the Openlist. Open indicates that the state is in the Openlist.

H (X) : cost function estimate, representing the cost estimate from the current State to G.

K (X) : The State with the smallest K value is located in the queue head. For the State X on the Openlist, K (X) represents the minimum cost H (X) from X to G after X is placed in the Openlist, which can be simply understood as. K (X) divides the State X in Openlist into two different states. One State is Raise (if K (X)

1.2 The key to the search described by the algorithm is the state transfer process, that is, the search process from G to the position of the robot. This transfer process is realized by constantly taking out the state with the minimum K value from the current OpenList. Whenever a state is removed from the OpenList, It passes overhead to its neighbor states, which are placed in Openlist, and the loop continues until the robot’s state is Closed or Openlist is empty (meaning there is no path to G).

The algorithm mainly consists of two functions, process-state and modify-cost. The former is used to calculate the optimal path to target G, and the latter is used to change the Cost C (X,Y) between the two states and place the affected State in Openlist.

The main Process of the algorithm: at the beginning, t (Tag) of all states is set as New, H (G) is set as 0, and G is placed in OpenList. Then the process-state function is continuously executed until the state X of the robot is queued out from OpenList. You can then point to target G by pressing backpointer on the robot’s current state. When a newly detected obstacle is found during movement, the modify-cost function is immediately called to correct the path overhead in C (°) and replace the affected state in openList. Let Y represent the state where robot finds the obstacle. By constantly calling process-state until kmin≥H (Y), it indicates that the change of path cost has been propagated to Y, and at this point, the construction of the new path is completed.

In the figure above, L1-L3 indicates that X with the lowest K value is removed from OpenList. If X is Lower, then its path cost is optimal.

In l8-L13, all adjacency states of X are checked to see if the path cost can be lower. The adjacency state of New is assigned an initial path cost value, and the cost change is propagated to every adjacency state Y of backpointer to X (regardless of whether the New cost is larger or smaller than the original cost). That is, as long as you’re pointing to X, your path cost has to change as the path cost of X changes. There may be a case where Y can reach the target through other states other than X and the path cost is lower because the path cost of X changes too much. This is not dealt with in L8-13, but put in the subsequent process-state function for Y. When processing Y, Backpointer points to the state with the least overhead of the surrounding path. If the State of X’s neighbor State is New, backpointer of its neighbor State points to X. All states with variable path overhead are processed in Openlist, propagating the change to the adjacent states. In the above discussion, X is in the Lower state, and in the next discussion, X is in the Raise state.

If X is Raise, its path cost H may not be optimal. In L4-L7, the path cost of X is optimized by the node in its neighbor state that already has the optimal cost (that is, H (Y) ≤kold). If there is a shorter path, the backpointer of X is directed to its neighbor. In L15-L18, the cost change is propagated to the neighbor state with state New. If X can minimize the path overhead of a neighbor state whose Backpointer does not point to X, that is, the distance between Y and target G is shorter through X, but the backpointer of Y does not point to X, in this case, X can be re-placed in Openlist to optimize Y. In L23-25, if X can reduce path overhead with a neighbor stateY whose state is closed that is not optimal, then Y is placed back in Openlist.

In modify-cost, C (X,Y) is updated and X is re-placed in Openlist. When X is propagated through process-state, the cost of Y is calculated, and H (Y) = H (X)+ C (X,Y).

2 algorithm Summary Compared with A-STAR algorithm, the main feature of D-STAR is to search the path from the target position to the starting position. When the object runs from the starting position to the target position and finds A new obstacle in the path, the path nodes within the range between the target position and the new obstacle are found. New obstacles do not affect its path to the target. The new obstacle only affects the path of nodes in the range between the object’s position and the obstacle. At this point, the nodes around the new obstacle are added to the Openlist for processing and then propagated to the location of the object, which can minimize the computational overhead. I personally feel that the process of path search is actually similar to Dijkstra algorithm. In a-Star algorithm, F (n)= G (n)+ H (n), h(n) is not reflected in D-Star, and the path search does not have the sense of direction that A-star has, that is, the feeling of searching towards the target. This kind of search is more of a search that spreads from the target location to all directions until the starting location is included in the search, more like Dijkstra algorithm.

## Ii. Source code

``````function varargout = A_GUI(varargin)
% A_GUI MATLAB code for A_GUI.fig
%      A_GUI, by itself, creates a new A_GUI or raises the existing
%      singleton*.
%
%      H = A_GUI returns the handle to a new A_GUI or the handle to
%      the existing singleton*.
%
%      A_GUI('CALLBACK',hObject,eventData,handles,...) calls the local
%      function named CALLBACK in A_GUI.M with the given input arguments.
%
%      A_GUI('Property'.'Value',...). creates anew A_GUI or raises the
%      existing singleton*.  Starting from the left, property value pairs are
%      applied to the GUI before A_GUI_OpeningFcn gets called.  An
%      unrecognized property name or invalid value makes property application
%      stop.  All inputs are passed to A_GUI_OpeningFcn via varargin.
%
%      *See GUI Options on GUIDE's Tools menu.  Choose "GUI allows only one % instance to run (singleton)".
%

% Edit the above text to modify the response to help A_GUI

% Begin initialization code - DO NOT EDIT
gui_Singleton = 1;
gui_State = struct('gui_Name',       mfilename, ...
'gui_Singleton',  gui_Singleton, ...
'gui_OpeningFcn', @A_GUI_OpeningFcn, ...
'gui_OutputFcn',  @A_GUI_OutputFcn, ...
'gui_LayoutFcn', [],...'gui_Callback'[]);if nargin && ischar(varargin{1})
gui_State.gui_Callback = str2func(varargin{1});
end

if nargout
[varargout{1:nargout}] = gui_mainfcn(gui_State, varargin{:});
else
gui_mainfcn(gui_State, varargin{:});
end
% End initialization code - DO NOT EDIT

% --- Executes just before A_GUI is made visible.
function A_GUI_OpeningFcn(hObject, eventdata, handles, varargin)
% This function has no output args, see OutputFcn.
% hObject    handle to figure
% eventdata  reserved - to be defined in a future version of MATLAB
% handles    structure with handles and user data (see GUIDATA)
% varargin   command line arguments to A_GUI (see VARARGIN)

% Choose default command line output for A_GUI
handles.output = hObject;

% Update handles structure
guidata(hObject, handles);

% UIWAIT makes A_GUI wait for user response (see UIRESUME)
% uiwait(handles.figure1);

% --- Outputs from this function are returned to the command line.
function varargout = A_GUI_OutputFcn(hObject, eventdata, handles)
% varargout  cell array for returning output args (see VARARGOUT);
% hObject    handle to figure
% eventdata  reserved - to be defined in a future version of MATLAB
% handles    structure with handles and user data (see GUIDATA)

% Get default command line output from handles structure
varargout{1} = handles.output;

% --- Executes on button press in pushbutton1.
function pushbutton1_Callback(hObject, eventdata, handles)
% hObject    handle to pushbutton1 (see GCBO)
% eventdata  reserved - to be defined in a future version of MATLAB
% handles    structure with handles and user data (see GUIDATA)

% set up color map forDisplay Generates the global Cmap;
global map;
global n_r;
global n_c;
global state;

cmap = [1 1 1; . %1- White - Accessible0 0 0; . %2- Black. - With a handicap0 0.8 0; . %3- Green - Searched0 0.4 0; . %4- Pink. - Searching0 1 1; . %5- Light blue - Starting point1 1 0; . %6- Yellow - Target point0 0 1];   % 7- Blue - Final path colormap(cmap); % Generate random mapmap = zeros(n_r,n_c);
randmap = rand(n_r,n_c);
for i = 2:(sub2ind(size(randmap),n_r,n_c)- 1)
if (randmap(i) >= 0.75)
map(i) = 2;
end
end

map(1.1) = 5; % start_coords Specifies the starting pointmap(n_r, n_c) = 6; % dest_coords image(1.5.1.5.map);
grid on;
axis image;
set(handles.text5,'string'.'Random map generated');

% --- Executes on button press in pushbutton2.
function pushbutton2_Callback(hObject, eventdata, handles)
% hObject    handle to pushbutton2 (see GCBO)
% eventdata  reserved - to be defined in a future version of MATLAB
% handles    structure with handles and user data (see GUIDATA)% Search for the best path global n_r;
global n_c;
global cmap;
global map;
global state;

nrows = n_r;
ncols = n_c;
start_node = sub2ind(size(map), 1.1); The %sub2ind() function computes the linear number of an element in a matrix.2*2Matrix [1 3; ,1It was the first one,5Is the second %5 7].3Is the third,7Dest_node = sub2ind(size()map), n_r, n_c);
% Initialize distance arrayDistanceFromStart = Inf(nrows,ncols); distanceFromStart(start_node) =0 ;
% For each grid cell this arrayHolds the index of its parent for each grid cell; parent = zeros(nrows, nCOLs); % Main Loopwhile true
% Draw current map
map(start_node) = 5;
map(dest_node) = 6;
image(1.5.1.5.map); grid on; % Grid Axis image; Drawnow; % Find the node with the minimum distance [min_dist, current] = min(distanceFromStart(:));if((current = = dest_node) | | isinf (min_dist)) % = TF isinf (A) returns an array as A size, if an element is A of the inf (infinite), the corresponding element is in the TF1Otherwise, the corresponding element in TF is0.break; end; % search center index coordinates: current, % search center distance from the start point: min_dist % these two values will be used later.map(current) = 3; distanceFromStart(current) = Inf; [i, j] = ind2sub(size(distanceFromStart), current); % index changed to coordinate neighbor = [I- 1,j;
i+1,j;
i,j+1;
i,j- 1];
outRangetest = (neighbor(:,1) <1) + (neighbor(:,1)>nrows)+(neighbor(:,2) <1) + (neighbor(:,2)>ncols);
locate = find(outRangetest>0); % returns outRangetest greater than0The corresponding linear index value of the element. neighbor(locate,:)=[]; neighborIndex = sub2ind(size(map),neighbor(:,1),neighbor(:,2));
for i=1:length(neighborIndex)
if (map(neighborIndex(i))~=2) && (map(neighborIndex(i))~=3 && map(neighborIndex(i))~= 5)
map(neighborIndex(i)) = 4;
if (distanceFromStart(neighborIndex(i))>= min_dist + 1 )
distanceFromStart(neighborIndex(i)) = min_dist+1;
parent(neighborIndex(i)) = current;
% pause(0.02);
end
end
end
end
Copy the code``````

Version: 2014 a