Multiple Objective Genetic Algorithms for Path-planning Optimization in Autonomous Mobile Robots

Abstract

This paper describes the use of a genetic algorithm (GA) for the problem of offline point-to-point autonomous mobile robot path planning. The problem consists of generating “valid” paths or trajectories, for an Holonomic Robot to use to move from a starting position to a destination across a flat map of a terrain, represented by a two-dimensional grid, with obstacles and dangerous ground that the Robot must evade. This means that the GA optimizes possible paths based on two criteria: length and difficulty. First, we decided to use a conventional GA to evaluate its ability to solve this problem (using only one criteria for optimization). Due to the fact that we also wanted to optimize paths under two criteria or objectives, then we extended the conventional GA to implement the ideas of Pareto optimality, making it a multi-objective genetic algorithm (MOGA). We describe useful performance measures and simulation results of the conventional GA and of the MOGA that show that both types of GAs are effective tools for solving the point-to-point path-planning problem.

  1. Oscar Castillo, Leonardo Trujillo and Patricia Melin. Multiple Objective Genetic Algorithms for Path-planning Optimization in Autonomous Mobile Robots. Soft Comput. 11(3):269–279, 2006. URL, DOI BibTeX

    @article{Castillo:2006:MOG:1178398.1178406,
    	author = "Castillo, Oscar and Trujillo, Leonardo and Melin, Patricia",
    	title = "Multiple Objective Genetic Algorithms for Path-planning Optimization in Autonomous Mobile Robots",
    	journal = "Soft Comput.",
    	issue_date = "October 2006",
    	volume = 11,
    	number = 3,
    	month = "",
    	year = 2006,
    	issn = "1432-7643",
    	pages = "269--279",
    	numpages = 11,
    	url = "http://dx.doi.org/10.1007/s00500-006-0068-4",
    	doi = "10.1007/s00500-006-0068-4",
    	acmid = 1178406,
    	publisher = "Springer-Verlag",
    	address = "Berlin, Heidelberg",
    	keywords = "Autonomous robots, Genetic algorithms, Multiple objective optimization, Path planning"
    }
    

Additional Info

Bibtex:
J-2007-1.bib
PDF:
Multiple Objective Genetic Algorithms for Path-planning Optimization in Autonomous Mobile Robots.pdf

Download

Download as PDF
Read 6964 times