Assignment #1 - Obstacle Avoidance

GPR440 Advanced AI
[ 2.5.21 ]

Made With	Languages
Unity3D Rider	C#

Overview

Over the course of the project, I attempted a few different approaches to using exclusively raycasting as a means to avoid obstacles (no tracking of other entities or overlap spheres) to have as simple of a behavior as possible. My intention was to try to use overlap spheres as a way to track multiple obstacles to make more complicated/informed decisions, but I ran out of time before I could explore that kind of obstacle detection/avoidance.

At first, I tried to see what I could do with only a single forward raycast (from here on out I will use the term whisker). It worked surprisingly well if you dialed the settings in right (longer whisker, higher acceleration and lower max speed).

The primary problem I encountered was that the agent could easily miss anything that wasn't directly in front of it and would clip the sides. To resolve this, I tried two different ways to mitigate that: sweep the whisker and use more than one whisker.

The results of using a sweeping whisker were a mixed bag. While it was more likely that the agent detected obstacles it would not have normally, it would also miss things it should have if the whisker was at one edge of its cone and the obstacle was in the other edge. In addition, the whisker being off center can also result in an obstacle being detected, but resulting in a less-than-ideal avoidance attempt (turning the less safe direction). Sweeping with multiple whiskers provided no new insights, and seemed largely useless.

The 'Simple Raycast' Approach

On the coding side of things, for my first attempts, I tried to make a straightforward, simple, one-size-fits-all algorithm for obstacle detection and avoidance to streamline the process and make it easier on the processing side. This had the pro of being easy to debug and implement, but the con of lacking finer control that'll be more relevant when I talk about using multiple whiskers.

Quickly, let me go over the agent's movement script. In FixedUpdate() the acceleration vector is calculated using the equation Acc = TargetDir - Vel which is capped of a magnitude set by Max Acc. Then the script updates the velocity using Vel += Acc * Time.fixedDeltaTime (which is capped at a magnitude of Max Speed). TargetDir is provided by the brain using the public function SetTargetDirection(Vector3 t).

For my first agents' actual brains, you can set the number of whiskers and their length (all are the same length, in Unity units) using the corresponding settings. There is a bool for whether you want the whiskers to sweep, how far, and how fast. When numWhiskers > 1 sweep angle is used for their distribution.

avoidSeverity is a modifier used when calculating the new target direction so the user can set how aggressively the agent will respond to any positive raycast hits. avoidSeverity is used very simply in the target direction algorithm below.

The target direction is calculated by adding the modified hit normal and the diff vector made by the whisker:

tDir = hitPt - agentPos + norm * avoidSeverity

For multiple whiskers, a target direction is found for every raycast hit and averaged together.

The algorithm is fairly simple and straightforward, but always provides a new target direction away from the obstacle that is in front of it. The only time this really fails is when there are multiple whiskers. If something comes between the whiskers, the resulting target direction will cause the agent to turn and get 'caught' on the obstacle. (Pictured below)

This is because all whiskers are treated the same under this approach, and the lack of finer control over the different whiskers results in undesired behavior.

This is one way an agent can get caught on a part of the environment. End caps of walls and corners are also liable to catch the agent.

Other undesired behavior, is that long whiskers spread into a wide arch can confuse the agent and get it stuck in tighter spaces.

3 Whisker Approach

Basic Differences

The primary difference of this approach is that it is locked in to three whiskers, meaning I can be sure how they're positioned and therefore have a much more deliberated avoidance solution, and I can adjust the lengths of the side whiskers and the front whisker (and their avoid severity) separately.

This slightly higher degree of control and added certainty of 3 whiskers allows me to narrow in to create a really solid avoidance behavior. (Using the same movement script)

Algorithmic Differences

Separating the forward and side whiskers allows me to respond to raycast hits using different cases rather than a conglomeration of a bunch of normals wall weighted the same.

For example, if both side whiskers (and therefore likely the forward whisker) the agent will set the target direction to directly behind it; if only one of the side whiskers hits, to the opposite direction.

Just the forward whisker hitting is the only time I use my original target direction formula.

Tri-Whisker Avoid Function

// get the left vector
Vector2 left = new Vector2(-forward.y, forward.x);

// hit on left
if (hits[1] && !hits[2])
{
    // turn right
    _targetVelocity = left * -sideAvoidCoeff;
    numHits++;
}

// hit on right
else if (!hits[1] && hits[2])
{
    // turn left
    _targetVelocity = left * sideAvoidCoeff;
    numHits++;
}

// hit on both sides
else if (hits[1] && hits[2])
{
    // turn around
    _targetVelocity = -forward * sideAvoidCoeff;
    numHits++;
}

// only a hit forward
else if (hits[0])
{
    // turn left or right based on where the normal points
    _targetVelocity = left * (Mathf.Sign(
                                Vec2Cross(forward, hits[0].normal)
                             ) * forwardAvoidCoeff);

    numHits++;
}
// else nothing hit so do nothing

if (numHits <= 0) // if there are no hits
{
    // Lerp the target velocity to the forward direction at max acceleration
    _targetVelocity = Vector3.Lerp(_targetVelocity, 
                                   forward * _moveScript.maxAcc,
                                   driftSpeed * Time.deltaTime);
}

Another Approach?

The Tri-Whisker approach still suffers from some of the problems mentioned above, but to fully eliminate it would be object tracking (particularly for moving obstacles) and a more complex pathing to circumvent obstacles. With a whisker based approach object tracking doesn’t feel super attainable, and I wanted to avoid complexity for this project.

A circle based approach, though, may offer the solution to higher quality avoidance through tracking, a 360 degree view and object tracking from a greater distance. I did not have time to implement this however, but I genuinely think it would offer a lot of room for top-tier avoidance, but ultimately I think you might as well just use regular pathfinding if you are going to this amount of effort.