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 Pacman 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.

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.

Pacman example

Usually the technique involves creating many small "antiobject" objects, for the Pacman example, one antiobject per background tile is created. Each of these antiobjects or agents has an identical and simple algorithm which it runs at ever turn of the game. Instead of making Ghosts smart enough to solve "shortest path" problems around the maze, a notion of "Pacman scent" is created instead and each tile is responsible for saying how much Pacman scent is on it's tile. Using Alan Turing's reaction-diffusion equation equation this turns out the 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 Pacman scent value, then it asks it's 4 nearest tiles for their scent. Lastly, given these inputs, it solves the differential equation, which simulates the spread of Pacman scent. Note that the walls of the maze, and Ghosts themselves, all block the diffusion of Pacman scent. These local differences affect the outcome of each tiles amount of scent and always provide a gradient that leads to Pacman. 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 Pacman scent.

This pattern of making each tile an agent and allowing them to look at the state of it's neighbors is also how Conway's Game of Life works. Similarly, notice the simple rules and naturally parallel nature of computation, also like the game of life.

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 Agent_sheets. The concept of antiobjects can be applied to other algorithms and problem spaces.