路径规划算法-基于遗传算法实现的路径规划算法.zip

Rahul Kala, Code Repository http://rkala.in/codes.html

Code for Robot Path Planning using Genetic Algorithms

Rahul Kala

Robotics and Artificial Intelligence Laboratory,

Indian Institute of Information Technology, Allahabad

Devghat, Jhalwa, Allahabad, INDIA

Email: [email protected]m

materials in the text; creation of derivatives and their publication; and sharing the code publically is permitted without permission.

Please cite the work in all materials as: R. Kala (2014) Code for Robot Path Planning using Genetic Algorithms, Indian Institute of Information

Technology Allahabad, Available at: http://rkala.in/codes.html

1. Background

The code provided with this document uses Genetic Algorithm for robot motion planning. Assume that you have a

robot arena with an overhead camera as shown in Figure 1. The camera can be easily calibrated and the image

coming from the camera can be used to create a robot map, as shown in the same figure. This is a simplistic

The same camera can also be used to capture the location of the robot at the start of the planning and also as the

For simplicity, the robot is taken as a point-sized object. This enables a quick implementation and understanding,

without delving into the libraries for collision detection and concepts of multi-dimensional configuration spaces.

2. Problem Solving using Genetic Algorithms

The readers should please familiarize themselves with the Genetic Algorithms (GA) before reading this tutorial. For

this tutorial GA would be used as a standard optimization algorithm. As an optimization algorithm, the GA does not

require any information about the derivatives for functioning. Stress is given in this tutorial on how to model the

Rahul Kala, Code Repository http://rkala.in/codes.html

that objective function (along with their bounds). Let a path be characterized by a fixed number of points in the

robotic map. In order to make some path from this set of points, we start from the source and connect it to the first

point by a straight line. The first point is connected to the second point by a straight line, and so on. At the end the

last point is connected to the goal. The objective function is the length of this path. A heavy penalty is added if any

part of the path lies inside the obstacle, while the penalty is proportional to the length of the path inside the obstacle.

3. How to Execute and Parameters

In order to execute the code you need to execute the file 'astart.m'. First make a new bitmap file and draw any map

on it, over which you need to execute the algorithm. Paint or any other simple drawing tool can be used. Make sure

you save the file as a BMP. Place the file in the project folder. You may prefer to open any of the supplied maps and

re-draw them. Change the name of the map file in the code to point out to the map that you created. Supply the

source and the goal positions. You can use paint or any other drawing utility which displays the pixel positions of

the points, to locate the source and goal on your drawn map.

results, depending upon the settings used. Click on the image to get the robot path. The path length and execution

time are given at the console.