Evolving A Diverse Collection of Robot Path Planning Problems
Authors:
- D.A. AshlockDAD.A. Ashlock
- T.W. ManikasTMT.W. Manikas
- K. AshenayiKAK. Ashenayi
- 22 September 2006
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 1089778X,p. 1837-1844
Abstract
This study presents an evolutionary computation system that can generate grid robot path planning problems. An evolvable cellular representation that specifies how to build a PPP is used. Also presented is a technique for taxonomizing path planning problems so that the vast number of problems that can be generated with the evolutionary computation system can be subsequently winnowed into a collection of substantially different problems of specified size. In this study the most difficult path planning problems, according to three different criteria, are evolved and those results are used to demonstrated the taxonomic technique. The hardness criteria are (i) the minimum number of turns a robot must make, (ii) the minimum number of forward moves it must make, and (iii) the sum of these quantities. A dynamic programming algorithm is used to compute these quantities for a given path planning program. The technique can be generalized to find cases of a specified hardness. The size of the board and maximum number of obstacles used are transparently specifiable.Keywords
This publication has 24 references indexed in Scilit:
- A fast path planning by path graph optimizationIEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans, 2003
- Realization of robust controllers in evolutionary robotics: a dynamically-rearranging neural network approach2003
- Perception-based genetic algorithm for a mobile robot with fuzzy controllers2003
- Cooperative search and rescue with a team of mobile robots2002
- Evolving a modular neural network-based behavioral fusion using extended VFF and environment classification for mobile robot navigationIEEE Transactions on Evolutionary Computation, 2002
- Planning multiple paths with evolutionary speciationIEEE Transactions on Evolutionary Computation, 2001
- A distributed architecture for autonomous navigation of robots2000
- Automatic Definition of Modular Neural NetworksAdaptive Behavior, 1994
- Gross motion planning—a surveyACM Computing Surveys, 1992
- Robot Motion Planning1991