In this paper we show a relationship between artificial potential field (APF) based motion planning/navigation, and constrained optimi zation. We then present a simple genetic hill climbing algorithm (SGHC), which is used to navigate a point robot through an environ ment using the APF approach. We compare SGHC with steepest descent hill climbing (SDHC). In SDHC, candidate moves are evaluated within a 360-degree radius and the best candidate is selected by the robot. One would think that SGHC would be at a disad vantage ; however, the performance of SGHC is comparable with SDHC. SGHC has an advantage in that it is capable of evolving (learning) the appropriate step size as well as the appropriate angle of movement.
Holland, J.H.Adaptation in Natural and Artificial Systems , University of Michigan Press, Ann Arbor, MI,, 1975.
2.
Michalewicz, Zbigniew.Genetic Algorithms + Data Structures = Evolution Programs, Second Edition, Springer-Verlag Artificial Intelligence Series, 1994.
3.
Fogel, D.B. "A Comparison of Evolutionary Programming and Genetic Algorithms on Selected Constrained Optimization Problems." SIMULATION, Vol. 64, No. 6, pp 399-406, 1995.
4.
Schwefel, Hans-Paul. "On the Evolution of Evolutionary Computation." Computational Intelligence: Imitating Life, Jacek M. Zurada , Robert J. Marks II and Charles J. Robinson, editors, IEEE Press , 1994.
5.
Montana, David J. and Davis, Lawrence. "Training Feedforward Neural Networks Using Genetic Algorithms." Proceedings of IJCAI-89, Vol. 1, pp 762-767, 1990.
6.
Corne, D., Ross, P., and Fang, H.L. "Fast Practical Evolutionary Timetabling." Proceedings of the AISB Workshop on Evolutionary Computation, Springer Verlag, 1994.
7.
Fogel, Lawrence J. "Evolutionary Programming in Perspective : The Top-Down View." Computational Intelligence: Imitating Life , Jacek M. Zurada, Robert J. Marks II and Charles J. Robinson , editors, IEEE Press, 1994.
8.
Lucasius, C.B. , Blommers, J.J., Buydens, L.M.C. and Kateman G. "A Genetic Algorithm for Conformational Analysis of DNA." Handbook of Genetic Algorithms , L. Davis, editor, Van Nostrand Reinhold, New York, 1991.
9.
Homaifar, A., Qi, C.X. and Lai, S.H. "Constrained Optimization Via Genetic Algorithms ." SIMULATION, Vol. 62, No. 4, pp 242-254, 1994.
10.
Dozier, G. , Bowen, J., Homaifar, A. and Esterline, A. "Solving Randomly Generated Static and Dynamic Fuzzy Constraint Networks Using Microevolutionary Hill-Climbing." Intelligent Automation and Soft Computing, Vol. 3, No. 1, pp 51-62, AutoSoft Press , 1997.
11.
Ashiru, I. and Czarnecki, C. (1995). "Optimal Motion Planning for Mobile Robots Using Genetic Algorithms." Proceedings of the 1995 IEEE/IAS International Conference on Industrial Automation and Control, 1995.
12.
Chang, T.Y., Kuo, S.W., and Hsu, J.Y.J. "A Two-Phase Navigation System for Mobile Robots in Dynamic Environments ." Proceedings of the 1994 IEEE/RSJ/GI International Conference on Intelligent Robots and Systems, pp 297-300, 1994.
13.
Dozier, G., Esterline, A., Homaifar, A. and Bikdash, M. "Hybrid Evolutionary Motion Planning via Visibility-Based Repair." Proceedings of the IEEE International Conference on Evolutionary Computation, 1997.
14.
Hocaoglu, C. and Sanderson, A. "Planning Multi-Paths Using Speciation in Genetic Algorithms." Proceedings of the 1996 IEEE International Conference on Evolutionary Computation, pp 378-383, 1996.
15.
Lin H-S., Xiao, J. and Michalewicz, Z. "Evolutionary Algorithm for Path Planning in Mobile Robot Environment ." Proceedings of the First IEEE Conference on Evolutionary Computation, IEEE World Congress on Computational Intelligence, 1994.
16.
Michalewicz, Zbigniew. "Path Evaluation in the Evolutionary Planner/Navigator." Proceedings of the 1995 International Workshop on Biologically Inspired Evolutionary Systems, Tokyo, May 30-31, 1995, pp 45-52.
17.
Shibata, T., and Fukuda, T. "Intelligent Motion Planning by Genetic Algorithm with Fuzzy Critic ." Proceedings of the 1993 International Symposium on Intelligent Control, 1993.
18.
Xiao, J., Michalewicz, Z. and Zhang, L. "Evolutionary Planner/Navigator: Operator Performance and Self-Tuning ." Proceedings of the 1996 IEEE International Conference on Evolutionary Computation, pp 366-371, 1996.
Khatib, O. "Real-Time Obstacle Avoidance for Manipulators and Mobile Robots." The International Journal of Robotics Research, Vol. 5, No. 1, Spring 1986, pp 90-98, Massachusetts Institute of Technology , 1986.
22.
Zhao, Y. "Theoretical and Experimental Evaluation of a Local-Minimum-Recovery Navigation Algorithm." Recent Trends in Mobile Robots, Yuan F. Zheng, editor, World Scientific , pp 75-117, 1993.
23.
Blackburn, M.R. and Nguyen, H.G. "Autonomous Visual Control of a Mobile Robot ." Image Understanding Workshop, Monterey, CA, Vol. 2, pp 1143-1150, 1994 .
24.
Deng, K., Wilson, J. and Ritter, G. "A Visual Tracking Based Robot Vision System." Proceedings of the SPIE —The International Society for Optical Engineering , pp 440-451, 1992.
25.
Hayashi, B.Y. and Negahdaripour , S. "Direct Motion Stereo: Recovery of Observer Motion and Scene Structure." Proceedings of the Third International Conference on Computer Vision, IEEE Computer Society Press, pp 446-450, 1990.
26.
Negahdaripour, S., Hayashi, B.Y. and Aloimonos , Y. "Direct Motion Stereo for Passive Navigation." IEEE Transactions on Robotics and Automation, Vol. 11, pp 829-843, 1995.
27.
Bryson, S. "BioVision: An Autonomous Recognition System." The NASA Center for Autonomous Control Engineering at North Carolina A&T State University, Greensboro, NC, ACE AT97-01, 1997.
28.
Wang, Y. and Cohen, F. "Part II: 3-D Object Recognition and Shape Estimation from Image Contours Using B-Splines, Shape Invariant Matching, and Neural Network." IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 16, pp 13-23, 1994.
29.
Vavak, F. and Fogarty, T.C. "Comparison of Steady State and Generational Genetic Algorithms for Use in Nonstationary Environments." Proceedings of the 1996 IEEE International Conference on Evolutionary Computation, pp 192-195, 1996.
30.
Nolfi, S., Floreano, D., Miglino, O. and Mondada, F. "How to Evolve Autonomous Robots: Different Approaches in Evolutionary Robotics." Proceedings of ALifeVI, Boston, 1994.
31.
Olmer, M., Nordin, P., and Banzhaf, W. "Evolving Real-Time Behavioral Modules for a Robot with GP." Proceedings of the Sixth International Symposium on Robotics and Manufacturing (ISRAM-96), 1996.
