In recent years, computer scientists have used the study of social insects to improve their own work. So-called ant algorithms have been applied to the optimization of network traffic, robot navigation and task scheduling. Researchers at Carnegie Mellon University thought it was time to give something back to the entomologists: They have developed a vision system that observes and classifies the behavior of ants in a colony. Tucker Balch, a research scientist at the university's Robotics Institute who developed the system with Manuela M. Veloso and Zia Khan, explained that it comprises an off-the-shelf NTSC video camera, 30-Hz PCI frame grabber and 700-MHz computer. The school's CMVision algorithm provides image-processing capability, and the ant trails are compared with Behavior Hidden Markov Models based on plots that myrmecologists, or ant researchers, use to describe an ant's activity in terms of its movement. The system's first task is to determine where the ants are in an image. Because ants tend to be the same color as food, waste and shadows, the researchers employed a hybrid approach that includes background differencing over many frames to determine which regions of ant-colored pixels also display movement between frames. To track the ants, the system uses a greedy association algorithm to connect these regions at 30 fps. The algorithm takes two consecutive frames and matches the location of an ant in the earlier frame to the nearest location of an ant in the later frame. This approach, while computationally efficient, can produce errors when, for example, the path of a quick ant crosses that of a slow one. Balch said that the team is working on a new algorithm that will be both fast and accurate. The spatial behavior of an ant is a good indicator of whether it is acting as a forager, nursemaid, soldier or caretaker of the nest. Myrmecologists have modeled this relationship between movement and role, and the system uses similar models to attach a role to each ant track. The researchers have tested the system in the lab with colonies of up to 500 ants, and fieldwork is under way in the Arizona desert. An immediate outcome of the work will be to make the life of a myrmecologist easier. The researchers hope that the successful modeling of ant behavior also will lead to the observation of other multiagent systems with the technique. "If we can do that," Balch said, "then we can also apply these algorithms to a broad range of other problems, like modeling human crowd behavior or traffic in a city or tanks on the battlefield."