Applications of agent technology

Submitting Institution

University of Southampton

Unit of Assessment

Computer Science and Informatics

Summary Impact Type

Technological

Research Subject Area(s)

Mathematical Sciences: Applied Mathematics
Information and Computing Sciences: Artificial Intelligence and Image Processing, Information Systems


Download original

PDF

Summary of the impact

Agent-based computing is a new paradigm for building complex socio-technical systems composed of many interacting intelligent and autonomous components. New co-ordination and negotiation algorithms developed at the University of Southampton, have provided new methods for managing such interactions in a flexible manner. This study focuses on their applications in two new start-up companies (Aerogility and Aroxo) in the defence, aerospace and civil contingency sectors (e.g. BAE Systems, Ministry of Defence and Hampshire County Council) in helping the GB Sailing Team to success at the 2012 Olympics, and in monitoring the environment for effects of climate change.

Underpinning research

Southampton's Agents, Interaction and Complexity Group (AICG) undertakes world-leading research into the science and engineering of complex socio-technical and socio-economic systems, that underpin the most pressing challenges facing society today. Problems as diverse as engineering resilient and sustainable smart infrastructure, refactoring healthcare 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, hardware robots and autonomous software agents. This has been the focus of Professors of Computer Science Nick Jennings (1999-) and Alex Rogers (2003-) and AICG Lecturers Sarvapali Ramchurn (2004-) Enrico Gerding (2005-) and Maria Polukarov (2007-). Fundamental underpinning research took place through a number of EPSRC projects: ALADDIN (2005-11, grant 1), ARGUS (2003-08, grant 2) Autonomic Computing (2008-2009, grant 3) Intelligent Systems for Disaster Management (ISDM) (2011-12, grant 4) Market-Based Control (MBC) (2005-10, grant 5) and ORCHID (2011-15, grant 6). Although several of these grants were collaborative in nature, most of the algorithms discussed in the impact section were developed solely by Southampton researchers (where this is not the case, Southampton researchers were joint inventors).

This body of work seeks to enable a number of autonomous components (agents) to flexibly interact with one another in complex environments, in order to achieve their individual and collective goals. As the agents are autonomous, the de facto mode of interaction is some form of negotiation and since there are interdependencies between the agents, their actions need to be coordinated if they are to be effective. Over the past decade, the Group has developed a suite of such approaches and has looked at both the theoretical properties of such interactions and how algorithms can be developed to facilitate computationally effective inter-working.

In terms of specific approaches, the key coordination technique is based on the max-sum algorithm: an efficient message-passing algorithm that supports decentralised decision making and control, developed on the ARGUS and ALADDIN projects [3.1]. An important complementary line of research, used Gaussian processes to make computationally efficient predictions about future events that involve significant degrees of uncertainty [3.2]. An earlier strand of work from ARGUS, led by Jennings, in collaboration with Kirk Martinez, Reader in Electronics and Computer Science (1997-) combined decision theoretic utility functions with information theory (specifically Kullback-Leibler divergence) to coordinate the sampling and information exchange in sensor networks [3.3]. The Group has also been very active in the area of coalition formation (mainly through ORCHID, ALADDIN and MBC) developing new algorithms for forming teams of agents and analysing the computational complexity of various stability concepts [3.4].

For automated negotiation work, the MBC project explored issues associated with using auctions and markets to undertake resource allocation in rapidly changing and highly uncertain domains. AICG researchers determined the optimal strategy that a bidding agent should use to maximise its return in a setting in which there are a series of auctions occurring simultaneously [3.5]. For encounters in which the agents need to interact with one another directly (in a bilateral encounter) the Group devised a number of heuristic negotiation strategies that built upon Jennings's seminal work in this area [3.6].

References to the research

(best three are starred)

*3.1 A. Rogers, A. Farinelli, R. Stranders and N. R. Jennings (2011) "Bounded approximate decentralized coordination via the max-sum algorithm" Artificial Intelligence 175 (2) 730-759.

 
 
 
 

*3.2 M. A. Osborne, S. J. Roberts, A. Rogers and N. R. Jennings (2012) "Real-time information processing of environmental sensor network data using Bayesian Gaussian processes" ACM Trans on Sensor Networks 9 (1) 1.1-1.32.

 
 
 
 

3.3 P. Padhy, R. K. Dash, K. Martinez and N. R. Jennings (2010) "A utility-based adaptive sensing and multi-hop communication protocol for wireless sensor networks" ACM Trans on Sensor Networks 6 (3) 27.1-27.39.

 
 
 
 

3.4 T. Rahwan, S. D. Ramchurn, A. Giovannucci and N. R. Jennings (2009) "An anytime algorithm for optimal coalition structure generation" Journal of AI Research 34 521-567.

3.5 E. H. Gerding, R. K. Dash, A. Byde and N. R. Jennings (2008) "Optimal strategies for bidding agents participating in simultaneous Vickrey auctions with perfect substitutes" Journal of AI Research 32 939-982.

*3.6 P. Faratin, C. Sierra, and N. R. Jennings (1998) "Negotiation decision functions for autonomous agents" Int. Journal of Robotics and Autonomous Systems 24 (3-4) 159-182

 
 
 
 

Grant 1 ALADDIN: PI Jennings; CoIs: Rogers, Ramchurn, Polukarov; "Autonomous Learning Agents for Decentralised Data and Information Systems"; BAE SYSTEMS/EPSRC (EP/C548051/1); 2005-2011; £5.4m.

Grant 2 ARGUS: PI Jennings; "Decentralised Data Fusion"; EPSRC/MoD/DTI (GR/S20727/01); 2003-2008; £1m.

Grant 3 Autonomic: PI Jennings; CoI: Rogers; "Autonomic Supply Chains in Computational Economies"; EPSRC (EP/F067143/1); 2008-2009; £120k.

Grant 4 MBC: PI Jennings; CoI: Gerding; "Market-Based Control"; EPSRC (GR/T10664/01); 2005-2010; £690k.

Grant 5 ISDM: PI Ramchurn; "Intelligent Systems for Disaster Management"; EPSRC Knowledge Transfer Scheme (EP/H500243/1); 2010-2011.

Grant 6 ORCHID: PI Jennings; CoIs: Rogers, Ramchurn; "Human-Agent Collectives"; EPSRC Programme Grant (EP/I011587/1); 2011-2016; £5.5m.

Details of the impact

New coordination and negotiation algorithms developed by the AICG, directly led to the creation of two independent start-ups (Aerogility and Aroxo), contributed to the economic growth of established businesses (e.g. BAE) informed key changes in public policy and services (e.g. Fawley) and served as a key technology for British Antarctic Survey environmental scientists.

Aerogility's main product is an agent-based business decision-support system, targeted at global aerospace and defence organisations. This was developed by Jennings, who, in his capacity as Chief Scientist, worked with Aerogility's product development team from the beginning of the company (established under the name Lostwax in 1999) to refine market-based negotiation algorithms developed through MBC and ALADDIN, so they could efficiently and effectively optimise aircraft scheduling and maintenance activities. This core intellectual property has directly led to Aerogility's growth. The company expanded its business to the United States in 2008 and currently employs 20 people. Since the beginning of the REF impact period, the system has been licenced by: i) Sikorsky Aerospace Services for the S-92 fleet (2009); ii) Lockheed Martin for the F-22 Raptor and F-35 fleets (2012); and iii) Boeing for the TLCS UK Chinook fleet (2012) with additional ongoing economic benefits from Aerogility's selection by BAE Systems for its Tornado, Harrier, Typhoon, Nimrod and Hawk fleets since 2006 [5.1]. Aerogility has twice received a BAE System's Chairman's Award. In 2007, it received a Bronze level for providing powerful decision-support for the UK Fleet Planners managing ATTAC, the strategic availability contract for the UK Tornado fleet valued in the region of £1.5 billion [5.8] and in 2008, a Silver level.

In 2009, Aroxo, an internet sales channel using heuristic negotiation algorithms developed as part of MBC and ALADDIN, was launched. Jennings worked with Aroxo's development teams to refine and scale the fundamental algorithms to enable online retailers to dynamically set prices for products in response to customer online bids. At its peak in 2011, the Aroxo marketplace controlled stock worth £10 million and dealt with up to 20,000 interactions per day [5.2; 5.9].

AICG research has led to improved performance in existing businesses. BAE Systems, in particular, has directly invested over £4 million (not including contributions in kind) in AICG research since 2005. In 2009, this enabled Jennings and Rogers to work with BAE staff to deploy the max-sum coordination algorithm to the problems of Force Threat Evaluation and Weapon Assignment (within Insyte's Combat Management System CMS-1) and, in 2010, for the collaborative control of multiple unmanned aerial vehicles and sensors [5.3, 5.10]. In both cases, the algorithms improved the performance of military platforms and sensors by enabling coordination to maximise operational effect. This work produced two patents and differentiating technologies that, since 2008, helped BAE secure £2 million in Ministry of Defence funding. This includes: i) BAE's selection to lead the Autonomous Systems Underpinning Research programme (approximate value £1 million); ii) a contract to demonstrate the benefit of agent-based computing in the context of the Network-Enabled Air Defence Surveillance programme (value £500k); and iii) £170k in Centre for Defence Enterprise funding to demonstrate the application of agent-based computing methods in defence (ISTAR) and security (intelligence processing) problems [5.10]. BAE Systems has also invested a significant amount of its Central Technology Programme research budget (worth over £1 million in 2012-13) on projects related to autonomy and agent-based computing that have been informed by Southampton's work and their ongoing relationship with Southampton researchers.

Further economic benefits were created through the university-owned business development agency ECS Partners Limited. Since 2008, they have secured commercial contracts involving the application of AICG agent tools and techniques worth £85k for: the Defence Science and Technology Laboratory, with respect to military logistics and for BAE Systems Insyte with respect to supply chain logistics; dismounted infantry patrols and autonomous power management [5.4].

The performance of other companies has been improved through AICG provision of training courses drawing upon this body of research. For example, across 2009/10, AICG staff ran three five-day intensive schools for 45 engineers from Roke Manor Research, BAE Systems, MBDA, Rolls-Royce and SELEX Galileo on agent-based techniques for defence applications [5.10].

In terms of societal impact, prediction algorithms developed by Rogers as part of ALADDIN, were deployed in a BAE prototype tool used to help the UK Sailing Team in the 2012 Olympics. The tool enabled improved accuracy of weather pattern forecasting in Weymouth Bay and Portland Harbour, with a view to providing the UK team with a competitive advantage [5.5, 5.10].

In 2010/11, ORCHID-derived coalition formation algorithms were incorporated into a large-scale agent-based disaster simulation platform that has impacted on public policy and services in Hampshire. Overseen by Ramchurn, Hampshire County Council's Emergency Planning Unit used the simulation to identify potential choke points in road networks and more accurately estimate civilian evacuation times for high-risk areas. For example, the Southampton-enabled simulation showed that the one hour estimated to evacuate Fawley Village needed to be revised upwards to three hours. As a direct result, Hampshire has enacted new congestion control strategies and changed its official operating procedures [5.11].

British Antarctic Survey scientists have benefited from work by Jennings and Martinez to coordinate sampling and information exchange in sensor networks, through the deployment of algorithms since 2012. Tools developed at Southampton were used to record temperature, pressure and orientation changes in the Briksdalsbreen glacier, Norway, providing new insights into the impact of climate change [5.6]. The Briksdalsbreen technology has received considerable media attention from, among others, BBC News at Ten [5.7] leading to increased public knowledge and awareness of climate change. Further public impact has been felt through use of the Briksdalsbreen findings in presentations on global warming by the Al Gore Climate Project in 2008 [5.12].

Sources to corroborate the impact

[5.1] Aerogility. http://www.aerogility.com/.

[5.2] Aroxo. http://www.aroxo.com; http://news.bbc.co.uk/1/hi/health/8185896.stm.

[5.3] ALADDIN Final Report. http://www.aladdinproject.org/.

[5.4] ECS Partners Ltd. http://www.ecspartners.ecs.soton.ac.uk/.

[5.5] http://www.baesystems.com/magazine/BAES_021279/.

[5.6] Glacsweb. http://glacsweb.org/pubs.html. This lists the earth science papers based on the data streams made possible by the project.

[5.7] BBC News at ten (http://www.youtube.com/watch?v=CY8AagMh_1M). BBC News on trials in Norway (http://news.bbc.co.uk/1/hi/technology/8297645.stm and http://www.millennium-project.org). BBC world service, BBC tech website, ACM news, UNICEF website, CBC Canada live news discussion, 26000 Google hits on "Glacsweb" mainly due to online discussion. Nature 2020 Computing (http://www.nature.com/nature/journal/v440/n7083/full/440402a.html)

[5.8] Executive Director, Aerogility Inc., London.

[5.9] Co-Founder, Aroxo UK Ltd., London.

[5.10] Research Manager, BAE Systems, Camberley.

[5.11] Head of Emergency Planning and Business Continuity, Hampshire County Council, Winchester.

[5.12] Glaciologist, British Antarctic Survey, Cambridge.