Kristina Lerman - US grants

EIA-0074790
Lerman, Kristina
University of Southern California

POWRE: Mathematical Modeling of Multi-Agent Systems

This POWRE proposal outlines a novel physics-based approach to solving computer science problems. The proposed activity leverages the author's training in physics, particularly the physics of complex systems, and applies to the study of multi-agent systems. The goal of the research is to propose a feasible mechanism in which interactions between agents with simple local strategies lead to desirable group behavior in each of the two domains: coalition formation in a multiagent system and dynamic routing in a sensor network. The proposed mechanism is then analyzed and a mathematical model of the process is constructed. The model is expressed as a series of coupled differential equations. For the coalition formation problem, for instance, the model describes how the number and distribution of coalitions change with time. The solutions of the equations describe collective behavior, and they can be analyzed for different values of the parameters.

The goal of the project is to develop a formal foundation for the synthesis and analysis of implicit multi-robot coordination mechanisms. Such a formal understanding will allow the multi-robot community to move away from ad-hoc solutions and toward the principled design and analysis of coordinated multi-robot systems. This will be achieved by introducing a formal language to describe the entities interacting in a coordinated multi-robot system, and apply this framework to the principled synthesis of robot controllers using logic-based induction. At the same time, this project will develop a methodology for modeling the coupled robot-environment system and derive the equations describing dynamics of the system. Finally, these procedures will be combined, so that results of analysis can be used to drive performance-enhancing modifications in the robot controller. To validate the formal concepts of the proposed research, these methods will be applied to the design and analysis of multi-robot coordination methods for a real-world sensor/actuator network deployment and maintenance task. The proposed research is novel in that it combines formal techniques from Computer Science, Mathematics, and Physics. As such, the work will serve as a vehicle for raising the profile of mathematical analysis in the robotics community. Undergraduate and graduate robotics courses will benefit from the inclusion of the developed formal analysis techniques. In addition, twice a year demonstrations will be given at local high schools to teach the students the concepts of collective behavior and give them the skills to better understand and approach complex problems.

A great deal of important human activity requires navigating and otherwise using physical spaces. Human spatial behavior, individual and collective, depends on the structure of the environment, the structure and content of cognitive representations of the environment (mental maps), individual and group goals, and interactions among individuals, groups, and crowds. As a result, human spatial behavior needs to be studied by considering all these aspects together; to do this requires a multidisciplinary effort. The proposed research brings together a team of researchers representing diverse disciplines of computation, psychology, and mathematics into an integrated program that will address human individual and collective use of physical space.
This project's multidisciplinary effort uses the tools of cognitive science, computational modeling, and mathematical analysis of collective behavior to study the dynamics of human spatial behavior. The project's goals are as follows:
1) To understand how individuals develop cognitive maps of complex environments in real-world situations that include rich spatial interactions with other people, individually and in groups;
2) To examine how cognitive maps influence the behavior of groups in high-density crowd conditions, and to develop the cognitive foundations for models of pedestrian dynamics and emergency evacuations;
3) To forge a mathematical link between microscopic (small scale) and macroscopic (large scale) models of adaptive human social behavior in spatial tasks.
The research program will develop novel cognitive map-driven models that will include the shared spatial information that individual people derive from social interactions. The models will be used to improve simulations of individuals and crowds, and provide a basis for mathematical analysis of collective spatial behavior dynamics. Validation and evaluation will exploit virtual reality technology, computer simulations of crowd behavior, and people's behavior in real environments. Through partnerships with two museums, the team will be working with real-world situations whose relevance to societal needs includes the design of emergency evacuation systems, automated detection of anomalies in large spaces and crowds, and the development of complex but human-friendly environments. The generation, validation, and free dissemination of powerful predictive models that will be developed will allow architects, planners, and developers of public spaces to design and/or modify public venues so as to optimize their navigability and safety. Finally, a comprehensive program of education, outreach, and dissemination will serve a broad audience of graduate and undergraduate students, inner-city K-12 students and teachers, and the general public will accompany the research.

This project systematically addresses the enormous complexity of mapping applications to current and future parallel platforms - both scalable parallel architectures consisting of tens of thousands of processors and distributed systems comprised of collections of these and other resources. By integrating the system layers - domain-specific environment, application program, compiler, run-time environment, performance models and simulation, and workflow manager -- and through a systematic strategy for application mapping, the project will exploit the vast machine resources available in such parallel platforms to dramatically increase the productivity of application programmers.

The key contribution of the project will be a systematic solution for performance optimization and adaptive application mapping -- a large step towards automating a process that is currently performed in an ad hoc way by programmers and compilers -- so that it is feasible to obtain scalable performance on parallel and distributed systems consisting of tens of thousands of processing nodes. The application components will be viewed as dynamically adaptive algorithms for which there exist a set of variants and parameters that can be chosen to develop an optimized implementation. Knowledge representation and machine learning techniques utilize this domain knowledge and past experience to navigate the search space efficiently.

CSR-AES: Intelligent Optimization of Parallel and Distributed Applications

ABSTRACT
This project derives a systematic solution for performance optimization and adaptive application mapping to obtain scalable performance on parallel and distributed systems consisting of tens of thousands of processing nodes. With expert domain scientists in molecular dynamics (MD) simulation, we expect to achieve performance levels on MD codes even better than what has been derived manually after years of development and many ports to a variety of architectures.
The application components are viewed as dynamically adaptive algorithms for which there exist a set of variants and parameters that can be searched to develop an optimized implementation. A workflow is an instance of the application where nodes represent application components and dependences between the nodes represent execution ordering constraints. By encoding an application in this way, we capture a large set of possible application mappings with a very compact representation. The system layers explore the large space of possible implementations to derive the most appropriate solution. Because the space of mappings is prohibitively large, the system captures and utilizes domain knowledge from the domain scientists and designers of the compiler, run-time and performance models to prune most of the possible implementations. Knowledge representation and machine learning utilize this domain knowledge and past experience to navigate the search space efficiently.
This multidisciplinary approach impacts the state-of-the-art in the sub-fields of compilers, run-time systems, machine learning, knowledge representation, and accelerates advances in MD simulation with far more productive software development and porting. More broadly, this research enables systematic performance optimization in other sciences.

This research will develop a general framework for mathematical analysis of collective behavior of adaptive multi-agent systems. Adaptation is an essential requirement for autonomous multi-agent systems functioning in uncertain dynamic environments, for example, distributed robot teams, modules in an embedded system, nodes in a sensor network, or software agents. Adaptation allows agents to change their behavior in response to changes in the environment or actions of other agents. Mathematical analysis of adaptive systems will enable researchers to design more robust systems, and to predict, control and understand their behavior.

The research will study agents that make decisions autonomously based on local information, which comes either from interactions with other agents or from the local environment. In particular, this project will examine different classes of adaptive behavior, such as adaptation through reinforcement and adaptation through communication via spatially extended fields. Reinforcement learning is a powerful framework where an agent learns optimal actions through a trial and error exploration of the environment and by receiving rewards for good actions. Collective adaptation can also take place in systems in which agents are coupled through external fields, for example, through markers they deposit in the environment.

Although adaptation and learning have long been the focus of the artificial intelligence community, there is relatively little work examining how a group of adaptive agents will act. The difficulty arises from the fact that agents adapt in the presence of other adaptive agents. Often it is not a priori clear how the system will act or even if adaptation will achieve the desired goals. In addition, the designer has very little guidance about what individual agent characteristics are required to guarantee the desired collective behavior. The lack of a formal understanding of these problems has prevented researchers from taking full advantage of this powerful design paradigm. The mathematical analysis to be performed in this research will help answer these questions.

There is a critical need for better foundations and tools for analyzing multi-agent behavior and verifying control mechanisms for multi-agent systems. The lack of such tools stands in the way of wider deployment of such systems, especially robots and embedded systems. Experiments and simulations that are necessary to validate control algorithms are time consuming and costly. Quantitative understanding provided by the mathematical models to be developed in this project will lead to more robust and efficient control algorithms and greater deployment of such systems in the field.

The Social Web is changing the way people create and use information.
Sites like Flickr, Del.icio.us, Digg, and others, enable users to
publish and organize content and participate in communities.
The information they create while interacting with content and
other users is called social metadata. Tags, one example of social
metadata, were introduced as a means for individuals to organize their
content by assigning freely-chosen keywords to it. Some Social
Web sites now also allow users to organize content hierarchically.
The photosharing site Flickr, for example, allows users to group
related photos in sets, and related sets in collections. Although
social metadata lacks formal structure, it captures the collective
knowledge of the community. Once extracted from the traces left by
many users, such collective knowledge will add a rich semantic layer
to the content of the Social Web. This project will develop a
probabilistic framework to combine diverse types of social metadata
to construct a common concept hierarchy. In addition, the methods
developed by the project will use social relations, in the form of
community participation, to discover community-specific vocabularies
and concepts, and identify facets of multi-dimensional concepts.

In the future, Social Web sites and data management tools will allow
users to express ever richer types of knowledge, including complex
predicates and semantic relations. The ability to aggregate
individually expressed knowledge into a unified whole will
transform the way people use information. Global concept hierarchies,
for instance, can help users visualize how their content relates
to that of others and allow for more efficient browsing, search
and discovery. By linking content to a common concept hierarchy,
the methods developed by the project could also be used to integrate
disparate data and align it across domains. The proposed work,
therefore, addresses one of the more important emerging questions
in AI, namely, how to harness the power of collective intelligence.

For further information about this project, please see the project
Web site at http://www.isi.edu/~lerman/projects/folksonomy.html.

ABSTRACT

Access to up-to-date and quality information can have a significant impact on the humanitarian relief community as they coordinate relief efforts. In addition to data that is created and curated by experts, there is a vast volunteer community who are empowered by the social Web to generate community curated content on sites such as Flickr, Del.icio.us, and Google Earth. Combining data from experts and volunteers can facilitate the efforts of relief agencies. In order to effectively use this data, one needs to (1) discover relevant sources, (2) assess quality, and (3) understand their content. Fortunately, the wealth of content and metadata, i.e., annotations in the form of tags, on the social Web, can aid in this task of semantic discovery and quality assessment.

The GeoNets project will develop methods to analyze social content and metadata in order to extract concepts, including geospatial concepts and generate semantically-rich geospatial data. GeoNets can also increase the re-use of data by suggesting terms to improve the quality of existing annotations. GeoNets will develop methodologies for semantic discovery and quality assessment to create a GeoNets dataspace and provide a user friendly query language.

The methods developed by the project also apply to other fields where information created by a lay community augments the knowledge produced by professionals. In several scientific disciplines, including astronomy, biology and ecology, an army of passionate amateurs is making new observations and discoveries. GeoNets will create tools that will enable scientists to leverage community-generated knowledge to create up-to-date, semantically rich dataspaces."

The Social Web, or Web 2.0, has changed the way people connect with each other and use information. Sites such as Twitter, Flickr, and Digg allow people to create content, annotate it with descriptive labels, and befriend others to create communities. The collective knowledge and expertise of the community is expressed through the links between people and information. The key to extracting this knowledge is understanding the structure and dynamics of networks.

This project will study dynamics of information spread on networks and how it relates to network structure and quality of information. In previous work, investigator has developed a mathematical framework to study the properties of static networks. She showed that a centrality metric based on the number of paths connecting nodes can be used to identify groups and important nodes within them. However, looking at static structure ignores valuable temporal information that can be used to improve the ability to identify influential nodes and hidden groups, as well as quickly and reliably predict important trends and evaluate the quality of information. The investigator will extend these metrics to dynamic networks and model information spread on networks. The investigator will apply these methods to complex networks that link different types of entities, namely, people, content, and groups.

Considering network structure in the dynamics of information spread will lead to more effective tools to leverage community's knowledge to address a number of problems, including identifying important trends, assessing information quality, and separating true information from rumors.

The Social Web has become an important medium for social interaction and potentially a powerful new computational tool. As people create and share information online, their collective activity shapes the structure and usefulness of the Social Web and can even be used to address a range of problems from collective decision-making to trend prediction. Understanding how the aggregate activity of many interconnected people evolves is crucial to our ability to transform the Social Web into a platform for social computing.

Mathematical modeling is a powerful tool for studying collective human activity. In previous work, the PI and collaborators developed a framework for mathematically modeling emergent behavior of groups of users on the Social Web. This framework allowed the modeler to relate aggregate behavior of a group of users to simple descriptions of their individual behavior. However, it failed to take into account key aspects of the Social Web: user diversity and the extent to which social links indicate a commonality of users' interests.

The goal of this project is to develop a methodology for modeling diverse groups of users on the Social Web and to understand how user heterogeneity affects group behavior. Mathematical modeling and analysis will lead to better, more effective Web sites by identifying productive ways to display information to users, as well as techniques for promoting collaboration and enhancing participation. Analysis will also lead to new insights into how to use human activity for computation, and eventually a programming toolkit for social computing.

Social, technological, and biological systems are often represented as a complex network, whose structure reveals important properties of the system and leads to insights about its behavior. Many methods have been proposed over the past several decades to analyze the structure of complex networks, for example, to identify influential people in a social network or functional modules in a protein-protein interaction network. Most of these methods examine connections between entities only, and ignore interactions between them. In recent years, however, it has been recognized that network structure is the product of both its connections (i.e., topology) and the interactions taking place between entities in the network. These interactions determine how ideas, signals, pathogens, or influence flow along the connections, and different interactions may lead to different views of network structure.

This research project will lay the foundation for understanding the interplay between network structure, topology and dynamical interactions. It will develop a mathematical framework for interactions-aware network analysis that will lead to principled metrics and algorithms for finding communities or modules, measuring proximity between entities in a network, and distance between networks. Theoretical findings will be empirically validated using real-world network data on tasks such as identifying modules, predicting missing links and others. This new framework for network analysis will translate into new discoveries in computer science, sociology, biology and medicine.

The central tenet of this project is that knowledge discovery and valuation is a human activity, and as such, it is subject to cognitive heuristics and biases, or mental shortcuts that help people make quick decisions. Social and economic progress is driven by scientific discoveries, and technological and legal innovations. However, as new knowledge accumulates at an accelerating pace through the publication of new scientific papers, patent applications and legal opinions, it becomes ever more difficult to identify information that is critical for innovation. In order to create tools to speed up innovation, we first need to understand how people find and evaluate knowledge. This project will analyze patterns of citation networks in three domains -- physics papers, patents and federal court decisions -- to learn how scholars and innovators discover and evaluate knowledge.

Behavioral data for studying cognitive heuristics is available in the form of citation networks. These networks capture the decisions that scholars and innovators made about what relevant documents to reference in their own work. By conducting comparative empirical analysis of citations made by physics papers, patents, and federal court decisions, this project will identify the strategies people use to decide what information to attend to, especially under conditions of information overload, and study the interplay between these strategies, the quality of information, and the decisions of others. In addition to its contributions to understanding how ideas are discovered and evaluated, this project will make a novel, clean data set of legal citations publicly available. The insights produced by this research will lead to new, robust measures of information quality and impact. The new understanding of the role of cognitive heuristics in citation will inform the design of next generation knowledge discovery tools that will help people to more optimally leverage citations to improve the efficiency and robustness of discovery and innovation.

An effective response to fight the spread of a pandemic requires a clear understanding of the complex interactions between biological, environmental and human networks. The COVID19 pandemic revealed both human and systemic failures along this chain. A key takeaway was the need for timely, relevant and actionable information to support effective public messaging and policy making that can impact in-real-life (IRL) outcomes. The COVID19 pandemic also revealed the need for messaging and policy making at a local scale, when national- or state-level approaches might not appropriately address the needs at community scale. Frontline public health officials often had little insight into the individuals that they wished to serve. Decision makers who managed cities or school systems often relied on epidemiological models that did not account for the impact of human beliefs and in-real-life behaviors - e.g., the willingness to wear a mask - on disease transmission. The PandEval project will address these challenges, so as to ultimately increase the trust and confidence in our public health infrastructure. If successful, public health officials will gain insight into the success of (past) messaging campaigns so that they can deliver the right message at the right time. In addition, decision makers will be able to use the outcomes of the epidemiological models, customized to population segments, while planning vaccine rollout, or admitting visitors to congregate living.<br/><br/>The innovation of the PandEval project is to rely on curating rich complex multimodal datasets. Social media-based models of community beliefs and attitudes around science skepticism, moral foundations, or the willingness to contribute to the public good, will be developed. Baseline profiles of in-real-life (IRL) behavior tracked by human mobility traces will be computed. Compartmental epidemiological models that account for population characteristics will be customized to account for a diversity of micro-targeted population segments and regions across the US. The PandEval platform will be engineered to measure the effectiveness of community targeted messaging around pandemic mitigation, including recommendations and mandates, and to measure the prediction accuracy of the customized epidemiological models. As the nation faces the potential of endemic COVID19, the PandEval project will create and curate Pand-Index, an index of online social beliefs and in-real-life (IRL) profiles at a national scale. Pand-Index profiles will help individuals to make personalized decisions about social distancing or masking versus working from home.<br/><br/>This award is supported by the cross-directorate Predictive Intelligence for Pandemic Prevention Phase I (PIPP) program, which is jointly funded by the Directorates for Biological Sciences (BIO), Computer Information Science and Engineering (CISE), Engineering (ENG) and Social, Behavioral and Economic Sciences (SBE).<br/><br/>This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.