# Mobile Robot Path Planning Computer Science Essay

Path planning is one of the most important areas for mobile robotics research. Path planning can be defined as finding a continuous trajectory leading from the initial position of the mobile robot to its target position while avoiding collisions with obstacles along the way. Several methods are developed for mobile robot path planning. These are roadmap, cell decomposition, wall following and potential fields methods.

The potential field path planning is one of the most popular methods. This method was first developed by Khatib and Mampey in 1978. The potential field method involves modeling the robot as a particle moving under the influence of a potential field that is determined by the set of obstacles and the target position. The sum of potential is the minimum, when the robot is at the goal configuration, and is the maximum on obstacles. Everywhere else, the function is sloping down toward the goal configuration. The negative gradient of the potential function makes the robot to reach to the goal from any positions.

For the course project, This report consist of literature review on path planning and finally simulate (using C++) a point mobile robot using potential field method where the GUI will show the robot initial position, all obstacles and goal position in 2D environment. The robot will find a path avoiding those obstacles from its initial to goal configuration.

## List of Figures

Figure 1: Road-Map Path Planning: Visibility Graph 9

Figure 2: Road-Map Path Planning: Voronoi Diagram 10

Figure 3: MRI heart image: original image on the left, edge image in the middle, distance map on the right. 11

Figure 4: MRI heart image: from left to right, level set curves of the minimal action from previous figure; heart ventricle detection: to find the second end point, saddle point classification is used on the middle image (after filtering, only two of these point 11

Figure 5: The two paths The thresholded potential The centered minimal action 12

Figure 6: Path tracking in brain vessels in a MR-Angiographic volume. 13

Figure 7: Path planning using exact cell decomposition technique 16

Figure 8: Path planning using approximate cell decomposition 17

Figure 9: Path planning with the optimal channel and five trajectories based on 1) centers of gravity (dashed), 2) centers of inspheres (dashdotted), 3) centers of common faces (dotted), 4) middles of common faces of 5 convex fragments (thin solid) 18

Figure 10: Path planning using binary integer programming 19

Figure 11: Path planning using Voronoi Graph 19

Figure 12: Benchmark problems: 2D maze with typical solution paths given by PCD 21

Figure 13: The first and second rows show some optimized paths calculated for two edge points on the first quad. The third and fourth rows illustrate some optimized paths calculated for one edge point on the second quad and the other edge point on the fourth quad 22

Figure 14: Left: When a local path intercepts an obstacle, the cell is further decomposed and a new path is calculated. Right: The decomposition is stopped when all the local paths lie on free collision space or when the size of the cell reaches some fixed value. 22

Figure 15: Accessible directions of rectangular- and triangular-cell-based decomposition 23

Figure 16: Result path planned on (a) rectangular map and (b) triangular map. 24

Figure 17: Wall following approach 24

Figure 18: An example of an unknown 2.5D maze 26

Figure 19: Attractive potential 28

Figure 20: Repulsing Potential 28

Figure 21: Sum of potential 29

Figure 22: Collision avoidance 30

Figure 23: Dead-lock solutions 30

Figure 24: General control scheme for mobile robots 31

Figure 25: Result analysis 32

Figure 26: Simulation Result-1 33

Figure 27: Simulation Result-2 33

Figure 28: Simulation Result-3 34

## Introduction

## Background

A 7-Degree-of-Freedom (DOF) robotic manipulator will be studied for my research. Robotic manipulator having more than 6-DOF is termed as redundant that means the manipulator has excess DOFs than the required to control its end-effector’s position in space. Redundancy is a task dependent concept. Redundancy increases flexibility of the robotic arm in terms of its uses. The redundant degree of freedom can be used to enhance manipulability, to avoid singularity and collisions, to get more mechanical advantage and so on. The manipulator will be configured to form a mobile manipulator with a mobile platform, for application in remote control systems, in industrial automations, in the space exploration or in teleoperations. The motivation for this work is to plan a path for that 7-DOF interactive humanoid mobile manipulator. This work cover 10% of my original research.

## Path Planning

Path planning for a mobile robot can be define as finding a continuous trajectory leading from the initial position of the mobile robot to its target position. Path planning can be classified into the following two major categories:

Static

Dynamic

## Static (Path planning with complete information)

It deals with the known initial, target position and orientation in 2D or in 3D plane. A set of obstacles whose shapes, positions, and orientations in space are fully described, the task is to find a continuous path for the mobile robot from its initial position to the target position while avoiding collisions with obstacles along the way. It is assumed that the surfaces of the moving object and of the obstacles are algebraic

Because of full information is assumed, the whole operation of path planning is a one-time, off-line operation. The main difficulty is not in proving that an algorithm that would guarantee a solution exists, but in obtaining a computationally efficient scheme.

## Dynamic (Path planning with incomplete information)

In dynamic planning, only partial information is available about the obstacles. Path planning with incomplete information deals with the immediate surroundings for which information on the scene is available. Because of the unknown environment the path cannot be preplanned. For the mobile robot when it meets an obstacle in the three-dimensional space, it has an infinite number of possibilities for passing around the obstacle. It makes path planning difficult with unknown environment.

## Classification of Path-Planning Algorithms

There are two aspects to the classification of mobile robot algorithms:

Completeness (exact or heuristic)

Scope (global or local)

Exact algorithms either find a solution or prove that there is no solution. Exact algorithms are usually computationally expensive. In contrast, heuristic algorithms are aimed at generating a solution in a short time. Heuristic algorithms are important in engineering applications, while exact algorithms determine complexities of problems and algorithms.

Global algorithms take into account all the information in the environment, and they plan a motion from the start to the goal configuration. Local algorithms are designed to avoid obstacles in the vicinity of the robot and thus use information about nearby obstacles only. They are used when the start and goal are close together. Local methods are used as a component in a global planner or as a safety feature to avoid unexpected obstacles not present in the model of the environment but detected by sensors during motion execution.

## Path Planning Approaches

There are several methods have been developed for mobile robot path planning. Some are applicable to a wide variety of path planning problems, whereas others have a limited applicability. These methods are

Roadmap Approaches

Cell Decomposition

Wall Following

Potential Fields

Most of the path planning problem can be solved by using these approaches.

## Roadmap Approaches

In this approach a set of feasible motions, is retracted, reduced to, or mapped onto a network of one-dimensional lines. This approach is also called the retraction, roadmap, or highway approach. The search for a solution is limited to the network, and path planning becomes a graph searching problem. In this approach, path planning is done in three steps.

First, the robot is moved from its starting configuration to a point on the skeleton, using a canonical method.

Second, the robot is moved from the goal configuration to a point on the skeleton likewise and

In the third step the two points on the skeleton are connected using lines in the skeleton.

One can plan for robot path from Visibility Graph or from Voronoi Diagram.

## Visibility Graph

Connect initial and goal locations with all the visible vertices

Connect each obstacle vertex to every visible obstacle vertex

Remove edges that intersect the interior of an obstacle

Plan on the resulting graph

Figure 1: Road-Map Path Planning: Visibility Graph

## Voronoi Diagram

One can generate a path for the mobile robot using voroni diagram. The steps are

A Voronoi diagram in a configuration space with a polygonal C-obstacle region.

This diagram is a planar network of line segments and parabolic curves, which are the set of points equidistant from at least two obstacles.

The path generated by this method keeps the robot as far away from the obstacles as possible, unlike the visibility graph.

Figure 2: Road-Map Path Planning: Voronoi Diagram

## Review Paper

In [1] present path planning using skeleton approach. The motivation of skeleton approach is tracking path in 3D medical images for virtual endoscopy inside an anatomical object. An endoscopy consists in threading a camera inside the patient’s body in order to examine a pathology. The virtual endoscopy process consists in rendering perspective views along a user-defined trajectory inside tubular structures of human anatomy with CT or MR 3D images. It is a non-invasive technique which is very useful for learning and preparing real examinations, and it can extract diagnostic elements from images. This new method skips the camera and can give views of region of the body difficult or impossible to reach physically (e.g. brain vessels). A major drawback in general remains when the user must define all path points manually. For a complex structure the required interactivity can be very tedious. If the path is not correctly built, it can cross an anatomical wall during the virtual fly-through.

It detects the global minimum of an active contour model’s energy between two end points. Initialization is made easier and the curve is not trapped at a local minimum by spurious edges. The paper modify the “snake” energy by including the internal regularization term in the external potential term. Their method is based on finding a path of minimal length in a Riemannian metric. We then make use of a new efficient numerical method to find this shortest path. It is shown that the proposed energy, though based only on a potential integrated along the curve, imposes a regularization effect like snakes. They explore the relation between the maximum curvature along the resulting contour and the potential generated from the image.

Figure 3: MRI heart image: original image on the left, edge image in the middle, distance map on the right.

Figure 4: MRI heart image: from left to right, level set curves of the minimal action from previous figure; heart ventricle detection: to find the second end point, saddle point classification is used on the middle image (after filtering, only two of these point

In [2] In this paper we presented a fast and efficient algorithm that computes a 3D path of minimal energy. This is particularly useful in medical image understanding for guiding endoscopic viewing. This paper presents a new method to find minimal paths in 3D images, giving as initial data one or two endpoints. This paper extend 2D to 3D technique, and give new improvements of the approach that are relevant in 2D as well as in 3D. We also introduce several methods to reduce the computation cost and the user interaction. This work finds its motivation in the particular case of 3D medical images. We show that this technique can be efficiently applied to the problem of finding a centered path in tubular anatomical structures with minimum interactivity, and we apply it to path construction for virtual endoscopy. Synthetic and real medical images are used to illustrate each contribution.

They improved the front propagation equation by creating new algorithms which decrease the minimal path extraction computing cost, and reduce user interaction in the case of path tracking inside tubular structures. It showed that those techniques can be efficiently applied to the problem of finding a path in tubular anatomical structures for virtual endoscopy with minimum interactivity. In particular they extracted centered paths inside a CT dataset of the colon, and in a MR datasets of the brain vessels. They have proved the benefit of our method towards manual path construction, and skeletonization techniques, showing that only a few seconds are necessary to build a complete trajectory inside the body, giving only one or two end points and the image as inputs.

Figure 5: The two paths The thresholded potential The centered minimal action

Figure 6: Path tracking in brain vessels in a MR-Angiographic volume.

Aylward and Bullitt [3] proposed a curve skeletons tracking approach for intensity images. The Eigen vectors of the Hessian matrix are used to estimate the local orientation of the vessels, and a normal plane is iteratively updated to follow the vessel’s cross-section. The method generates curve skeletons that are thin and connected. However, it requires user interaction and a set of heuristics to handle branching and end points.

Deschamps and Cohen [4] relate the problem of finding curve skeletons to that of finding paths of minimal action in 3D intensity images, which can be found by first solving the Eikonal equation using the fast marching method and then following the gradient descent between two points selected by a user on the branch of interest. The method is fast and generates good quality curve skeletons but is limited to one branch at a time. For tree structures, it generates trajectories rather than curve skeletons [5].

Bitter et al. [6] proposed a penalized-distance algorithm to extract curve skeletons from volumetric data. A graph is first built from a coarse approximation of the 3D skeleton. Each edge of the graph is assigned a weight which is a function of both the Euclidean distance from a user defined source point and from the object’s boundary. The curve skeletons are then extracted using Dijkstra’s shortest path algorithm [7]. The parameters of the weight factor are specified heuristically for each object preventing the algorithm from automation. Siddiqi et al. [8] extracted curve skeletons by thinning the object’s medial surface, which has been computed by thresholding the negative average outward flux of the gradient field of the distance map. They have presented nice curve skeletons for vascular trees. However, the accuracy of computing curve skeletons becomes a function of the accurate computation of the object’s medial surface. In addition, the user has to choose a suitable threshold value to guarantee connected skeleton.

Zhou and Toga [9] proposed a volumetric sample points coding technique, in which each volumetric sample points is assigned two codes. One is the distance from the object’s boundary, while the other is the distance from a user defined point. The object is divided into a set of clusters, where each cluster is assumed to be the object cross section, whose center is the volumetric sample points of maximum distance from the boundary. curve skeletons are initially extracted as trajectories and then centered using some criteria. The algorithm guarantees connected paths. However, as the complexity of the object increases, the clusters are no longer normal to the CS, and hence centeredness is not guaranteed.

In this paper, we present a PDE-based framework for computing flight paths of tubular structures for VE. The proposed framework is an enhanced version of our recent work [10]. The key idea is to propagate from a medial volumetric sample points that belongs to the curve skeletons of the organ, wave fronts of different speeds. The first front propagates with a moderate speed to capture the organ’s topology, while the second one propagates much faster at medial volumetric sample points such that curve skeletons intersect the propagating fronts at those volumetric sample points of maximum positive curvatures, which are identified by solving an ordinary differential equation. Unlike previous methods, the new technique automatically and consistently handles complex anatomical structures with arbitrary number of loops.

## Cell Decomposition Approaches

The basic idea behind this method is that a path between the initial configuration and the goal configuration can be determined by subdividing the free space of the robot's configuration into smaller regions called cells. After this decomposition, a connectivity graph is constructed according to the adjacency relationships between the cells, where the nodes represent the cells in the free space, and the links between the nodes show that the corresponding cells are adjacent to each other. From the connectivity graph, a continuous path, or channel, can be determined by simply following adjacent free cells from the initial point to the goal point. The cell decomposition approach can be summarized as:

Divide space into simple regions called cells

Determine which open cells are adjacent and construct a connectivity graph

Find cells in which the initial and goal configuration (state) lie and search for a path in the connectivity graph to join them

From the sequence of cells found with an appropriate Search algorithm, compute a path within each cell

This method can be divided into two categories:

Exact cell decomposition,

Approximate cell decomposition

## Exact cell decomposition

The first step in this type of cell decomposition is to decompose the free space, which is bounded both externally and internally by polygons, into trapezoidal and triangular cells by simply drawing parallel line segments from each vertex of each interior polygon in the configuration space to the exterior boundary. Then each cell is numbered and represented as a node in the connectivity graph. Nodes that are adjacent in the configuration space are linked in the connectivity graph. A path in this graph corresponds to a channel in free space, which is illustrated by the sequence of striped cells. This channel is then translated into a free path by connecting the initial configuration to the goal configuration through the midpoints of the intersections of the adjacent cells in the channel.

In summary we can say

Decomposition of the free space into trapezoidal & triangular cells

Connectivity graph represents the adjacency relation between the cells

Figure 7: Path planning using exact cell decomposition technique

## Approximate cell decomposition

The approximate cell decomposition approach was first introduced by Lozano- Perez [11] and a general description is found in Latombe [12]. The robot's free space is decomposed into single regions, non-overlapping cells, such that a path between any two configurations in a cell can be generated. A graph representing the adjacency relation between the cells is then constructed. The nodes are the cells and two nodes are connected by a link if and only if the two corresponding cells are adjacent. The outcome is a sequence of cells from which a free path can be computed.

It uses a recursive method to continue subdividing the cells until one of the following scenarios occurs:

Each cell lies either completely in free space or completely in the C-obstacle region

An arbitrary limit resolution is reached.

Once a cell fulfills one of these criteria, it stops decomposing.

Both exact cell decomposition methods and approximate cell decomposition methods have advantages and disadvantages. The former are guaranteed to be complete, meaning that if a free path exists, exact cell decomposition will find it; however, the trade-off for this accuracy is a more difficult mathematical process. Approximate cell decomposition is less involved, but can yield similar, if not exactly the same, results as exact cell decomposition.

Figure 8: Path planning using approximate cell decomposition

## Review Paper

In [13] presents a new algorithm for path planning of mobile robots in known 3D environments using Binary Integer Programming.

## Solution Steps

Workspace tessellation: The Cfree is tessellated through the 3D Delaunay triangulation such that it is exactly decomposed into a set of tetrahedrons.

Optimal channel finding: Each tetrahedron is associated with a variable that is incorporated in a 0-1 Integer Programming model with an appropriate objective function. The solution gives a set of connected tetrahedrons forming a channel.

Path finding: The channel is further segmented into a number of convex fragments, and a safe path is calculated passing through the medians of the convex fragments

## Binary Integer Programming Algorithm:

Each tetrahedron is define as binary number (0 1)

If tetrahedron i is selected

Otherwise

The Start and Goal tetrahedrons (tS and tG, respectively) must be selected.

If any tetrahedron (other than tS and tG) is selected, two of its adjacent tetrahedrons must also be selected (continuity condition).

Each of the Start and Goal tetrahedrons must have only one selected adjacent tetrahedrons (loop avoidance condition).

To avoid looping, only two adjacent tetrahedrons of tetrahedrons with three free edges must be selected.

The BIP model for finding the optimal channel is :

Minimize

Where

T is the vector of variables

Figure 9: Path planning with the optimal channel and five trajectories based on 1) centers of gravity (dashed), 2) centers of inspheres (dashdotted), 3) centers of common faces (dotted), 4) middles of common faces of 5 convex fragments (thin solid)

Figure 10: Path planning using binary integer programming

Figure 11: Path planning using Voronoi Graph

Compare Results: A typical problem took 0.5 seconds to be solved by BIP and 1.23 seconds by Voronoi graph.

Paper [14] presents a new approach to path planning in high-dimensional static configuration spaces. The concept of cell decomposition is combined with probabilistic sampling to obtain a method called Probabilistic Cell Decomposition (PCD). The use of lazy evaluation techniques and supervised sampling in important areas leads to a very competitive path planning method. It is shown that PCD is easily scalable and applicable to many different kinds of problems. Experimental results show that PCD performs well under various conditions. Rigid body movements, maze like problems as well as path planning problems for chainlike robotic platforms have been solved successfully using the proposed algorithm.

PCD is based on the approximate cell decomposition technique, where all cells have a predefined shape and cell boundaries do not necessarily have any physical meaning, e.g. correspond to changes in motion constraints.

The basic PCD algorithm is given as

WHILE ( !success )

IF ( path <- findCellPath(G) )

IF ( checkPath(path) )

success <- true

ELSE

splitMixedCells

ELSE

x <- randomState(pOccCells)

IF ( !collision(x) )

splitMixedCells

Initially set kinit = kgoal = C.

Whenever there exists a channel in G connecting κinit with κgoal, check the states along a path through these cells connecting xinit with xgoal. If no collision occurs, a feasible path has been found. The cells are evaluated lazily. Otherwise, a cell that was marked as possibly free contains free and colliding states. Thus this cell has to be marked as known to be mixed and split up into possibly free and possibly occupied cells. If no such channel exists in G, check random states in the possibly occupied cells for collision. If the test is negative, a cell that was marked as possibly occupied contains free and colliding states and has to be relabelled and split up. In this manner the possibly occupied cells are refined until a path in G has been found. All states that are checked for collision, either in the sampling step or while path checking, that do not lie on the boundary between two cells, are stored as samples in the respective cell.

Figure 12: Benchmark problems: 2D maze with typical solution paths given by PCD

Maritza Bracho [15] developed a path planning algorithm based on an approximate cell decomposition of the workspace is presented. The free space of the robot is recursively decomposed into a set of non-overlapping cells through a real space renormalization procedure. The algorithm includes a previously calculated data base of heuristics defining the optimal paths that cross a cell between any two predefined edge points. The first step of the algorithm consists on the computation of a straight path from the initial configuration to the goal position. This initial proposed path is further recursively corrected in the following steps until a definitive path is obtained. The recursive process is stopped when the complete path lies on a free collision space or the size of the cell reaches some predefined value of resolution. The algorithm of path planning was experimentally tested on a workspace cluttered with thirty randomly distributed obstacles. In each case, with very little computational effort a good free collision path is calculated. The results indicate that the proposed path planning algorithm is very suitable for real time applications.

## The Algorithm:

The path planning algorithm consists of a recursive decomposition of the work-space into a set of non-overlapping cells through a real space renormalization procedure. The algorithm requires a previously established set of heuristics defining the optimal paths in a basic quad cell (2x2). This data base includes all possible optimized paths from any two edge points of a cell. Edge points are defined as crossing points between two adjacent cells. Figure 10 shows several examples of these optimized paths.

Figure 13: The first and second rows show some optimized paths calculated for two edge points on the first quad. The third and fourth rows illustrate some optimized paths calculated for one edge point on the second quad and the other edge point on the fourth quad

Figure 14: Left: When a local path intercepts an obstacle, the cell is further decomposed and a new path is calculated. Right: The decomposition is stopped when all the local paths lie on free collision space or when the size of the cell reaches some fixed value.

This [16] paper presents a novel approach for navigation of cleaning robots in an unknown workspace. To do so, we propose a new map representation method as well as a complete coverage navigation method. First, we discuss a triangular cell map representation which makes the cleaning robot navigate with a shorter path and increased flexibility than a rectangular cell map representation. Then, we propose the complete coverage navigation and map construction methods which enable the cleaning robot to navigate the complete workspace without complete information about the environment. Finally, we evaluate the performance of our proposed triangular cell map via the existing distance transform based path-planning method comparing it to that of the rectangular cell map. Also, we verify the effectiveness of the proposed methods through computer simulations.

Figure 15: Accessible directions of rectangular- and triangular-cell-based decomposition

In order to verify the efficiency of the triangular-cell-based map, we use the same example of workspace, which has four obstacles, for both the triangular-cell-based map and the rectangular cell-based map. In addition, the size of the workspace is assumed to be 16 m 25 m. Fig. a shows the result of the path from the starting point S to the target point G planned on the rectangular-cell-based map by the distance-transform-based path-planning method. In this figure, the navigation distance of the cleaning robot is 32.27 m. Fig. b shows the result of the path from the starting point S to the target point G planned on the triangular-cell-based map by the same method as Fig. 8. In this figure, the navigation distance of the cleaning robot is 30.23 m. From the results of Figs. 12, it is verified that the triangular cell-based map makes the navigation path shorter and more flexible.

Figure 16: Result path planned on (a) rectangular map and (b) triangular map.

## Wall Following Approach

The algorithm of the wall following can be describe as follows:

If the robot is too close to the wall, then turn right

If the robot is too far from the wall, then turn left.

Otherwise, go straight ahead.

Figure 17: Wall following approach

## Review Paper

The paper [17] describes two complementary algorithms developed for mobile robots operating within unknown, maze-type environments. The first is an environmental mapping and navigation algorithm which ensures complete coverage of a maze with apriori unknown wall locations, and the second a stochastic learning automaton approach for general obstacle avoidance within the maze. The environmental mapping and navigation algorithm employs a modified, wall following type scheme for exploring the maze and a variation of a flood-fill strategy for path planning to ensure complete coverage of the maze. A stochastic learning automaton provides a means of avoiding collisions with unstructured obstacles in the maze based upon a reward and penalty system which is used to adapt action probabilities. Both approaches are implemented within the UMBRA modular simulation and visualization framework in order to validate the algorithms prior to implementation in a RTLinux-based hardware platform.

One of the main advantages to using a stochastic learning automata (SLA) in addressing the obstacle avoidance problem is that this approach requires no apriori knowledge of the environment in which the robot will operate or any analytical foreknowledge of the function to be optimized. In the scenario of a robot trying to go to a destination without any prior information about the environment, an optimal path is almost impossible to compute. In these cases the probabilistic approach motivated by penalty or reward from the surrounding environment can be a good choice. It is possible for this type of approach to avoid local minima where other algorithms would become trapped. A learning automata is a sequential machine characterized by a set of internal states, input actions, state probability distributions, a reinforcement scheme, and an output function; and is connected via a feedback loop to the environment as shown in Figure 5.

Figure 18: An example of an unknown 2.5D maze

## Potential Field Approach

The potential field method involves modeling the robot as a particle moving under the influence of a potential field that is determined by the set of obstacles and the target destination. This method is usually very efficient because at any moment the motion of the robot is determined by the potential field at its location. Thus, the only computed information has direct relevance to the robot's motion and no computational power is wasted. It is also a powerful method because it easily yields itself to extensions. For example, since potential fields are additive, adding a new obstacle is easy because the field for that obstacle can be simply added to the old one.

The idea of using potential functions for obstacle avoidance was used in Khatib and Mampey [ 1978] and in Hogan [1985] for force control. It was also developed independently in Miyazaki and Arimoto [1984] and Pavlov and Voronin [1984]. This approach constructs a scalar function called the potential that has a minimum, when the robot is at the goal configuration, and a high value on obstacles. Everywhere else, the function is sloping down toward the goal configuration, so that the robot can reach the goal configuration from any other configuration by following the negative gradient of the potential. The high value of the potential prevents the robot from running into obstacles. The idea of potential field path planning can be summarized as,

Given: Position of robot, of all obstacles and of goal.

Robot is a particle under the influence of a potential field.

– Robot: positive charged particle,

– Goal: negative charged particle,

– Obstacles: positive charged particle.

## Attractive Potential Field

Attractive potential , Associated with

Where

Figure 19: Attractive potential

## Repulsing Potential

Repulsive potential , Associated with the Obstacles

Figure 20: Repulsing Potential

Sum of Potential field

The resulting forces

Figure 21: Sum of potential

## Review Paper

The paper [19] presents a hybrid path planning algorithm for the design of autonomous vehicles such as mobile robots. The hybrid planner is based on Potential Field method and Voronoi Diagram approach and is represented with the ability of concurrent navigation and map building. The system controller (Look-ahead Control) with the Potential Field method guarantees the robot generate a smooth and safe path to an expected position. The Voronoi Diagram approach is adopted for the purpose of helping the mobile robot to avoid being trapped by concave environment while exploring a route to a target. This approach allows the mobile robot to accomplish an autonomous navigation task with only an essential exploration between a start and goal position. Based on the existing topological map the mobile robot is able to construct sub-goals between predefined start and goal, and follows a smooth and safe trajectory in a flexible manner when stationary and moving obstacles

Figure 22: Collision avoidance

Figure 23: Dead-lock solutions

The paper [20] focuses on development of algorithms with the integration of path planning by potential field method and Monte Carlo localization method for navigation, obstacle avoidance, and localization of the mobile robot in a dynamic environment like in manufacturing industry. The path planning algorithms has divided into two submodules, one is global path planning which uses visibility graph with A* search method and another is local path planning which uses potential field method to avoid the obstacles. The image processing is used to get the working environment information from the global camera. The robot control program uses MCL algorithms with gradient path planning for continuous localization. User-friendly path planning software PMADE V 2.0 is developed. PMADE v 2.0 is used for image processing, path lanning, simulation of robot navigation, real robot manual control and real robot automatic control for navigation in dynamic environment from position data of the simulator.

Figure 24: General control scheme for mobile robots

The algorithms are designed for the mobile robot working in manufacturing industry environment with machinery parts as the moving objects. The potential field technique is used for path planning in dynamic environment. The data we get from path planning in terms of x, y and theta position i.e. in terms of goals (position data). In this section we are focusing on how the position data from path planning module use to localize the mobile robot in the dynamic environment and the operation of the simulator.

Figure 25: Result analysis

## Simulations

Mobile robot path is simulated using C++ language. The GUI can take input of robot initial and final position. It can also take input of the co-ordinates of three obstacles. After defining the robot initial, final and all obstacles positions and then pressing plot button, the GUI shows the robot path from initial to final while avoiding obstacles. Figures 13, 14 and 15 show simulation result.

Figure 26: Simulation Result-1

Figure 27: Simulation Result-2

Figure 28: Simulation Result-3

## Conclusions

A motion planner is an essential component of a robot that interacts with the environment; without it a human operator has to constantly specify the motion for the robot. A significant amount of research has been done on the development of efficient motion-planning algorithms. In this report path planning is simulated based on potential field method. Simulation result shows the effectiveness of the

method.

### Share This Essay

To share this essay on Reddit, Facebook, Twitter, or Google+ just click on the buttons below:

### Request Removal

If you are the original writer of this essay and no longer wish to have the essay published on the UK Essays website then please click on the link below to request removal:

Request the removal of this essay.

### More from UK Essays

- Free Essays Index - Return to the FREE Essays Index
- More Computer Science Essays - More Free Computer Science Essays (submitted by students)
- Computer Science Essay Writing Service -find out more about how we can help you
- Example Computer Science Essays - See examples of Computer Science Essays (written by our in-house experts)