Artificial potential field based robot navigation, dynamic constrained optimization and simple genetic hill-climbing

Abstract

The authors show a relationship between artificial potential field (APF) based motion planning/navigation and constrained optimization. They then present a simple genetic hill-climbing algorithm (SGHC) which is used to navigate a point robot through an environment using the APF approach. The motivation for the research is a robot that they are currently developing, named AGIE-3 (Autonomous Guided Intelligent Equipment 3), which senses and navigates through the use of a stereo vision head. They compare the SGHC with steepest descent hill-climbing (SDHC), using two environments. The first environment is composed of stationary obstacles while the second environment is composed of non-stationary obstacles. In SDHC, candidate moves are evaluated within a 360 degree radius and the best candidate is selected by the robot. One would think that the SGHC would be at a disadvantage; however, the performance of the SGHC is comparable with SDHC even though it does not search 360 degrees for candidate moves. The SGHC has an advantage in that it is capable of evolving the appropriate step size as well as the appropriate angle of movement.