User:Block based programmer/Antiobjects

The notion of antiobjects is a computational metaphor useful to conceptualize and solve hard problems by swapping computational foreground and background. Similar to optical illusions based on potential confusion of background versus foreground perceptions, antiobjects are the inverse of what we perceive to be the computational objects. If we implement, as part of a Pac-Man game, a ghost we are tempted to think of the necessary behavior associated with the ghost object; if we simulate the behavior of an air bubble in a water glass we are tempted to think of how the bubble object should behave; if we build a soccer simulation we are tempted to think of how the soccer player objects should interact with the ball and other player objects. Antiobjects turn things on their head. In the case of Pacman we put the main computation into the maze; to simulate the behavior of an air bubble we put the main computation into the water; to create a collaborative soccer game we put the main computation into the soccer field.

Overview

From the abstract of “Collaborative Diffusion: Programming Antiobjects”:

The metaphor of objects can go too far by making us try to create objects that are too much inspired by the real world. This is a serious problem, as a resulting system may be significantly more complex than it would have to be, or worse, will not work at all. We postulate the notion of an antiobject as a kind of object that appears to essentially do the opposite of what we generally think the object should be doing. As a Gedankenexperiment antiobjects allow us to literally think outside the proverbial box or, in this case outside the object.

Putting computation into antiobjects, e.g., the maze, the water, and the soccer field, can substantially simplify hard problems in Artificial Intelligence and simulations. Moreover, the mapping of computation from a small number of objects to a much larger number of typically homogenous antiobjects can by employed to parallelize computation in ways that it can be executed on parallel architectures such as GPUs and multi-core CPUs with very little overhead.

Examples

Usually the technique involves creating many small "antiobject" objects, for the Pac-Man example, one antiobject per background tile is created. Each of these antiobjects or agents has an identical and simple algorithm which it runs at every turn of the game. Instead of making Ghosts smart enough to solve "shortest path" problems around the maze, a notion of "Pac-Man scent" is created instead and each tile is responsible for saying how much Pac-Man scent is on its tile. Using Alan Turing's reaction-diffusion equation this turns out to be a simple distributed solution which runs on each instance of tile. The tile asks other objects or antiobjects located on top of it for their Pac-Man scent value, then it asks its 4 nearest tiles for their scent. Lastly, given these inputs, it solves the differential equation, which simulates the spread of Pac-Man scent. Note that the walls of the maze, and Ghosts themselves, all block the diffusion of Pac-Man scent. These local differences affect the outcome of each tile's amount of scent and always provide a gradient that leads to Pac-Man. Besides the reaction-diffusion equation, no difficult algorithms, such as topology problems, are needed, yet a correct and accurate solution emerges. The Ghosts are given a simple hill climbing algorithm to walk towards higher quantities of Pac-Man scent.

This pattern of making each tile an agent and allowing them to look at the state of its neighbors is also how Conway's Game of Life works, as well as all cellular automata. Similarly, notice the simple rules and naturally parallel nature of computation, also like the game of life. Spicher, Fatès and Simonin proposed a general scheme to turn an agent-based model into a cellular automaton. The authors studied the case of Diffusion-Limited Aggregation as a starting example

Reaction Diffusion

In all of Repenning's papers on antiobjects, reaction diffusion equations are used in the algorithms. These papers are written within the context of AgentSheets. The concept of antiobjects can be applied to other algorithms and problem spaces.