?About the author: A Matlab simulation developer who loves scientific research. He cultivates his mind and improves his technology simultaneously.
For code acquisition, paper reproduction and scientific research simulation cooperation, please send a private message.
Personal homepage: Matlab Research Studio
Personal credo: Investigate things to gain knowledge.
For more complete Matlab code and simulation customization content, click
Intelligent optimization algorithm Neural network prediction Radar communication Wireless sensor Power system
Signal processing Image processing Path planning Cellular automaton Drone
Content introduction
With the continuous development of artificial intelligence and robotics technology, robots are increasingly used in various fields. The robot path planning algorithm is one of the key technologies for robot navigation and movement. In practical applications, A-star algorithm and Dijkstra algorithm are two commonly used path planning algorithms. This article will introduce the robot path planning algorithm process based on A-star and Dijkstra algorithms.
The A-star algorithm is a heuristic search algorithm commonly used in fields such as graphics, game development, and robot path planning. The basic idea is to evaluate the cost of each node through a heuristic function and select the optimal path. The process of A-star algorithm is as follows:
-
Initialize the start point and end point, and add the start point to the open list.
-
Select the node with the smallest cost from the open list as the current node and add it to the closed list.
-
Traverse the adjacent nodes of the current node, calculate their costs, and update their parent nodes and costs.
-
Add adjacent nodes to the open list and repeat steps 2 and 3 until the end point is found or the open list is empty.
The advantage of the A-star algorithm is that it can quickly find the optimal path and is suitable for complex environments. But it also has some disadvantages, such as consuming a lot of computing resources when processing large-scale maps.
Another commonly used path planning algorithm is Dijkstra’s algorithm, which is a shortest path algorithm for undirected graphs. The basic idea of Dijkstra’s algorithm is to continuously update the shortest path from the starting point to each node until the end point is found. The process is as follows:
-
Initialize the starting point and end point, and add the starting point to the to-be-visited list.
-
Select the node in the to-be-visited list that is closest to the starting point and mark it as visited.
-
Update the distance of nodes adjacent to the current node and add them to the to-be-visited list.
-
Repeat steps 2 and 3 until the end point is found or the list to be visited is empty.
The advantage of Dijkstra’s algorithm is that it can find the shortest path and is not affected by heuristic functions. But it also has some disadvantages, such as consuming a lot of memory when processing large-scale maps.
The robot path planning algorithm process based on A-star and Dijkstra algorithms can choose the appropriate algorithm according to actual needs. In practical applications, we can choose appropriate algorithms based on the complexity of the map and the limitations of computing resources to achieve efficient path planning. I hope this article can help readers better understand the process and characteristics of the robot path planning algorithm.
Part of the code
clear</code><code>close all </code><code>clc</code><code>%% 1. Initial settings</code><code>map_range = struct('x_range',20 ,'y_range',20); % 1-20</code><code>obstacles = CreateObstacles(20);</code><code>goal = [20,20];</code><code>start = [1,1];</code><code>OPEN = zeros(map_range.x_range,map_range.y_range); % If in OPEN, it is 1</code><code>CLOSED = zeros(map_range.x_range,map_range .y_range); % If it is in CLOSED, it is 1</code><code>PARENT = cell(map_range.x_range,map_range.y_range); % Store coordinates (x, y)</code><code>g = Inf (map_range.x_range,map_range.y_range);</code><code>prior = Inf(map_range.x_range,map_range.y_range); % Breadth first, that is, first search for the node with the longest time in OPEN and the priority of the new node Set to maximum</code><code>p = 0;</code><code>% % plot</code><code>% plot(obstacles(:,1),obstacles(:,2),'k *',start(1),start(2),'g*',goal(1),goal(2),'r*'); hold on;</code><code>% grid on;</code> code><code>fig = figure('Name','bfs');</code><code>% Set color map</code><code>cmap = [1 1 1; ...% 1 - white - clear cell </code><code> 0 0 0; ...% 2 - black - obstacle</code><code> 1 0 0; ...% 3 - red = visited </code><code> 0 0 1; ...% 4 - blue - on list </code><code> 0 1 0; ...% 5 - green - start </code><code> 1 1 0; ...% 6 - yellow - goal</code><code> 1 0 1]; % 7 - pink - path </code><code>colormap(cmap);</code><code>?</code><code> end </code><code>% % drawing</code><code>% [row_CLOSED,col_CLOSED] = find(CLOSED==1);</code><code>% [row_OPEN,col_OPEN] = find(OPEN= =1);</code><code>% plot(row_OPEN',col_OPEN','bh'); hold on;</code><code>% plot(row_CLOSED',col_CLOSED','mh'); hold on;</code><code>% drawnow;</code><code>% pause(0.5);</code><code> [row_CLOSED,col_CLOSED] = find(CLOSED==1);</code> <code> for i = 1:length(row_CLOSED)</code><code> map(row_CLOSED(i),col_CLOSED(i)) = 3;</code><code> end</code><code> [ row_OPEN,col_OPEN] = find(OPEN==1);</code><code> for i = 1:length(row_OPEN)</code><code> map(row_OPEN(i),col_OPEN(i)) = 4 ;</code><code> end</code><code> map(start(1),start(2)) = 5;</code><code> map(goal(1),goal(2)) = 6;</code><code> image(map);</code><code> set(gca,'YDir','normal');</code><code> drawnow;</code><code>% pause(0.5);</code><code> frame = getframe(fig); </code><code> im{idx}=frame2im(frame);</code><code> idx = idx + 1 ;</code><code>end</code><code>%% 3. Extract path</code><code>path = extractPath(PARENT,start,goal);</code><code>% plot( path(1,:),path(2,:),'b-'); hold on;</code><code>for i = 1:length(path)</code><code> map(path( 1,i),path(2,i)) = 7;</code><code>end</code><code>image(map);</code><code>set(gca,'YDir', 'normal');</code><code>frame = getframe(fig); </code><code>im{idx}=frame2im(frame);</code><code>%% 4. Make gif</code><code>filename = 'BreadthFirstSearching.gif'; % Specify the output file name is not case sensitive</code><code>for idx = 1:length(im)</code><code> [A, map] = rgb2ind(im{idx},256);</code><code> if idx == 1</code><code> imwrite(A,map,filename,'gif','LoopCount',Inf, 'DelayTime',0.1);</code><code> else</code><code> imwrite(A,map,filename,'gif','WriteMode','append','DelayTime',0.1);</code><code> end</code><code>end
Operation results
References
[1] Zhou Yuhang, Wang Wenming, Li Zebin, et al. Research on application of mobile robot path planning based on A-star algorithm [J]. Computer Knowledge and Technology: Academic Edition, 2020, 16(13):4.DOI:CNKI:SUN: DNZS.0.2020-13-001.
[2] Zhang Mengqi, Ye Yulin, Zhang Yujie, et al. A robot path planning method based on the A-star penalty control optimization algorithm. CN202211285517.0[2023-11-11].
[3] Pan Chenghao, School of Economics and Management, North China University, Taiyuan, Shanxi, et al. Mobile robot path planning based on relaxed Dijkstra algorithm [J]. Computers and Modernization, 2016(11):5.DOI:10.3969/ j.issn.1006-2475.2016.11.004.
Some theories are quoted from online literature. If there is any infringement, please contact the blogger to delete it
Follow me to receive massive matlab e-books and mathematical modeling materials
Private message complete code, paper reproduction, journal cooperation, paper tutoring and scientific research simulation customization
1 Improvements and applications of various intelligent optimization algorithms
Production scheduling, economic scheduling, assembly line scheduling, charging optimization, workshop scheduling, departure optimization, reservoir scheduling, three-dimensional packing, logistics location selection, cargo space optimization, bus scheduling optimization, charging pile layout optimization, workshop layout optimization, Container ship stowage optimization, water pump combination optimization, medical resource allocation optimization, facility layout optimization, visible area base station and drone site selection optimization
2 Machine learning and deep learning
Convolutional neural network (CNN), LSTM, support vector machine (SVM), least squares support vector machine (LSSVM), extreme learning machine (ELM), kernel extreme learning machine (KELM), BP, RBF, width Learning, DBN, RF, RBF, DELM, XGBOOST, TCN realize wind power prediction, photovoltaic prediction, battery life prediction, radiation source identification, traffic flow prediction, load prediction, stock price prediction, PM2.5 concentration prediction, battery health status prediction, water body Optical parameter inversion, NLOS signal identification, accurate subway parking prediction, transformer fault diagnosis
2. Image processing
Image recognition, image segmentation, image detection, image hiding, image registration, image splicing, image fusion, image enhancement, image compressed sensing
3 Path planning
Traveling salesman problem (TSP), vehicle routing problem (VRP, MVRP, CVRP, VRPTW, etc.), UAV three-dimensional path planning, UAV collaboration, UAV formation, robot path planning, raster map path planning , multimodal transportation problems, vehicle collaborative UAV path planning, antenna linear array distribution optimization, workshop layout optimization
4 UAV applications
UAV path planning, UAV control, UAV formation, UAV collaboration, UAV task allocation, and online optimization of UAV safe communication trajectories
5 Wireless sensor positioning and layout
Sensor deployment optimization, communication protocol optimization, routing optimization, target positioning optimization, Dv-Hop positioning optimization, Leach protocol optimization, WSN coverage optimization, multicast optimization, RSSI positioning optimization
6 Signal processing
Signal recognition, signal encryption, signal denoising, signal enhancement, radar signal processing, signal watermark embedding and extraction, EMG signal, EEG signal, signal timing optimization
7 Power system aspects
Microgrid optimization, reactive power optimization, distribution network reconstruction, energy storage configuration
8 Cellular Automata
Traffic flow, crowd evacuation, virus spread, crystal growth
9 Radar aspect
Kalman filter tracking, track correlation, track fusion
The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 57515 people are learning the system