Obstacle implementation

Obstacle avoidance has been implemented to complement the agent perception and navigational models. The agent's desire to avoid obstacles is treated in the same way as its desire to obey the other rules of flocking. If the agent perceives a collision on its horizon of perception, the collision avoidance vector is given a heavy weighting (~500%) and included in the averaging algorithm with the other agent desires. The theory behind including the obstacle avoidance vector without ignoring all other desires allows the flock to maintain it's organisational structure whilst avoiding collisions with neighbouring agents and environmental obstacles.

Obstacles are stored as a pair of coordinates that correspond to the extremities of a 2D line segment through which agents cannot penetrate. More complex obstacles can be constructed from joining and intersecting a series of lines together. Manipulation of the geometry surrounding the obstacles is made easier with the use of the Line2D class which provides static methods to calculate distances and intersections between coordinates and lines in 2D space. For example, the heading of an agent can be thought of as a 2D line segment extending outwards from the location of the agent to the boundary of the perception model. This segment can be tested against each of the obstacle line segments using the 'public static boolean linesIntersect()' method, which returns true if the line segments intersect (i.e. if the agent is on a collision course with the obstacle).

The first function I added to the existing Agent class took two pairs of coordinates [x1, y1], [x2, y2], representing a line segment, and returned the identity of the first obstacle hit (i.e. the first obstacle line segment intersected) when tracing a straight line from [x1, y1] to [x2, y2]. If no obstacle intersection is found, -1 is returned. This function serves two purposes. Firstly, when [x1, y1] is given the value of the current agent position, and [x2, y2] is given the position on the agent's perception horizon in the direction of its current heading, the function returns the id of the obstacle the agent must steer around to avoid a collision. If no obstacle intersection is found then the obstacle avoidance vectors play no further part in the navigation of the agent.

Secondly, the function can be used by the perception model as a means of identifying neighbouring agents that cannot establish a direct line of sight with the current agent because the visible path between them is intersected by obstacles. In this case [x1, y1] would represent the current agent position and similarly [x2, y2] would be the neighbouring agents position. The returned result of -1 from the function represents a clear line of sight between agent and neighbour. Any result greater than this implies that the neighbour cannot be seen and therefore should not play any further role in the agent's navigational model. It is worth noting that I am assuming all obstacles to be opaque.

Solving the silhouetted edge problem (the cul-de-sac lemma)

The initial algorithm used by agents to avoid collisions with obstacles, looked at both ends of the obstacle line segment as being avoidance paths around the object and simply chose the path of least resistance based on the directional acceleration that would be required from the agent to follow each one. There were a number of problems resulting from this simple model. The agent would pick a path to avoid the immanent obstacle, irrespective of where the path led to. This lack of foresight would often lead the agent onto a new collision path with a different obstacle. In the case of a cul-de-sac, where two obstacles intersect making a conical barrier, the suicidal agent moves towards the end of the cul-de-sac as the avoidance path of each interior side leads to the opposite side. This gives the agent no option other than to jitter between the two avoidance paths until finally it passes through the apex of the cul-de-sac as if there was no obstacle present at all.

This cyclic avoidance behaviour can be halted by considering the future of the agents' avoidance path. If the avoidance route brings the agent into contact with a new obstacle, a new avoidance path is calculated. If this new path leads back towards the original obstacle the avoidance behaviour is said to be cyclic. To break out of the cycle the agent is forced to select the route of most resistance. In the cul-de-sac example, the path of most resistance leads the agent directly away from the end of the cul-de-sac.

By considering the future of the obstacle avoidance path, the agent is able to form a route that avoids several intersecting obstacles in one step. This is equivalent to the way Reynolds's uses a silhouette of a 3D polygon to find the appropriate escape route for his 'Boids'.

Further refinements

Originally, agent obstacle avoidance made use of both sets of obstacle coordinates irrespective of weather or not they lay inside the agent's perception model. This gave the agents seemingly mystical powers of obstacle avoidance that enabled them to map large sets of intersecting obstacles and determine how to avoid collisions with obstacles that had edges far outside the perception area.

The solution was to crop each obstacle relative to each agent so there exists no obstacle detail available to the agent that lies beyond the agent's area of perception. This limiting process gives rise to another one of ReynoldsÕs steering behaviours: wall following, or 'steer along surface'. The virtual obstacle edges the agent seeks to avoid only exist relative to a specific agent at a discrete moment in time. As the agent moves, the virtual edges move, providing the agent with updated avoidance vectors. This process has the effect of steering the agent along side the surface of the obstacle until the acceleration acting on the agent brings its direction parallel to the obstacle's orientation. This behaviour better mirrors the processes that agents perform to avoid obstacles in reality.