Building a Better Agent
Yasamin Mostofi shows that strong networks start with more cooperative agents
Imagine a group of small, mobile robots methodically searching a warehouse for an explosive device or testing the air for a dangerous toxin. Each intrepid robot, or "agent," has its own sensing capabilities, but it can cover only so much ground on its own. To complete the mission, the agents must move in a coordinated fashion, share information, and work together while reporting to the human in charge. Restrict power resources, limit sensing and processing capability, and add physical obstacles like walls, uneven terrain, and weather, and the agents' job becomes much more challenging.
Yasamin Mostofi is researching ways to make their job easier. An assistant professor in the Electrical and Computer Engineering Department, Mostofi is studying cooperative networks and ways to make them more efficient and robust. She conducts her research with a team of masters and doctoral students including Alireza Ghaffarkhah, Mehrzad Chegini, and Yongxiang Ruan.
Improving Network Potential
A subcategory of complex systems, cooperative networks are groups of decentralized agents, sometimes called "nodes," that work together to achieve a common goal without the direction of a leader. An agent can be anything from computer software to a sensor or power plant. The advent of cheap embedded units equipped with sensing, communication, and processing capabilities has created new and unimaginable possibilities for learning and interacting with our environment. The vision of such networks cooperatively learning and adapting to achieve a common goal is closer than ever. However, to realize the full potential of cooperative networks, several challenges must be addressed. Understanding and optimization of information flow is one of the critical challenges of network science, which is a new field of investigation for studying complex networks.
Mostofi's academic background gives her research a unique twist. She earned her Ph.D. in communications and conducted post-doctoral research in control and dynamical systems. Using her experience and understanding of communication links between agents, she applies a realistic view of how communication affects high-level decision-making and control in cooperative networks, something that has received little attention. "Due to the complex and multidisciplinary nature of the problem, it is common to assume ideal communication links or links that are perfect within a certain radius when it comes to motion planning," explains Mostofi. "This, however, is too simplistic and does not allow for understanding and optimization of information flow in mobile cooperative networks." She was one of the first researchers to propose communication aware decision-making strategies where issues such as multipath fading and shadowing, both random and time varying factors that affect link quality, are accounted for in high level decision-making and motion-planning.
Mostofi and her team are working on multiple research projects that focus on two main areas: developing mathematical foundations for understanding cooperative networks and creating smarter algorithms to improve the network's performance and robustness, with an emphasis on information flow.
Planning the Next Step
To achieve the goal in a timely and efficient manner, each agent must make strategic decisions about movement based on information from other agents. Otherwise, all of the agents may search the same area.
Agents must also take into account how actions will affect their ability to communicate. "Motion planning cannot ignore communication," says Mostofi. "As you move around, communication link qualities are going to change due to effects such as fading and shadowing so we need to take those into account." A move in one direction may improve an agent's ability to sense a target, but diminish its capacity to exchange information with other agents because of the extra power required to communicate, a process Mostofi refers to as "communication and sensing trade-offs."
This means that an agent may need to sacrifice some local sensing quality in order to have stronger communication links, and hence better overall networked sensing. On the other hand, an agent may need to rely on itself, from time to time, if the cost of communication is too high.
To get better insight into designing cooperative networks, Mostofi learned from networks in the natural world. Studies of social insect colonies have shown that in collective foraging, if the cost of communication among individuals in a large area is high, insects may decide to explore the area independently as opposed to relying on getting the information from others. Based on such studies, she proved that the optimum design in cooperative mobile networks involves similar strategies, which she characterized mathematically.
Reaching an Agreement
Once the agents have planned their next step, they must be able to reach a consensus about their findings. Mostofi and her team are researching that challenge with Majeed Hayat, professor of electrical and computer engineering, and Patrick Bridges, assistant professor of computer science. Their network science-related research project is funded by the Defense Threat Reduction Agency. In August 2007, the team received $400,000 from DTRA to design a network that can withstand a deliberate attack. However, findings from the research would be applicable to all types of networks facing a variety of threats or failures.
Mostofi and her team are responsible for robust and distributed estimation and detection of the attacks; or how to make agents smarter so they can share information and reach an agreement about the situation while lowering the probability of making false assessments.
"The main challenge is that the information for such estimation and detection is sparse and distributed over the network," says Mostofi. "Network consensus problems have therefore received considerable importance and attention in recent years. Most of the work in this area, however, has focused on estimation type consensus."
Using matrix analysis, probability, and communication theory, her team has mathematically characterized the relationship between the transient behavior of detection consensus and link qualities. This characterization shows that it is beneficial for the agents to communicate to reach a consensus over the occurrence of an event-but only up to a point. When links between agents have deteriorated, probabilistic measures of link quality must also be factored in to how the agents make decisions. To address this, Mostofi uses concepts such as soft information processing, a familiar approach in coding theory, to make smarter agents. In a sense, this allows an agent receiving information over a poor-quality link to weigh it less heavily than the information coming from an agent with a better connection.
The UNM research team has already developed intelligent algorithms for increasing robustness of cooperative networks to attacks and failures. Now, they've put in a proposal with DTRA to extend their research to more complex scenarios.
Sharing Tasks
Another focus of the team is on computation, communication, and control, a process that evaluates how best to allocate both computation and communication resources among agents that are in charge of real-time and cooperative decision-making and control. While problems at the intersection of communication and control have received considerable attention in recent years, the intersection of the three has mainly stayed unexplored.
Working in real time and managing tasks, agents in the network must distribute tasks among themselves and do so in an adaptive and decentralized manner that allows for the fact that agents fail and new agents join the network. Communication resources such as limited bandwidth must be allocated accordingly and cannot be optimized independently. "It results in very interesting trade-offs as to how agents should share computation and communication resources and allocate tasks," says Mostofi.
So far, Mostofi has developed an optimization framework where the optimum allocation of computing resources is related to the characteristics of the jobs and link qualities. Through solving the dual problem, Mostofi was able to find a closed-form expression for the optimum solution.
"This, however, is just the beginning," says Mostofi. Judging by their diverse projects and passion for research, Mostofi and her team will move beyond researching better agents to finding new solutions for an increasingly complicated world.