ensuremathThe industry related to electric vehicles (EVs) has seen a substantial increase in recent years, as such vehicles have the ability to significantly reduce total COensuremath2ensuremath emissions and the related global warming effect. In this paper, we focus on the problem of allocating EVs to charging stations, scheduling and pricing their charging. Specifically, we developed a Mixed Integer Program (MIP) which executes offline and optimally allocates EVs to charging stations. On top, we propose two alternative mechanisms to price the electricity the EVs charge. The first mechanism is a typical fixed-price one, while the second is a variation of the Vickrey?Clark?Groves (VCG) mechanism. We also developed online solutions that incrementally call the MIP-based algorithm and solve it for branches of EVs. In all cases, the EVs? aim is to minimize the price to pay and the impact on their driving schedule, acting as self-interested agents. We conducted a thorough empirical evaluation of our mechanisms and we observed that they had satisfactory scalability. Additionally, the VCG mechanism achieved an up to 2.2% improvement in terms of the number of vehicles that were charged compared to the fixed-price one and, in cases where the stations were congested, it calculated higher prices for the EVs and provided a higher profit for the stations, but lower utility to the EVs. However, in a theoretical evaluation, we proved that the variant of the VCG mechanism being proposed in this paper still guaranteed truthful reporting of the EVs? preferences. In contrast, the fixed-price one was found to be vulnerable to agents? strategic behavior as non-truthful EVs can charge instead of truthful ones. Finally, we observed the online algorithms to be, on average, at 95.6% of the offline ones in terms of the average number of serviced EVs.ensuremath

https://eprints.soton.ac.uk/455806/

@article{soton455806,
title = {Mechanism design for efficient offline and online allocation of electric vehicles to charging stations},
author = {Emmanouil S Rigas and Enrico H Gerding and Sebastian Stein and Sarvapali D Ramchurn and Nick Bassiliades},
url = {https://eprints.soton.ac.uk/455806/},
year = {2022},
date = {2022-03-01},
journal = {Energies},
volume = {15},
number = {5},
abstract = {ensuremathThe industry related to electric vehicles (EVs) has seen a substantial increase in recent years, as such vehicles have the ability to significantly reduce total COensuremath2ensuremath emissions and the related global warming effect. In this paper, we focus on the problem of allocating EVs to charging stations, scheduling and pricing their charging. Specifically, we developed a Mixed Integer Program (MIP) which executes offline and optimally allocates EVs to charging stations. On top, we propose two alternative mechanisms to price the electricity the EVs charge. The first mechanism is a typical fixed-price one, while the second is a variation of the Vickrey?Clark?Groves (VCG) mechanism. We also developed online solutions that incrementally call the MIP-based algorithm and solve it for branches of EVs. In all cases, the EVs? aim is to minimize the price to pay and the impact on their driving schedule, acting as self-interested agents. We conducted a thorough empirical evaluation of our mechanisms and we observed that they had satisfactory scalability. Additionally, the VCG mechanism achieved an up to 2.2% improvement in terms of the number of vehicles that were charged compared to the fixed-price one and, in cases where the stations were congested, it calculated higher prices for the EVs and provided a higher profit for the stations, but lower utility to the EVs. However, in a theoretical evaluation, we proved that the variant of the VCG mechanism being proposed in this paper still guaranteed truthful reporting of the EVs? preferences. In contrast, the fixed-price one was found to be vulnerable to agents? strategic behavior as non-truthful EVs can charge instead of truthful ones. Finally, we observed the online algorithms to be, on average, at 95.6% of the offline ones in terms of the average number of serviced EVs.ensuremath},
note = {Funding Information: Funding: This research study was co-financed by Greece and the European Union (European Social Fund--ESF) through the Operational Programme ?Human Resources Development, Education and Lifelong Learning? in the context of the project ?Reinforcement of Postdoctoral Researchers-2nd Cycle? (MIS-5033021), implemented by State Scholarships Foundation (IKY).
Copyright 2022 Elsevier B.V., All rights reserved.},
keywords = {},
pubstate = {published},
tppubtype = {article} }

In Multiple Instance Learning (MIL), models are trained using bags of instances, where only a single label is provided for each bag. A bag label is often only determined by a handful of key instances within a bag, making it difficult to interpret what information a classifier is using to make decisions. In this work, we establish the key requirements for interpreting MIL models. We then go on to develop several model-agnostic approaches that meet these requirements. Our methods are compared against existing inherently interpretable MIL models on several datasets, and achieve an increase in interpretability accuracy of up to 30%. We also examine the ability of the methods to identify interactions between instances and scale to larger datasets, improving their applicability to real-world problems.

https://eprints.soton.ac.uk/454952/

@inproceedings{soton454952,
title = {Model agnostic interpretability for multiple instance learning},
author = {Joseph Early and Christine Evers and Sarvapali Ramchurn},
url = {https://eprints.soton.ac.uk/454952/},
year = {2022},
date = {2022-01-01},
booktitle = {International Conference on Learning Representations 2022 (25/04/22 - 29/04/22)},
abstract = {In Multiple Instance Learning (MIL), models are trained using bags of instances, where only a single label is provided for each bag. A bag label is often only determined by a handful of key instances within a bag, making it difficult to interpret what information a classifier is using to make decisions. In this work, we establish the key requirements for interpreting MIL models. We then go on to develop several model-agnostic approaches that meet these requirements. Our methods are compared against existing inherently interpretable MIL models on several datasets, and achieve an increase in interpretability accuracy of up to 30%. We also examine the ability of the methods to identify interactions between instances and scale to larger datasets, improving their applicability to real-world problems.},
note = {25 pages (9 content, 2 acknowledgement + references, 14 appendix). 16 figures (3 main content, 13 appendix). Submitted and accepted to ICLR 22, see http://openreview.net/forum?id=KSSfF5lMIAg . Revision: added additional acknowledgements},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings} }

This report is the Trustworthy Autonomous Hub (TAS-hub) response to the call for evidence from the Joint Committee on the Draft Online Safety Bill. The Joint Committee was established to consider the Government's draft Bill to establish a new regulatory framework to tackle harmful content online.

https://eprints.soton.ac.uk/451428/

@techreport{soton451428,
title = {A Response to Draft Online Safety Bill: A call for evidence from the Joint Committee},
author = {Sarvapali Ramchurn and Stuart Middleton and Derek McAuley and Helena Webb and Richard Hyde and Justyna Lisinska},
url = {https://eprints.soton.ac.uk/451428/},
year = {2021},
date = {2021-09-01},
number = {10.18742/pub01-060},
abstract = {This report is the Trustworthy Autonomous Hub (TAS-hub) response to the call for evidence from the Joint Committee on the Draft Online Safety Bill. The Joint Committee was established to consider the Government's draft Bill to establish a new regulatory framework to tackle harmful content online.},
keywords = {},
pubstate = {published},
tppubtype = {techreport} }

In this paper, we foreground some of the key research challenges that arise in the design of trustworthy human-AI partnerships. In particular, we focus on the challenges in designing human-AI partnerships that need to be addressed to help humans and organisations trust their machine counterparts individually or as a collective (e.g., as robot teams or groups of software agents). We also aim to identify the risks associated with human-AI partnerships and therefore determine the associated measures to mitigate these risks. By so doing, we will trigger new avenues of research that will address the key barriers to the adoption of AI-based systems more widely in our daily lives and in industry.

https://eprints.soton.ac.uk/450597/

@article{soton450597,
title = {Trustworthy human-AI partnerships},
author = {Sarvapali Ramchurn and Sebastian Stein and Nicholas R Jennings},
url = {https://eprints.soton.ac.uk/450597/},
year = {2021},
date = {2021-08-01},
journal = {iScience},
volume = {24},
number = {8},
abstract = {In this paper, we foreground some of the key research challenges that arise in the design of trustworthy human-AI partnerships. In particular, we focus on the challenges in designing human-AI partnerships that need to be addressed to help humans and organisations trust their machine counterparts individually or as a collective (e.g., as robot teams or groups of software agents). We also aim to identify the risks associated with human-AI partnerships and therefore determine the associated measures to mitigate these risks. By so doing, we will trigger new avenues of research that will address the key barriers to the adoption of AI-based systems more widely in our daily lives and in industry.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}

This report is a response to the call for evidence from the Department for Business, Energy & Industrial Strategy and the Centre for Connected and Autonomous Vehicles on the future of connected and automated mobility in the UK.ensuremath
Executive Summary:Despite relative weaknesses in global collaboration and co-creation platforms, smart road and communication infrastructure, urban planning, and public awareness, the United Kingdom (UK) has a substantial strength in the area of Connected and Automated Mobility (CAM) by investing in research and innovation platforms for developing the underlying technologies, creating impact, and co-creation leading to innovative solutions. Many UK legal and policymaking initiatives in this domain are world leading. To sustain the UK?s leading position, we make the following recommendations:? The development of financial and policy-related incentive schemes for research and innovation in the foundations and applications of autonomous systems as well as schemes for proof of concepts, and commercialisation.? Supporting policy and standardisation initiatives as well as engagement and community-building activities to increase public awareness and trust.? Giving greater attention to integrating CAM/Connected Autonomous Shared Electric vehicles (CASE) policy with related government priorities for mobility, including supporting active transport and public transport, and improving air quality.? Further investment in updating liability and risk models and coming up with innovative liability schemes covering the Autonomous Vehicles (AVs) ecosystem.? Investing in training and retraining of the work force in the automotive, mobility, and transport sectors, particularly with skills concerningArtificial Intelligence (AI), software and computer systems, in order to ensure employability and an adequate response to the drastically changing industrial landscape

https://eprints.soton.ac.uk/450228/

@techreport{soton450228,
title = {The future of connected and automated mobility in the UK: call for evidence},
author = {Sarvapali Ramchurn and Mohammad Reza Mousavi and Seyed Mohammad Hossein Toliyat and Mark Kleinman and Justyna Lisinska and Diego Sempreboni and Sebastian Stein and Enrico Gerding and Richard Gomer and Francesco DÁmore},
editor = {Wassim Dbouk},
url = {https://eprints.soton.ac.uk/450228/},
year = {2021},
date = {2021-07-01},
number = {10.5258/SOTON/P0097},
publisher = {University of Southampton},
abstract = {This report is a response to the call for evidence from the Department for Business, Energy & Industrial Strategy and the Centre for Connected and Autonomous Vehicles on the future of connected and automated mobility in the UK.ensuremath
Executive Summary:Despite relative weaknesses in global collaboration and co-creation platforms, smart road and communication infrastructure, urban planning, and public awareness, the United Kingdom (UK) has a substantial strength in the area of Connected and Automated Mobility (CAM) by investing in research and innovation platforms for developing the underlying technologies, creating impact, and co-creation leading to innovative solutions. Many UK legal and policymaking initiatives in this domain are world leading. To sustain the UK?s leading position, we make the following recommendations:? The development of financial and policy-related incentive schemes for research and innovation in the foundations and applications of autonomous systems as well as schemes for proof of concepts, and commercialisation.? Supporting policy and standardisation initiatives as well as engagement and community-building activities to increase public awareness and trust.? Giving greater attention to integrating CAM/Connected Autonomous Shared Electric vehicles (CASE) policy with related government priorities for mobility, including supporting active transport and public transport, and improving air quality.? Further investment in updating liability and risk models and coming up with innovative liability schemes covering the Autonomous Vehicles (AVs) ecosystem.? Investing in training and retraining of the work force in the automotive, mobility, and transport sectors, particularly with skills concerningArtificial Intelligence (AI), software and computer systems, in order to ensure employability and an adequate response to the drastically changing industrial landscape}, note = {The UKRI TAS Hub assembles a team from the Universities of Southampton, Nottingham and King?s College London. The Hub sits at the centre of the pounds33M Trustworthy Autonomous Systems Programme, funded by the UKRI Strategic Priorities Fund.
The role of the TAS Hub is to coordinate and work with six research nodes to establish a collaborative platform for the UK to enable the development of socially beneficial autonomous systems that are both trustworthy in principle and trusted in practice by individuals, society and government. Read more about the TAS Hub at https://www.tas.ac.uk/aboutus/overview/},
keywords = {},
pubstate = {published},
tppubtype = {techreport} }

In this paper, we propose a novel decentralised agent-based mechanism for road intersection management for connected autonomous vehicles. In our work we focus on road obstructions causing major traffic delays. In doing so, we propose the first decentralised mechanism able to maximise the overall vehicle throughput at intersections in the presence of obstructions. The distributed algorithm transfers most of the computational cost from the intersection manager to the driving agents, thereby improving scalability. Our realistic empirical experiments using SUMO show that, when an obstacle is located at the entrance or in the middle of the intersection, existing state of the art algorithms and traffic lights show a reduced throughput of 65?90% from the optimal point without obstructions while our mechanism can maintain the throughput upensuremath
Q7 to 94?99%.

https://eprints.soton.ac.uk/449675/

@article{soton449675,
title = {Resilient intersection management with multi-vehicle collision avoidance},
author = {Phuriwat Worrawichaipat and Enrico Gerding and Ioannis Kaparias and Sarvapali Ramchurn},
url = {https://eprints.soton.ac.uk/449675/},
year = {2021},
date = {2021-06-01},
journal = {Frontiers in Sustainable Cities},
volume = {3},
abstract = {In this paper, we propose a novel decentralised agent-based mechanism for road intersection management for connected autonomous vehicles. In our work we focus on road obstructions causing major traffic delays. In doing so, we propose the first decentralised mechanism able to maximise the overall vehicle throughput at intersections in the presence of obstructions. The distributed algorithm transfers most of the computational cost from the intersection manager to the driving agents, thereby improving scalability. Our realistic empirical experiments using SUMO show that, when an obstacle is located at the entrance or in the middle of the intersection, existing state of the art algorithms and traffic lights show a reduced throughput of 65?90% from the optimal point without obstructions while our mechanism can maintain the throughput upensuremath Q7 to 94?99%.},
keywords = {},
pubstate = {published},
tppubtype = {article} }

The†Coalition Formation with Spatial and Temporal constraints Problem†(CFSTP) is a multi-agent task allocation problem in which few agents have to perform many tasks, each with its deadline and workload. To maximize the number of completed tasks, the agents need to cooperate by forming, disbanding and reforming coalitions. The original mathematical programming formulation of the CFSTP is difficult to implement, since it is lengthy and based on the problematic Big-M method. In this paper, we propose a compact and easy-to-implement formulation. Moreover, we design D-CTS, a distributed version of the state-of-the-art CFSTP algorithm. Using public London Fire Brigade records, we create a dataset with 347588 tasks and a test framework that simulates the mobilization of firefighters in dynamic environments. In problems with up†to 150 agents and 3000 tasks, compared to DSA-SDP, a state-of-the-art distributed algorithm, D-CTS completes†3.79%$pm$[42.22%,1.96%]†more tasks, and is one order of magnitude more efficient in terms of communication overhead and time complexity. D-CTS sets the first large-scale, dynamic and distributed CFSTP benchmark.ensuremath

https://eprints.soton.ac.uk/452050/

@article{soton452050,
title = {Large-scale, dynamic and distributed coalition formation with spatial and†temporal constraints},
author = {Luca Capezzuto and Danesh Tarapore and Sarvapali Ramchurn},
url = {https://eprints.soton.ac.uk/452050/},
year = {2021},
date = {2021-05-01},
journal = {Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)},
pages = {108--125},
abstract = {The†Coalition Formation with Spatial and Temporal constraints Problem†(CFSTP) is a multi-agent task allocation problem in which few agents have to perform many tasks, each with its deadline and workload. To maximize the number of completed tasks, the agents need to cooperate by forming, disbanding and reforming coalitions. The original mathematical programming formulation of the CFSTP is difficult to implement, since it is lengthy and based on the problematic Big-M method. In this paper, we propose a compact and easy-to-implement formulation. Moreover, we design D-CTS, a distributed version of the state-of-the-art CFSTP algorithm. Using public London Fire Brigade records, we create a dataset with 347588 tasks and a test framework that simulates the mobilization of firefighters in dynamic environments. In problems with up†to 150 agents and 3000 tasks, compared to DSA-SDP, a state-of-the-art distributed algorithm, D-CTS completes†3.79%$pm$[42.22%,1.96%]†more tasks, and is one order of magnitude more efficient in terms of communication overhead and time complexity. D-CTS sets the first large-scale, dynamic and distributed CFSTP benchmark.ensuremath },
keywords = {},
pubstate = {published},
tppubtype = {article} }

The Coalition Formation with Spatial and Temporal constraints Problem (CFSTP) is a multi-agent task allocation problem where the tasks are spatially distributed, with deadlines and workloads, and the number of agents is typically much smaller than the number of tasks. To maximise the number of completed tasks, the agents may have to schedule coalitions. The state-of-the-art CFSTP solver, the Coalition Formation with Look-Ahead (CFLA) algorithm, has two main limitations. First, its time complexity is exponential with the number of agents. Second, as we show, its look-ahead technique is not effective in real-world scenarios, such as open multi-agent systems, where new tasks can appear at any time. In this work, we study its design and define a variant, called Coalition Formation with Improved Look-Ahead (CFLA2), which achieves better performance. Since we cannot eliminate the limitations of CFLA in CFLA2, we also develop a novel algorithm to solve the CFSTP, the first to be simultaneously anytime, efficient and with convergence guarantee, called Cluster-based Task Scheduling (CTS). In tests where the look-ahead technique is highly effective, CTS completes up to 30% (resp. 10%) more tasks than CFLA (resp. CFLA2) while being up to 4 orders of magnitude faster. We also propose S-CTS, a simplified but parallel variant of CTS with even lower time complexity. Using scenarios generated by the RoboCup Rescue Simulation, we show that S-CTS is at most 10% less performing than high-performance algorithms such as Binary Max-Sum and DSA, but up to 2 orders of magnitude faster. Our results affirm CTS as the new state-of-the-art algorithm to solve the CFSTP.

https://eprints.soton.ac.uk/467373/

@article{soton467373,
title = {Anytime and efficient multi-agent coordination for disaster response},
author = {Luca Capezzuto and Danesh Tarapore and Sarvapali D Ramchurn},
url = {https://eprints.soton.ac.uk/467373/},
year = {2021},
date = {2021-03-01},
journal = {SN Computer Science},
volume = {2},
number = {3},
abstract = {The Coalition Formation with Spatial and Temporal constraints Problem (CFSTP) is a multi-agent task allocation problem where the tasks are spatially distributed, with deadlines and workloads, and the number of agents is typically much smaller than the number of tasks. To maximise the number of completed tasks, the agents may have to schedule coalitions. The state-of-the-art CFSTP solver, the Coalition Formation with Look-Ahead (CFLA) algorithm, has two main limitations. First, its time complexity is exponential with the number of agents. Second, as we show, its look-ahead technique is not effective in real-world scenarios, such as open multi-agent systems, where new tasks can appear at any time. In this work, we study its design and define a variant, called Coalition Formation with Improved Look-Ahead (CFLA2), which achieves better performance. Since we cannot eliminate the limitations of CFLA in CFLA2, we also develop a novel algorithm to solve the CFSTP, the first to be simultaneously anytime, efficient and with convergence guarantee, called Cluster-based Task Scheduling (CTS). In tests where the look-ahead technique is highly effective, CTS completes up to 30% (resp. 10%) more tasks than CFLA (resp. CFLA2) while being up to 4 orders of magnitude faster. We also propose S-CTS, a simplified but parallel variant of CTS with even lower time complexity. Using scenarios generated by the RoboCup Rescue Simulation, we show that S-CTS is at most 10% less performing than high-performance algorithms such as Binary Max-Sum and DSA, but up to 2 orders of magnitude faster. Our results affirm CTS as the new state-of-the-art algorithm to solve the CFSTP.},
keywords = {},
pubstate = {published},
tppubtype = {article} }