Surfing Artificial Potential Fields

Back to Home Page

Final Project Report
Artificial Intelligence II -- CSCI 5512
For Dr. Maria Gini
3/5/96
Paul E. Rybski

Introduction:

Programming an autonomous mobile robot to navigate in any sort of environment is probably one of the oldest problems faced by any robotics or artificial intelligence researcher. Even in the most carefully constructed environments, robots are notorious for finding ways of becoming lost or stuck. The problem becomes even harder when a robot is expected to navigate effectively through an unknown and chaotic environment. The more cluttered and uncertain the space is that the robot has to maneuver in, the more likely that it will get into a situation where it cannot recover from.

One way of solving this task would be to attempt to anticipate all of the various situations that the robot could find itself. However, this would quickly lead to failure because it is probably impossible to dream up all of the different possible objects and environments that the robot could encounter. Another way would be to devise a method of using as much information about the world around the robot to allow the robot to decide what to do next. Such a method would extract vital clues from the immediate surroundings so that the robot can make the best decision at that time. This kind of method is superior to the first because it doesn't depend on the creativity of the programmer to dream up what the robot should do in every possible world. Instead, it uses a few simple rules that give the robot just enough information to make a good decision. One such method is called Artificial Potential Fields.

Artificial Potential Fields represent obstacles in an environment as "virtual forces". All objects in an environment that the robot wants to avoid can be thought of as emitting a virtual force that repels a robot that comes close to it. As a robot's sensors let it know that it is approaching an object, the robot's controller can steer the robot away as if pushed by an invisible force coming from that object. The closer the robot gets, the stronger the virtual force will be that will push it away. Virtual forces can also be used as attractors as well. If the robot needs to approach a beacon or some other goal, the goal can be thought of as emitting a virtual force that pulls a robot towards it. No matter where it is in the environment, the robot will "feel" that attraction and will try to move towards it. If there are obstacles between the robot and the goal, they will cause the robot to steer around them while still moving towards the goal. Artificial Potential Fields allow a robot to effectively "feel" its way around an environment such that it knows where it is supposed to go and where it shouldn't.

This goal of this project was to develop a mobile robotic control system based on Artificial Potential Fields. This project was inspired by an paper published by Dr. Ronald Arkin at the Georgia Institute of Technology "Motor Schema - Based Mobile Robot Navigation" [1].

Description of Robot and Software

The robot used for this project was a 3-wheeled LEGO vehicle fitted with a Polaroid sonic ranging sensor mounted on its front driving turret (Fig 1). The robot was capable of turning its front sensor/wheel turret in a 180 degree arc to take distance measurements from objects located in this area. Due to its low proximity (one inch off the floor), the sonar was capable of returning reasonably accurate distances to objects of up to about five or six feet before becoming unreliable. Computational power was provided by a Miniboard, a mc68HC11-based microcontroller board developed at MIT.

When the robot took sonar measurements, it would do so at nine points, each 22.5 degrees apart from the other. This produced nine force vectors that would make the robot feel as if it were being pushed back from the front and the sides. The strength of these force vectors depended on how close obstacles were to the robot. Because the front sensor/wheel turret could not turn past 90 degrees to the right or the left of the robot, the robot was essentially blind to anything behind it. This was a problem because artificial potential field algorithms usually provide sensor information in a complete 360 degree arc, so that the robot is capable of feeling forces from all sides. Should one side have no force applied to it, the other forces will push the robot in that direction. In general, robots that make use of artificial potential fields are either run in simulation where all of the field vectors are already known via the system or they have an all-encompassing ring of sonar or other range sensors which give them a complete description of the area around surrounding them (Fig 2).

In order to compensate for the lack of sensory information, an artificially-induced force vector was hard-coded into the robot's controller in order to produce a forward-facing vector to offset the rear-facing vectors produced by objects facing the front half of the robot. This was accomplished by a technique that I have affectionately dubbed "potential wave surfing." The robot generated a set of fake force vectors pointing in from the areas that the sonic range sensors did not cover. These force vectors were fake in the sense that because there was no sensor coverage in the rear, their magnitudes were not based on anything. After doing this, the robot was completely surrounded by 16 distinct vectors produced by real (or faked) distance measurements. These 16 were summed in order to produce the final vector that indicated the direction of motion. Of the 16 vectors, the 9 in the front half (including to the immediate left and right) were generated by the Polaroid sonic ranger and the 7 in the back half were generated internally without any knowledge about the world. Since the general direction that the robot was designed to travel was straight ahead, the magnitudes of the seven rear vectors were set initially to equal amounts. Thus the sum of these vectors produced a force vector that pointed straight ahead.

Another way to visualize how the effect of these potential fields is to imagine a landscape in which hills represent the forces that push the robot away. The faked rear-based vectors would appear as a semi-circular hill which surrounds the rear of the robot. This semi-circular hill would always try to push the robot forward. Since the hill moves with the robot (the rear force vectors are fixed in strength), one could imagine the robot riding the crest of this hill (thus the surfing analogy).

As the robot rides this false rear potential wave, hereafter referred to as the potential surf, it would encounter other potential mountains in this landscape which would repel it. The slightest force from an object to one side of the robot of the robot will cause the robot to move in a direction away from the obstacle. If the robot was being pushed closer to an obstacle by riding its potential surf, it would eventually reach a point at which it could get no closer since the potential surf does not have enough force to push the robot up the incline. At this point, the robot might oscillate between these two conflicting forces until it works itself free and moves in a different direction.

Experiments and Discussion:

By altering the shape and strength of the potential surf, the overall behavior of the robot could be tweaked and adjusted. The first of three different attenuation experiments was to see how stretching the potential wave to either the right or left side of the robot (perpendicular to the direction of travel of the robot) would affect it's behavior. (Fig 4) By adjusting the relative intensities of the force vectors, the potential surf was shaped in such a way that it pushed the robot to one side instead of just straight ahead. This biasing helped to remove the difficulty that the robot would normally have when approaching features in the landscape that exhibit a great deal of symmetry. Normally, in such a situation, the force vectors generated by these features would start to cancel each other out and cause the robot to head straight towards them instead of moving away. Another behavior that the left or right biasing of the potential surf produced was that of wall-following. Once the robot located a wall or obstacle in the direction that it was being pushed, the stronger force vectors of the bias kept the robot near the perimeter of that obstacle.

The second experiment was to see what would happen if the magnitudes of the forces on the left and right vectors were increased while the magnitudes of the forces along the center axis of the robot were decreased (Fig 5). This served to shape the potential surf such that it pinned the robot between two very steep potential hills. This forced the robot to keep from getting too close to obstacles in the off to the sides. When this biasing was implemented, the robot spent a fair amount of time oscillating between two obstacles that were to its left and right until it found a point that was very close to the exact center between the two. In addition to maintaining its distance from obstacles off to the side, the robot gave frontal obstacles a very wide berth as well. Areas where the robot used to go (such as between tables) were apparently no longer accessible to this configuration as the potential surf vector was not strong enough to carry the robot over the potential hills that such environmental features created.

The third and final experiment to alter the shape of the potential surf was to do just the opposite of the previous experiment (Fig. 5). The forces to the immediate rear of the robot were be augmented and the forces along the left and right rear side of the robot were diminished. When implemented, the robot still tended to stay directly between obstacles to its right and left side. However, it did not oscillate between them as severely as it did in the previous experiment. Instead, the robot's motion could be described as a gentle wander. Since the left and right sides of the robot were pinned between small potential hills, the robot could move between them reasonably easily without being forced back down one side or another. The robot was also able to move through the tighter areas and passages that the previous parameters avoided.

Of the three approaches, the third one seemed to be the most successful in navigating the chaos and clutter that covers the floor in parts of the University of Minnesota Artificial Intelligence, Robotics and Vision Laboratory.

Future Research:

Initially, all of the sonic data range gathering was done while the robot was stationary. This was done to avoid introducing additional noise into an already noisy system (sonars are notorious for returning inconsistent readings). However, after the initial experiments were completed, it was found that the robot could still maintain a respectable and distance from most objects when moving very slowly while taking sonar readings. By running the robot at 1/4 maximum speed when taking readings, it it was still able to perform as well as before.

Finally, additional research into methods of keeping the robot out of situations where it is stuck between a potential hill and its potential surf would be useful. One possible approach would be to introduce random noise into the vector equations. This would help to shake the system up sufficiently to push the robot out of a situation where conflicting vector forces are pinning the robot into a fixed location. Such a random function could easily be implemented into the current robotic system. However, determining the correct parameters so that the random variance is strong enough to be useful but not strong enough to completely throw the robot off course would take some time and experimentation.

Conclusions:

The success of this project proved just how well a robust Artificial Potential Fields algorithm could be designed and implemented under such limited resources. The potential surfing modification to the Artificial Potential Fields algorithm proved to be a very reliable method of navigation with obstacle avoidance. The size of the algorithm was extremely small and its speed on the little 2MHz 6811 was very quick. The choice to use LEGOs for the construction of the robot was made because of their ease of construction as well as the ease of interfacing with any number of different sensors, actuators, motors and computers. They are also extremely accessible to students of all ages and thus are an effective way of doing robotics from teaching design techniques to implementing full-blown robotic systems.

References:

[1] Arkin, R. 1989. "Motor Schema based mobile robot navigation." International Journal of Robotics and Automation, 678.