The Agents, Interaction and Complexity group (AIC) undertakes world‐leading research into the science and engineering of complex socio‐technical, socio‐economic and socio‐ecological systems that underpin the most pressing challenges currently facing society. Problems as diverse as engineering resilient and sustainable smart infrastructure, or refactoring health‐care systems to cope with demographic change, or anticipating and mitigating the impacts of climate change, all involve building and analysing complex systems comprising many interacting agents, including people and other organisms, hardware robots and autonomous software agents.
Our research spans a wide range of themes and applications:
We are one of the world's leading groups in the area of agent-based computing. We have some 30 people working on various facets of intelligent agents and multi-agent systems. This ranges from foundational work in the design of flexible and autonomous individual agents and their interactions, through the principled analysis and design of agent-based systems, to the deployment of real-world applications.
We view agent-based systems as consisting of three main constituent components:
Encapsulated computer systems that are situated in some environment and are capable of flexible, autonomous action in that environment in order to meet their design objectives.
Agents invariably need to interact with one another in order to manage their inter-dependencies. These interactions involve the agents cooperating, negotiating and coordinating with one another to achieve their individual and/or collective aims.
Agent interactions take place within some organisational context (e.g. a marketplace, an auction or some other form of institution) and we are concerned with the analysis and design of such structures to ensure desirable behaviour ensues.
Within this landscape, our particular areas of specialisation focus on
Design of Individual Agents
We are interested in the design of individual agents that can achieve their goals in highly uncertain and dynamic environments. Our work typically uses decision theory, learning algorithms and Bayesian techniques to control the sensing, reasoning and acting of such agents.
Models of Interaction
This work develops new models and techniques for controlling and managing the interactions that take place between multiple autonomous agents. Particular prominence is given to automated cooperation, coordination and negotiation using techniques such as game theory, mechanism design, computational economics, distributed optimisation and constraint satisfaction. We also have a strong interest in the design of a variety of electronic institutions such that the equilibria they produce can be analysed from the perspectives of both the constituent individuals and the collective.
Applications of Agent Technology
This work involves applying agent-based concepts and techniques to real-world applications. In particular, we are concerned with the domains of business process management, eCommerce, logistics, energy systems, sensor networks, disaster response, telecommunications, and eDefence.
Applying and extending network theory to deal with the large-scale and topologically complex networks found in domains such as biology, computing, geography and knowledge representation. Example topics: constraints on networks due to spatial layout, integration of multiple interacting networks, network sampling, network structure in markets, ontology networks, social networks.
Fundamental research into networks underpins our understanding of many natural and engineered systems, e.g., social organisations, critical infrastructure, software agent systems, sensor networks, evolving populations, ecosystems, brains, economies, cities, and cells. Of particular interest are co-evolutionary networks (where the state of the network nodes co-evolves with the configuration of the network edges) and spatially embedded networks (an important sub-class of networks in which nodes tend to be connected to their spatial neighbours and long distance connections are rare or expensive to maintain). A combination of mathematical and simulation modelling is required to understand how real-world networks arise, persist, and change, and also to explore the functional properties of different topologies and dynamics: for instance, the capacity for a network to support efficient collaboration, to reorganise after attack, or to absorb stress without failing.
Spatially embedded networks
Many real-world networks are embedded in space; e.g., the Internet, social networks, neural networks, etc. It is clear that this spatial embedding often influences the structure of the networks, allowing pairs of nearby nodes to be directly connected while discouraging direct connections between nodes that are distant from one another, for example. Yet networks science has tended to abstract away the spatial organisation of these networks in order to concentrate on the topology of their connectivity. By studying a class of Spatially Embedded Random Networks (SERNs), we are able to answer the question: what does spatial embedding contribute to the structure and dynamics of complex networks? In answering this question we have begun to demonstrate the influence of spatial embedding on connectivity such as the effects of spatial symmetry on conditions for scale free degree distributions, and the existence of small-world spatial networks. One interesting result is the lack of a phase transition to a giant component that is characteristic of some other random graphs. We have also been able to show that spatial embedding tends to increase the complexity of network dynamics.
Real-world networks are rarely static structures. The properties of the nodes change over time as people age, species evolve, agents learn or neurons interact. Likewise, the connections between the nodes change as people make and break friendships, ecological interactions shift, agents move in and out of communication range, and synaptic connections strengthen or weaken. In truly dynamic networks, nodes and connections also enter and leave the network. What makes these dynamics especially interesting is that they are coupled – changes in the properties of the nodes bring about changes in their connections, and changes in connections between nodes bring about changes the properties of the nodes themselves. Understanding this kind of co-evolutionary reflexivity is important where systems are changing over time, especially as a consequence of adaptive processes such as learning or evolution. Key contexts include social networks where social ties are the relationships through which affiliations, social attitudes and knowledge diffuse, and these properties provide the context for new social ties to form. Other domains include ecological networks, neural networks and agent populations.
Physically distributed systems in which multiple stakeholders, all with their own individual preferences and aims interact with one another, are increasingly important within our everyday lives as transportation, health care, utility and emergency response systems steadily make more use of ubiquitous computing and sensing resources. Such systems are significant in that they frequently lack any central point of control, and yet, as system designers, we would like to ensure that these systems exhibit desirable system-wide properties, and can operate with minimal human intervention.
Within AIC we are designing, prototyping and evaluating the technologies that are required to build these systems. We are investigating the fundamental issue of how agents should communicate, negotiate and cooperate, and we are exploiting insights from game theory, economics, graph theory and evolutionary science to engineer robust systems that operate under a decentralised control regime.
Key application domains for this work include the coordination and control of multiple autonomous sensing platforms (such as UAVs – unmanned autonomous vehicles) within a disaster response scenario where first responder must maintain up-to-date situational awareness, and in future energy systems, such as the smart grid, where every home and building across the electricity grid may become both a producer and consumer of electricity, making autonomous decisions that benefit both the homes or building occupants, and also the grid itself.
Understanding the underlying algorithmic principles of biological systems, via the application of modelling techniques developed in artificial intelligence to problems in ecology and evolution. Example topics: the major transitions in evolution, the evolution of sex, symbiosis and symbiogenesis, ecosystem selection in biofilms, collective building behaviour in insects, the evolution of signalling and communication, social learning behaviour, mimicry, the epistemological status of evolutionary simulation models.
Critical drivers in the life sciences require that we better understand the interconnected organisation and adaptation of ecological and evolutionary systems. Key applications include bio-engineering and synthetic biology (e.g., bio-transformation in chemical industries, bio-regeneration and sustainability in agriculture, and epidemiology and disease treatments in medicine). Moreover, understanding how biological systems cope with and exploit complexity will also inform bio-inspired engineering of artificial complex adaptive systems (e.g., robust and adaptable approaches to distributed sensor networks, amorphous computation, collective robotics, or indeed, high-performance parallel computing).
Human Computer Interaction (HCI) research focuses on how people interact with technology and on the design of novel interfaces and interaction techniques. In particular our interests are in systems and strategies to support innovation and creativity, and help users in making sense of large amounts of data. To this end, we create and evaluate prototypes that range from tangible and mobile interfaces to Web applications.
Because technology today permeates and influences most aspects of our lives – and will do so even more in the foreseeable future – HCI can have a considerable impact on our living. Our overarching research goal, then, is to develop insights and tools to improve wellbeing and quality of life.
Our work is interdisciplinary in its approach, drawing on cognitive psychology, design and sociology in addition to electronics and computer science. In particular our research interests include the following areas:
Building & Managing Knowledge
One of our key interests is in the design of systems and methods to help people develop new, usable knowledge about the world around them and how they engage with it. Examples range from understanding how people make sense of electricity smart meters to interaction design of mobile technology to support health goals.
Value from Social Networks
On-line social networks can be a source of information and wisdom, but not all content we find there is equal. From spammers to bots to people just desperate for attention, a lot of advice out there is just, plain bad. How can we separate the wheat from the chaff? Our work aims at finding or fostering structure around online social media, to augment their value.
Mixing Physical + Digital in Everyday Life
Tangible user interfaces (TUIs) have been promoted and discussed in the Ubicomp and HCI communities since the early nineties. In TUIs physical objects are used for the control and representation of digital information, similarly to how icons are used in graphical user interfaces for the same purpose. Our research in TUIs builds on extremely low-cost prototypes that can be easily deployed and studied in the real world, even through the Web.
We are starting to investigate the opportunities and challenges related to human interaction with autonomous agent systems. As more and more sensing and computation power become available and accessible, opportunities emerge to leverage them in our everyday life: from smart homes to smart classrooms, to smart vehicles. How do we decide how much control to retain and how much to delegate to autonomous systems?
Computational economics is a core part of the AIC research agenda and applies game-theoretic and market-based economic principles to the design and understanding of multi-agent systems. Research areas include algorithmic game theory, coalition formation, mechanism design, automated negotiation, social choice, and agent-based computational economics. Applications include sponsored search, cloud computing, the smart grid, e-business, and disaster management.
Our research in computational economics focuses on the following areas.
Algorithmic game theory is a new and exciting area of research on the intersection of economics and theoretical computer science. Its results have found applications in a wide range of real life domains, such as international affairs, coalition formation in parliament, multi-robot coordination, job scheduling, auction design, peer-to-peer file sharing, and, most notably, the internet. Algorithmic game theory combines the ideas and techniques from game theory and algorithm design, with the aim of developing appropriate algorithms for strategic environments, where multiple self-interested agents interact. In addition to the strategic considerations analysed in classical game theory, algorithmic game theory considers whether and how the theoretical solution concepts, such as Nash equilibrium, can be applied in practice. In particular, it involves determining the feasibility of certain approaches by considering their computational complexity, as well as designing approximate algorithms when computing optimal solutions is intractable. The aim is then to design computationally tractable algorithms which have good approximation ratios, and at the same time maintain their economic properties.
Coalition formation is also concerned with strategic environments, and focuses on situations where groups of self-interested agents come together to achieve a set of joint goals. Such situations arise in various domains, from political lobbies and customs unions, to production cartels and multi-agent systems. Example applications in multi-agent systems include disaster response, where different stakeholders need to share their resources to achieve various tasks such as saving civilians; sensor networks where different sensors need to work together to achieve missions such as tracking targets; and group buying networks where groups of agents form a coalition to take advantage of quantity discounts. Key challenges in this area include the computation of optimal coalitions, which takes maximum advantage of the synergies between agents, as well as computing stable coalitions whereby no group of agents has an incentive to deviate and form their own coalition.
Social choice addresses a central problem in multi-agent systems and is concerned with how groups of agents with different interests arrive at a collective decision, such as deciding which subset of tasks to execute, a joint plan of action, or a specific allocation of resources. Social choice considers the mechanisms, such as voting, by which disparate agents can reconcile their differences. In particular, given that agents may have incentives to vote strategically and hide their real interests, much of the research involves exploring different mechanisms for minimising or even eliminating such manipulations.
Mechanism design studies the design of incentives in order to build systems where individual agents, be they humans or software agents, would act in a way that satisfies the goals of the system as a whole. A prime example is the allocation of tasks and resources through auctions, where the system goal is to allocate the tasks to those agents who are most able to execute them, or to allocate the resources to those who value them the most. Unlike cooperative systems where techniques such as decentralised optimisation can be used to perform such allocations, mechanism design applies to systems which consist of different stakeholders, and where agents may have conflicting goals and preferences. The aim is to make these agents, through appropriate rewards and penalties such as monetary payments or reputation values, to act in a way that is consistent with the global goals of the system. For instance, in the auction example, it is important to incentivise the agents to be truthful about their capabilities and preferences such that appropriate allocations can be made. Furthermore, unlike social choice, where the decisions are global and affect all of the agents, mechanism design considers local decisions that affect individual agents.
Automated negotiation studies computational approaches to resolve conflicts between two or more agents by means of negotiation. Such situations arise, for example, when software agents need to agree on an the exchange of resources, the scheduling of appointments, and other situations where agents have conflicts of interest. Negotiation typically involves an iterative process whereby agents exchange offers and counter offers. The advantage of using machines to automate this process is that the computer can negotiate much more effectively in a number of ways. Specifically, automated negotiation allows for a large number of offers to be exchanged in a short period of time, the offers can be of a complex nature (consisting of not just the price, but include many other factors such as quality of service, duration, and other terms and conditions), negotiation can occur concurrently between a number of agents, and overall negotiation time can be significantly reduced.
Agent-based computational economics is concerned with reproducing system-wide phenomena from the real world, such as financial bubbles and crashes, using relatively simple agents, where the complexity arises through the interaction among the agents. The aim is to find the fundamental features that could explain the observed phenomena, and how changes in system variables, such as government policy and market structure, could affect the outcome of a system. This is mostly achieved through computational simulations.
Our research in Informed Matter focuses on integrating information processing into physical and chemical systems to enable the formation of complex structure and functionality. The overall aim is to facilitate a step-change in the complexity of synthetic materials and thus narrow the gap between the intricate material organisation found in the biological world and what is available in the present engineering tool-kit. AIC activities in Informed Matter range from molecular to macroscopic scale and include molecular computing, self-assembly, and bio-hybrid devices.
A complexity barrier prevents chemists and engineers from entering the design space of the marvellously capable and efficient materials we see in the living world. To make the complexification of matter exhibited by nature amenable to engineering, it will be necessary to integrate information processing with the physical and chemical processes that govern the interaction of material building blocks.
In AIC we work towards this aim in three-pronged approach:
Molecular Information Technology
Living systems are peculiarly organised inhomogeneous arrangements of the very same matter that forms the remaining dead universe. Their highly organised state can be sustained only by active maintenance which in turn necessitates the processing of information—life without computation is inconceivable. Conversely, the proficiency with which single-cell organisms maintain their living state under adverse conditions and severe constraints in energy and material indicates the efficiency that may be achieved through the direct use of the physical characteristics of materials for computation.
In close collaboration with the Centre for Hybrid Biodevices at the Institute for Life Sciences AIC develops and implements molecular computing architectures based on micro droplets that are filled with a chemically excitable medium. Droplet-to-droplet excitations lead to a chemical pulse that travels through an array of droplets, mimicking neuronal impulses in the brain.
Self-assembly processes in the broadest sense, including irreversible assembly and self-disassembly, play an important role in the organisation and as well as repair of biomolecular architectures. The loss of prescriptive control concomitant with molecular components and nano devices makes self-formation also important for manufacturing. Within AIC we employ self-assembly in the implementation of our molecular computing architectures and investigate strategies for self-formation on the macroscale.
Present information technology is founded on the basis that computation can be formally prescribed independent of its physical realisation. Coercing a physical substrate to obey the formalism, however, comes at the price of a large overhead in material and energy. For the use of bio- and nano-materials it is often uneconomical, if not impossible to achieve a narrowly prescribed behaviour. This poses a challenge for the engineering of systems in which biomacromolecules or living cells play an important functional role. In AIC we investigate engineering approaches to the integration of such autonomous components into conventional architectures. We employ autonomous experimentation, i.e a closed-loop of computer-controlled experimentation and machine learning, to characterise materials or systems, such as enzymatic networks. We also develop the interface technology to integrate living cells into conventional electronic architectures.
Meeting the challenge of cutting greenhouse-gas emissions and ensuring energy security requires radical changes in the ways in which energy is generated, distributed and consumed.
Central to this change is the vision of the smart grid – anelectricity network in which information flows freely between consumers andsuppliers, and demand adapts in real-time in response to the continuously changing supply from intermittent renewable sources.
The decentralized nature of the smart grid, and the autonomous intelligent behaviour expected of it, is increasingly leading power-systemsengineers to turn to novel information- and communication-technology approaches to understand how to build and control this new grid. In particular, the field of multi-agent systems offers a rich set of techniques, algorithms and methodologies for building distributed systems in which desirable system-wide properties can be assured, despite the autonomous (and perhaps self-interested) actions of the component parts (here individual homes and businesses making their own decisions about energy generation and consumption).
Researchers within AIC have been at the forefront of the application of multi-agent systems in future energy systems such as the smart grid. Work to date has addressed areas as diverse as the coordination of energy storage, the pricing of electric vehicle charging, the formation of virtual power plants, and the development of personal energy assistants that can advise on and automate home energy use.
We increasingly rely on an interdependent network of complementary, interacting, infrastructure systems: transport, energy, water, waste, ICT, and even governmental, health care and emergency services. In the UK, and in advanced economies globally, these systems face serious challenges. There is an urgent need to reduce carbon emissions from infrastructure systems, to respond to future demographic, social and lifestyle changes and to improve resilience.
Acheiving this will require interdsiciplinary collaboration and a complex systems perspective. Recent reports from, e.g., the Institute for Public Policy Research, the Institution of Civil Engineers, the Council for Science and Technology, and the Cabinet Office agree that achieving and sustaining resilience is a key challenge facing the UK’s infrastructure systems. Examples of stresses and shocks range from climate change and demograhpic change, to systemic failure and terrorist attack. The complex, disparate and interconnected nature of the UK’s infrastructure is a key concern. Our infrastructure systems are highly fragmented both in terms of their governance and in terms of the number of agencies charged with achieving and maintaining resilience, which range from national government to local services and even community groups and local resilience forums. Moreover, the cross-sector interactions amongst different technological and techno-social systems within national infrastructure systems are not well understood. AIC research in modelling and managing infrastrcture is working towards a better understanding of the resilience implications of our current and future infrastructural organisation; and vehicles for effectively conveying this understanding to the full range of relevant stakeholders.
We are surrounded by and embedded in social systems that were not planned or designed but rather grew out of historical contingency. For example, consider the global trade network, global financial markets, systems of national government, education systems, and demographic phenomena such as the family, the neighbourhood, the town, and the city. In some cases we are confident that our social institutions are both well-adapted and worth preserving, e.g., the system of trial by jury, or the separation of powers between legislative, judicial, and executive branches of government. In other cases (e.g., global trade imbalances and wealth inequality) most would agree that the current state of affairs is unjust or inefficient, but the difficulty is in finding a feasible path to a better arrangement. Pervasive social systems are not easily "switched off" while a new and improved model is installed.
The AIC group uses agent-based computing and ideas from economics in order to build robust multi-agent systems in software and hardware. The same methods (agent-based modelling, optimization, mechanism design) can be applied to problematic social systems with a view to making clear the potential inefficiencies in the current arrangement, and proposing better ways of doing things in the future.
Examples of this work include the Care Life Cycle project, in which agent-based modelling researchers from the AIC group are working with social scientists in order to model the provision of formal and informal social care in the UK, a particularly pertinent issue given the demographic shift towards a more elderly population. A second strand of work includes models that highlight inefficiency and suggest reform in the institutions of science itself (e.g., funding, peer review, training, etc.).