Overview
Collision avoidance is an important aspect of agent navigation. Collision detection enables agents to avoid colliding with stationary obstacles or moving objects (including each other). In this case, we implemented a couple of techniques using sensors and radars.
These sensors provide agents with two types of collision avoidance.
These sensors and radars can provide the agent with two types of collision avoidance and provide useful data to help plan its path and actions accordingly. In this article, we’ll look into how this is implemented.
Obstacle Avoidance Sensors
Navigation Agents in this research are equipped with sensors to allow them to detect stationary obstacles in front of them.
With the detectors, agents are able to see obstacles ahead of them and act accordingly by applying some steering force to avoid a collision.
The article on “Training Agents to Navigate a Virtual Environment Using the NEAT Algorithm“, explains how detectors are used by explorer agents to avoid colliding with obstacles.
The navigation agents of this research are also powered by sensory boundaries (radars) that enable them to detect neighboring agents.
The radars provide information about the location of nearby agents and help agents keep a distance between each other to avoid incidences of overlapping.
The figure above shows the sensory boundaries of an agent. The smallest sensory boundary is used to detect an agent getting too close to other agents. It helps the agent separate its personal space from other agents. The second-largest range is the Field of View of the agent or its sensory horizon, which covers the region in which it can detect other agents or items in its vicinity. This sensory range helps the agent to interact with other agents and entities. Data (received from this sensory range) is then evaluated by an agent to plan tasks and achieve goals. Examples of such tasks might include escaping from an enemy force, following a leader agent, or approaching a target point.
The outermost sensory boundary is used to help to detect another agent leaving the agent’s Field of View. This information is useful when agents are equipped with short-term memory, which is a data set with memory records consisting of selective information about other agents that have been recently encountered. The memory records of an agent can indicate which other agents were last detected or became visible and can estimate the time and location of their presence or disappearance.
Space Partitioning to Improve Performance of the System
When there are many other agents and items in the environment, it is inefficient to check all of them to detect which ones are within range of an agent. Space partitioning techniques are required to reduce the amount of calculation required to find nearby items and thus increase efficiency. Many techniques are available to divide the space into separate regions. Some techniques such as Binary Space Partitioning (BSP) [1] and Quad-trees [2] divide it into regions, recursively representing the regions with a tree data structure.
Another partitioning technique called Cell-based partitioning [3] is efficient enough for collision detection in environments with moving obstacles. It divides the 2D region into axis-aligned rectangles and creates a matrix of cells. Each agent uses a query rectangle that is slightly larger than the size of the other cells (as shown in Figure above). The query rectangle detects which cells are within radar range of the agent. The number of cells by which can overlap is either four or nine and since agents or obstacles cannot overlap each other, there can only be a limited number of them in each cell at each time. Therefore, only agents and obstacles within the overlapped cells are examined to find out which ones are within radar range of the agent. This method significantly reduces the number of calculations required to find entities neighboring the agent to a time complexity of O(n).
References
- M. D. Berg, M. V. Kreveld, M. Overmars, and O. Schwarzkopf. Computational Geometry: Algorithms and Applications. Springer-Verlag, 2nd edition, 2000.
- R. Finkel and J. L. Bentley. Quad trees: A data structure for retrieval on composite keys. Acta Informatica, 4(1):1–9, 1974.
- M. Buckland. Programming Game AI by Example. Wordware Publishing, Inc., Plano, Texas, USA, 2005.
Pingback: Training Agents to Navigate a Virtual Environment Using the NEAT Algorithm - Brainy Loop