Monthly Archives: August 2016

Analysis of ant colony behavior

Ants, it turns out, are extremely good at estimating the concentration of other ants in their vicinity. This ability appears to play a role in several communal activities, particularly in the voting procedure whereby an ant colony selects a new nest.

Biologists have long suspected that ants base their population-density estimates on the frequency with which they — literally — bump into other ants while randomly exploring their environments.

That theory gets new support from a theoretical paper that researchers from MIT’s Computer Science and Artificial Intelligence Laboratory will present at the Association for Computing Machinery’s Symposium on Principles of Distributed Computing conference later this month. The paper shows that observations from random exploration of the environment converge very quickly on an accurate estimate of population density. Indeed, they converge about as quickly as is theoretically possible.

Beyond offering support for biologists’ suppositions, this theoretical framework also applies to the analysis of social networks, of collective decision making among robot swarms, and of communication in ad hoc networks, such as networks of low-cost sensors scattered in forbidding environments.

“It’s intuitive that if a bunch of people are randomly walking around an area, the number of times they bump into each other will be a surrogate of the population density,” says Cameron Musco, an MIT graduate student in electrical engineering and computer science and a co-author on the new paper. “What we’re doing is giving a rigorous analysis behind that intuition, and also saying that the estimate is a very good estimate, rather than some coarse estimate. As a function of time, it gets more and more accurate, and it goes nearly as fast as you would expect you could ever do.”

Random walks

Musco and his coauthors — his advisor, NEC Professor of Software Science and Engineering Nancy Lynch, and Hsin-Hao Su, a postdoc in Lynch’s group — characterize an ant’s environment as a grid, with some number of other ants scattered randomly across it. The ant of interest — call it the explorer — starts at some cell of the grid and, with equal probability, moves to one of the adjacent cells. Then, with equal probability, it moves to one of the cells adjacent to that one, and so on. In statistics, this is referred to as a “random walk.” The explorer counts the number of other ants inhabiting every cell it visits.

In their paper, the researchers compare the random walk to random sampling, in which cells are selected from the grid at random and the number of ants counted. The accuracy of both approaches improves with each additional sample, but remarkably, the random walk converges on the true population density virtually as quickly as random sampling does.

That’s important because in many practical cases, random sampling isn’t an option. Suppose, for instance, that you want to write an algorithm to analyze an online social network — say, to estimate what fraction of the network self-describes as Republican. There’s no publicly available list of the network’s members; the only way to explore it is to pick an individual member and start tracing connections.

Similarly, in ad hoc networks, a given device knows only the locations of the devices in its immediate vicinity; it doesn’t know the layout of the network as a whole. An algorithm that uses random walks to aggregate information from multiple devices would be much easier to implement than one that has to characterize the network as a whole.

Solve complex urban problems

MIT has signed an agreement to engage in research collaborations with the Amsterdam Institute for Advanced Metropolitan Solutions (AMS) in the Netherlands. The collaboration’s flagship project, led by researchers from multiple departments at MIT, will be to develop a fleet of autonomous boats for the city’s canals.

Based in Amsterdam, the AMS Institute brings together a consortium of public and private partners to tackle complex urban challenges such as water, energy, waste, food, data, and mobility. MIT joins with two research institutions in the Netherlands — the Delft University of Technology and Wageningen University and Research Center — as the core academic partners who will use the city as a living laboratory and test bed.

An interdisciplinary team from MIT has assembled to lead the collaboration’s first project: ROBOAT, an effort to develop a fleet of autonomous boats, or “roboats,” to investigate how urban waterways can be used to improve the city’s function and quality of life.

The ROBOAT project will develop a logistics platform for people and goods, superimposing a dynamic infrastructure over one the world’s most famous water cities. “This project imagines a fleet of autonomous boats for the transportation of goods and people that can also cooperate to produce temporary floating infrastructure, such as on-demand bridges or stages that can be assembled or disassembled in a matter of hours,” says Carlo Ratti, professor of the practice of urban technologies in the MIT Department of Urban Studies and Planning (DUSP).

In addition to infrastructure and transport, ROBOAT will also deploy environmental sensing to monitor water quality and offer data for assessing and predicting issues related to public health, pollution, and the environment. “Water is the bearer of life. By focusing on the water system of the city, ROBOAT can create opportunities for new environmental sensing methods and climate adaptation. This will help secure the city’s quality of life and lasting functionality,” says Arjan van Timmeren, professor and scientific director at AMS, who also envisions a multitude of possibilities for a network of roboats, from real-time sensing similar to the MIT Underworlds project to retrieving the 12,000 bicycles or cleaning up the floating waste that ends up in the Dutch city’s canals each year.

Joining Ratti from MIT as co-principal investigators are Daniela Rus, professor of electrical engineering and computer science and director of the MIT Computer Science and Artificial Intelligence Laboratory (CSAIL); Andrew Whittle, the Edmund K. Turner Professor in Civil Engineering in the Department of Civil and Environmental Engineering; and Dennis Frenchman, the Class of 1922 Professor of Urban Design and Planning and director of the DesignX program in the MIT School of Architecture and Planning.

At AMS, Van Timmeren and Stephan van Dijk, research program manager, will coordinate the involvement of another 12 groups of researchers from TU Delft and Wageningen UR. Along with the City of Amsterdam, Waternet, the public water utility of Amsterdam and surrounding areas, will participate in the research.

The first prototypes of autonomous boats, or “roboats,” are expected to be tested in Amsterdam in 2017. The project’s initial phase will last for five years.

With nearly one-quarter of the city covered by water, Amsterdam is an ideal place for developing ROBOAT, according to the researchers. The canal system was once the key functional urban infrastructure of the city and today still plays a major role in recreation and tourism. Amsterdam’s waters, including bridges, canals, and the IJ river and its docks, offer plenty of opportunity to help solve current issues with transportation, mobility, and water quality.

Measuring your heartbeat and breath

As many a relationship book can tell you, understanding someone else’s emotions can be a difficult task. Facial expressions aren’t always reliable: A smile can conceal frustration, while a poker face might mask a winning hand.

But what if technology could tell us how someone is really feeling?

Researchers from MIT’s Computer Science and Artificial Intelligence Laboratory (CSAIL) have developed “EQ-Radio,” a device that can detect a person’s emotions using wireless signals.

By measuring subtle changes in breathing and heart rhythms, EQ-Radio is 87 percent accurate at detecting if a person is excited, happy, angry or sad — and can do so without on-body sensors.

MIT professor and project lead Dina Katabi envisions the system being used in entertainment, consumer behavior, and health care. Film studios and ad agencies could test viewers’ reactions in real-time, while smart homes could use information about your mood to adjust the heating or suggest that you get some fresh air.

“Our work shows that wireless signals can capture information about human behavior that is not always visible to the naked eye,” says Katabi, who co-wrote a paper on the topic with PhD students Mingmin Zhao and Fadel Adib. “We believe that our results could pave the way for future technologies that could help monitor and diagnose conditions like depression and anxiety.”

EQ-Radio builds on Katabi’s continued efforts to use wireless technology for measuring human behaviors such as breathing and falling. She says that she will incorporate emotion-detection into her spinoff company Emerald, which makes a device that is aimed at detecting and predicting falls among the elderly.

Using wireless signals reflected off people’s bodies, the device measures heartbeats as accurately as an ECG monitor, with a margin of error of approximately 0.3 percent. It then studies the waveforms within each heartbeat to match a person’s behavior to how they previously acted in one of the four emotion-states.

The team will present the work next month at the Association of Computing Machinery’s International Conference on Mobile Computing and Networking (MobiCom).

How it works

Existing emotion-detection methods rely on audiovisual cues or on-body sensors, but there are downsides to both techniques. Facial expressions are famously unreliable, while on-body sensors such as chest bands and ECG monitors are inconvenient to wear and become inaccurate if they change position over time.

EQ-Radio instead sends wireless signals that reflect off of a person’s body and back to the device. Its beat-extraction algorithms break the reflections into individual heartbeats and analyze the small variations in heartbeat intervals to determine their levels of arousal and positive affect.

These measurements are what allow EQ-Radio to detect emotion. For example, a person whose signals correlate to low arousal and negative affect is more likely to tagged as sad, while someone whose signals correlate to high arousal and positive affect would likely be tagged as excited.

The exact correlations vary from person to person, but are consistent enough that EQ-Radio could detect emotions with 70 percent accuracy even when it hadn’t previously measured the target person’s heartbeat.