What Is an Autonomous Agent?
An autonomous agent is a system situated within and a part of an environment that senses that environment and acts on it, over time, in pursuit of its own agenda and so as to effect what it senses in the future.
The movement of an autonomous agent can be broken down into three layers:
- This is the part of the agent’s behavior responsible for choosing its goals and deciding what plan to follow. It is the part that says “go here” and “do A, B, and then C.”
- This layer is responsible for calculating the desired trajectories required to satisfy the goals and plans set by the action selection layer. Steering behaviors are the implementation of this layer.They produce a steering force that describes where an agent should move and how fast it should travel to get there.
- The bottom layer, locomotion, represents the more mechanical aspects of an agent’s movement. It is the how of traveling from A to B. By separating this layer from the steering layer, it’s possible to utilize, with little modification, the same steering behaviors for completely different types of locomotion.
The Steering Behaviors
The seek steering behavior returns a force that directs an agent toward a target position.
Flee is the opposite of seek. Instead of producing a steering force to steer the agent toward a target position, flee creates a force that steers the agent away.
Arrive is a behavior that steers the agent in such a way it decelerates onto the target position.
Pursuit behavior is useful when an agent is required to intercept a moving target.
Evade is almost the same as pursuit except that this time the evader flees from the estimated future position.
It’s designed to produce a steering force that will give the impression of a random walk through the agent’s environment.
Reynolds’ solution is to project a circle in front of the vehicle and steer toward a target that is constrained to move along the perimeter. Each time step, a small random displacement is added to this target, and over time it moves backward and forward along the circumference of the circle, creating a lovely jitter-free alternating motion. This method can be used to
produce a whole range of random motion, from very smooth undulating turns to wild Strictly Ballroom type whirls and pirouettes depending on the size of the circle, its distance from the vehicle, and the amount of random displacement each frame.
Obstacle avoidance is a behavior that steers a vehicle to avoid obstacles lying in its path. An obstacle is any object that can be approximated by a circle (or sphere, if you are working in 3D). This is achieved by steering the vehicle so as to keep a rectangular are a — a detection box, extending forward from the vehicle — free of collisions. The detection box’s width is equal to the bounding radius of the vehicle, and its length is proportional to the vehicle’s current speed — the faster it goes, the longer the detection box.
Finding the Closest Intersection Point
The process of checking for intersections with obstacles is quite complicated, so let’s take this step by step.
- The vehicle should only consider those obstacles within range of its detection box. Initially, the obstacle avoidance algorithm iterates through all the obstacles in the game world and tags those that are within this range for further consideration.
- The algorithm then transforms all the tagged obstacles into the vehicle’s local space. This makes life much easier as after transformation any objects with a negative local x-coordinate can be dismissed.
- The algorithm now has to check to see if any obstacles overlap the detection box. Local coordinates are useful here as all you need to do is expand the bounding radius of an obstacle by half the width of the detection box (the vehicle’s bounding radius) and then check to see if its local y value is smaller than this value. If it isn’t, then it won’t intersect the detection box and can subsequently be discarded from further consideration.
At this point there are only those obstacles remaining that intersect the detection box. It’s now necessary to find the intersection point closest to the vehicle. Once more, local space comes to the rescue. Step C expanded an object’s bounding radius. Using this, a simple line/circle intersection test can be used to find where the expanded circle intersects the x-axis. There will be two intersection points, as shown in Figure 3.8. (We don’t have to worry about the case where there is one intersection tangent to the circle — the vehicle will appear to just glance off the obstacle.) Note that it is possible to have an obstacle in front of the vehicle, but it will have an intersection point to the rear of the vehicle. This is shown in the figure by obstacle A. The algorithm discards these cases and only considers intersection points laying on the positive x-axis.
Calculating the Steering Force
Determining the steering force is easy. It’s calculated in two parts: a lateral force and a braking force.
- There are a number of ways to calculate the lateral force but the one I prefer is to subtract the y value of the obstacle’s local position from its radius. This results in a lateral steering force away from the obstacle that diminishes with the obstacle’s distance from the x-axis. This force is scaled in proportion to the vehicle’s distance from the obstacle (because the closer the vehicle is to an obstacle the quicker it should react).
- The next component of the steering force is the braking force. This is a force acting backward, along the horizontal axis as shown in the figure, and is also scaled in proportion to the vehicle’s distance from the obstacle.
A wall is a line segment (in 3D, a polygon) with a normal pointing in the direction it is facing. Wall avoidance steers to avoid potential collisions with a wall. It does this by projecting three “feelers” out in front of the vehicle and testing to see if any of them intersect with any walls in the game world. See Figure 3.10. (The little “stub” halfway along the wall indicates the direction of the wall normal.) This is similar to how cats and rodents use their whiskers to navigate their environment in the dark.
Interpose returns a steering force that moves a vehicle to the midpoint of the imaginary line connecting two other agents (or points in space, or of an agent and a point). A bodyguard taking a bullet for his employer or a soccer player intercepting a pass are examples of this type of behavior.
Like pursuit, the vehicle must estimate where the two agents are going to be located at a time T in the future. It can then steer toward that position. But how do we know what the best value of T is to use? The answer is, we don’t, so we make a calculated guess instead.
The first step in calculating this force is to determine the midpoint of a line connecting the positions of the agents at the current time step. The distance from this point is computed and the value divided by the vehicle’s maximum speed to give the time required to travel the distance.This is our T value. See Figure 3.11, top.
Using T, the agents’ positions are extrapolated into the future. The midpoint of these predicted positions is determined and finally the vehicle uses the arrive behavior to steer toward that point. See Figure 3.11, bottom.
Hide attempts to position a vehicle so that an obstacle is always between itself and the agent — the hunter — it’s trying to hide from.
- For each of the obstacles, a hiding spot is determined.
The distance to each of these spots is determined. The vehicle then uses the arrive behavior to steer toward the closest. If no appropriate obstacles can be found, the vehicle evades the target.
Path following creates a steering force that moves a vehicle along a series of waypoints forming a path. Sometimes paths have a start and end point, and other times they loop back around on themselves forming a neverending, closed path.
The simplest way of following a path is to set the current waypoint to the first in the list, steer toward that using seek until the vehicle comes with in a target distance of it, then grab the next waypoint and seek to that,and so on, until the current waypoint is the last waypoint in the list. When this happens the vehicle should either arrive at the current waypoint, or, if the path is a closed loop, the current waypoint should be set to the first in the list again, and the vehicle just keeps on seeking.
Offset pursuit calculates the steering force required to keep a vehicle positioned at a specified offset from a target vehicle. This is particularly useful for creating formations. When you watch an air display, such as the British Red Arrows, many of the spectacular maneuvers require that the aircraft remain in the same relative positions to the lead aircraft.
Arrive is used instead of seek as it gives far smoother motion and isn’t so reliant on the max speed and max force settings of the vehicles.
Seek can give some rather bizarre results at times — orderly formations can turn into what looks like a swarm of bees attacking the formation leader!
Offset pursuit is useful for all kinds of situations. Here are a few:
- Marking an opponent in a sports simulation
- Docking with a spaceship
- Shadowing an aircraft
- Implementing battle formations
Flocking is a combination of three group behaviors — cohesion, separation, and alignment — all working together.
The white vehicle is the steering agent and the gray circle shows the extent of its neighborhood. Consequently, all the vehicles shown
in black are considered to be its neighbors and the vehicles shown in gray are not.
Separation creates a force that steers a vehicle away from those in its neighborhood region. When applied to a number of vehicles, they will spread out, trying to maximize their distance from every other vehicle.
Alignment attempts to keep a vehicle’s heading aligned with its neighbors. The force is calculated by first iterating through all the neighbors and averaging their heading vectors. This value is the desired heading, so we just subtract the vehicle’s heading to get the steering force.
Cars moving along roads demonstrate alignment type behavior. They also demonstrate separation as they try to keep a minimum distance from each other.
Cohesion produces a steering force that moves a vehicle toward the center of mass of its neighbors.
Flocking is a combination of the three previously described group behaviors: separation, alignment, and cohesion. This works okay but, because of the limited view distance of a vehicle, it’s possible for an agent to become isolated from its flock. If this happens, it will just sit still and do nothing. To prevent this from happening, I prefer to add in the wander behavior too. This way, all the agents keep moving all the time.
Combining Steering Behaviors
Often you will be using a combination of steering behaviors to get the behavior you desire. Very rarely will you only use one behavior in isolation.
Don’t forget that the vehicle is constrained by a maximum steering force, so this sum must be truncated in some way to make sure its magnitude never exceeds the limit.
Weighted Truncated Sum
The simplest approach is to multiply each steering behavior with a weight, sum them all together, and then truncate the result to the maximum allowable steering force.
This can work fine, but the trade-off is that it comes with a few problems. The first problem is that because every active behavior is calculated every time step, this is a very costly method to process.
Weighted Truncated Running Sum with Prioritization
This method involves calculating a prioritized weighted running total that is truncated after the addition of each force to make sure the magnitude of the steering force does not exceed the maximum available.
The steering behaviors are prioritized since some behaviors can be considered much more important than others. Let’s say a vehicle is using the behaviors separation, alignment, cohesion, wall avoidance, and obstacle avoidance. The wall avoidance and obstacle avoidance behaviors should be given priority over the others as the vehicle should try not to intersect a wall or an obstacle — it’s more important for a vehicle to avoid a wall than it is for it to align itself with another vehicle.
In addition to the prioritization, this method iterates through every active behavior, summing up the forces (with weighting) as it goes. Immediately after the calculation of each new behavior, the resultant force, together with the running total, is dispatched to a method called
AccumulateForce. This function first determines how much of the maximum available steering force is remaining, and then one of the following happens:
- If there is a surplus remaining, the new force is added to the running total.
- If there is no surplus remaining, the method returns false. When this happens, Calculate returns the current value of m_vSteeringForce immediately and without considering any further active behaviors.
- If there is still some steering force available, but the magnitude remaining is less than the magnitude of the new force, the new force is truncated to the remaining magnitude before it is added.
In his paper, Reynolds suggests a method of force combination he calls prioritized dithering. When used, this method checks to see if the first priority behavior is going to be evaluated this simulation step, dependent on a preset probability. If it is and the result is non-zero, the method returns the calculated force and no other active behaviors are considered. If the result is zero or if that behavior has been skipped over due to its probability of being evaluated, the next priority behavior is considered and so on, for all the active behaviors.
This method requires far less CPU time than the others, but at the cost of accuracy.
Ensuring Zero Overlap
Often when combining behaviors, the vehicles will occasionally overlap one another.
This can be prevented with the use of a non-penetration constraint. This is a function that tests for overlap. If there is any, the vehicles are
moved apart in a direction away from the point of contact (and without regard to their mass, velocity, or any other physical constraints)
Coping with Lots of Vehicles: Spatial Partitioning
When you have many interacting vehicles, it becomes increasingly inefficient to tag neighboring entities by comparing each one with every other one.
Large speed improvements can be made by partitioning the world space. There are many different techniques to choose from. You’ve probably heard of many of them — BSP trees, quad-trees, oct-trees, etc. — and may even have used them, in which case you’ll be familiar with their advantages. The method I use here is called cell-space partitioning, sometimes called bin-space partitioning (that’s not short for binary space partitioning by the way; in this case “bin” really means bin).
Here is how it’s done step by step:
- First of all, an entity’s bounding radius is approximated with a box.
Cell-space partitioning. The circled vehicles are those within the white
vehicle’s neighborhood region.
- The cells that intersect with this box are tested to see if they contain any entities.
All the entities contained within the cells from step 2 are examined to see if they are positioned within the neighborhood radius. If they are, they are added to the neighborhood list.
A vehicle can twitch or jitter slightly when it finds itself in a situation with conflicting responses from different behaviors.
A simple alternative suggested by Robin Green of Sony is to decouple the heading from the velocity vector and to average its value over several update steps.