2012–2020 · Completed

Verification of Swarm Systems

Funded by Royal Academy of Engineering; EPSRC.

Kilobot swarm robots

Motivation

Swarm robotics is an approach to performing a task by using a large number of robots that coordinate to accomplish their common goal. Robotic swarms have been put forward a good alternative to single robots in a number of scenarios including tasks such as surveillance and maintenance of industrial plants.

In safety critical situations, it is necessary to verify that these swarm systems will behave as expected regardless of how many agents are present in the system. However, this cannot be achieved with traditional model checking techniques since it involves checking an unbounded number of systems. This project aims to develop novel model checking techniques that enable the verification of these unbounded multi-agent systems.

Objectives and current results

To enable the development of verification methods, the project aims at defining semantic models and formal specification languages for swarm systems.

A number of such semantics have been proposed, both for modelling synchronous systems (in which all the participants perform actions simultaneously) and asychronous systems (where participants may perform actions independently). Both non-deterministic and stochastic semantics have been considered, and formal specification languages have been explored ranging from those describing simple temporal properties to richer logics that can describe probabilistic, epistemic, or strategic properties.

These techniques have also been extended to address the verification of faulty systems (where the participants in the swarm may exhibit faults) and open systems (where participants of the swarm may leave or join at run-time).

More details on our current research can be found in the Software and Publications sections below.

Software

The following tools have been developed within the project:

  • A number of extensions to MCMAS to enable the verification of non-probabilistic unbounded multi-agent systems. These can be found here.
  • A number of variants of PSV (Probabilistic Swarm Verifier), which are built on top of PRISM and enable the verification of unbounded probabilistic multi-agent systems. These can be found here.

Team members

Principal investigator

Research associates

Collaborators

Funding

This research is supported by a Royal Academy of Engineering Chair in Emerging Technologies and an EPSRC-sponsored studentship.

It was previously also supported by an EPSRC fellowship on Trusted Autonomous Systems.

Publications

2020

IJCAI 2020

Verifying Fault-Tolerance in Probabilistic Swarm Systems

A. Lomuscio, E. Pirovano

Multi-agent systemsPDFDOI
BibTeX
@inproceedings{DBLP:conf/ijcai/LomuscioP20,
  author     = {Alessio Lomuscio and Edoardo Pirovano},
  title      = {{Verifying Fault-Tolerance in Probabilistic Swarm Systems}},
  booktitle  = {Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020},
  pages      = {325--331},
  publisher  = {ijcai.org},
  year       = {2020},
  doi        = {10.24963/IJCAI.2020/46}
}
AAMAS 2020

Parameterised Verification of Strategic Properties in Probabilistic Multi-Agent Systems

A. Lomuscio, E. Pirovano

Multi-agent systemsPDFPublisherVideo
BibTeX
@inproceedings{DBLP:conf/atal/LomuscioP20,
  author     = {Alessio Lomuscio and Edoardo Pirovano},
  title      = {{Parameterised Verification of Strategic Properties in Probabilistic Multi-Agent Systems}},
  booktitle  = {Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems, AAMAS '20, Auckland, New Zealand, May 9-13, 2020},
  pages      = {762--770},
  publisher  = {International Foundation for Autonomous Agents and Multiagent Systems},
  year       = {2020},
  url        = {https://dl.acm.org/doi/10.5555/3398761.3398852}
}

2019

AAMAS 2019

Formal Verification of Open Multi-Agent Systems

P. Kouvaros, A. Lomuscio, E. Pirovano, H. Punchihewa

Multi-agent systemsPDFPublisher
BibTeX
@inproceedings{DBLP:conf/atal/KouvarosLPP19,
  author     = {Panagiotis Kouvaros and Alessio Lomuscio and Edoardo Pirovano and Hashan Punchihewa},
  title      = {{Formal Verification of Open Multi-Agent Systems}},
  booktitle  = {Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS '19, Montreal, QC, Canada, May 13-17, 2019},
  pages      = {179--187},
  publisher  = {International Foundation for Autonomous Agents and Multiagent Systems},
  year       = {2019},
  url        = {http://dl.acm.org/citation.cfm?id=3331691}
}
AAMAS 2019

A Counter Abstraction Technique for the Verification of Probabilistic Swarm Systems

A. Lomuscio, E. Pirovano

Multi-agent systemsPDFPublisher
BibTeX
@inproceedings{DBLP:conf/atal/LomuscioP19,
  author     = {Alessio Lomuscio and Edoardo Pirovano},
  title      = {{A Counter Abstraction Technique for the Verification of Probabilistic Swarm Systems}},
  booktitle  = {Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS '19, Montreal, QC, Canada, May 13-17, 2019},
  pages      = {161--169},
  publisher  = {International Foundation for Autonomous Agents and Multiagent Systems},
  year       = {2019},
  url        = {http://dl.acm.org/citation.cfm?id=3331689}
}

2018

IJCAI 2018

Symbolic Synthesis of Fault-Tolerance Ratios in Parameterised Multi-Agent Systems

P. Kouvaros, A. Lomuscio, E. Pirovano

Multi-agent systemsPDFDOI
BibTeX
@inproceedings{DBLP:conf/ijcai/KouvarosLP18,
  author     = {Panagiotis Kouvaros and Alessio Lomuscio and Edoardo Pirovano},
  title      = {{Symbolic Synthesis of Fault-Tolerance Ratios in Parameterised Multi-Agent Systems}},
  booktitle  = {Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI 2018, July 13-19, 2018, Stockholm, Sweden},
  pages      = {324--330},
  publisher  = {ijcai.org},
  year       = {2018},
  doi        = {10.24963/IJCAI.2018/45}
}
IJCAI 2018

Verifying Emergence of Bounded Time Properties in Probabilistic Swarm Systems

A. Lomuscio, E. Pirovano

Multi-agent systemsPDFDOI
BibTeX
@inproceedings{DBLP:conf/ijcai/LomuscioP18,
  author     = {Alessio Lomuscio and Edoardo Pirovano},
  title      = {{Verifying Emergence of Bounded Time Properties in Probabilistic Swarm Systems}},
  booktitle  = {Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI 2018, July 13-19, 2018, Stockholm, Sweden},
  pages      = {403--409},
  publisher  = {ijcai.org},
  year       = {2018},
  doi        = {10.24963/IJCAI.2018/56}
}
Other 2018

Towards the Formal Verification of Correctness and Robustness of Robot Swarms (Invited Talk)

P. Kouvaros, A. Lomuscio

Multi-agent systemsPDF
BibTeX
@inproceedings{SAIL:2018-towards-the-formal-verification-of-correctness,
  author     = {P. Kouvaros and A. Lomuscio},
  title      = {{Towards the Formal Verification of Correctness and Robustness of Robot Swarms (Invited Talk)}},
  booktitle  = {Proceedings of the 18th Italian Conference on Theoretical Computer Science and the 32nd Italian Conference on Computational Logic.},
  year       = {2018}
}

2017

IJCAI 2017

Verifying Fault-tolerance in Parameterised Multi-Agent Systems

P. Kouvaros, A. Lomuscio

Multi-agent systemsPDFDOI
BibTeX
@inproceedings{DBLP:conf/ijcai/KouvarosL17,
  author     = {Panagiotis Kouvaros and Alessio Lomuscio},
  title      = {{Verifying Fault-tolerance in Parameterised Multi-Agent Systems}},
  booktitle  = {Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia, August 19-25, 2017},
  pages      = {288--294},
  publisher  = {ijcai.org},
  year       = {2017},
  doi        = {10.24963/IJCAI.2017/41}
}
IJCAI 2017

Parameterised Verification of Data-aware Multi-Agent Systems

F. Belardinelli, P. Kouvaros, A. Lomuscio

Multi-agent systemsPDFDOI
BibTeX
@inproceedings{DBLP:conf/ijcai/BelardinelliKL17,
  author     = {Francesco Belardinelli and Panagiotis Kouvaros and Alessio Lomuscio},
  title      = {{Parameterised Verification of Data-aware Multi-Agent Systems}},
  booktitle  = {Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia, August 19-25, 2017},
  pages      = {98--104},
  publisher  = {ijcai.org},
  year       = {2017},
  doi        = {10.24963/IJCAI.2017/15}
}
AAAI 2017

Parameterised Verification of Infinite State Multi-Agent Systems via Predicate Abstraction

P. Kouvaros, A. Lomuscio

Multi-agent systemsPDFDOI
BibTeX
@inproceedings{DBLP:conf/aaai/KouvarosL17,
  author     = {Panagiotis Kouvaros and Alessio Lomuscio},
  title      = {{Parameterised Verification of Infinite State Multi-Agent Systems via Predicate Abstraction}},
  booktitle  = {Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, February 4-9, 2017, San Francisco, California, USA},
  pages      = {3013--3020},
  publisher  = {AAAI Press},
  year       = {2017},
  doi        = {10.1609/AAAI.V31I1.10710}
}

2016

ECAI 2016

Parameterised Model Checking for Alternating-Time Temporal Logic

P. Kouvaros, A. Lomuscio

Multi-agent systemsPDFDOI
BibTeX
@inproceedings{DBLP:conf/ecai/KouvarosL16,
  author     = {Panagiotis Kouvaros and Alessio Lomuscio},
  title      = {{Parameterised Model Checking for Alternating-Time Temporal Logic}},
  booktitle  = {ECAI 2016 - 22nd European Conference on Artificial Intelligence, 29 August-2 September 2016, The Hague, The Netherlands - Including Prestigious Applications of Artificial Intelligence (PAIS 2016)},
  series     = {Frontiers in Artificial Intelligence and Applications},
  volume     = {285},
  pages      = {1230--1238},
  publisher  = {IOS Press},
  year       = {2016},
  doi        = {10.3233/978-1-61499-672-9-1230}
}
AAMAS 2016

Formal Verification of Opinion Formation in Swarms

P. Kouvaros, A. Lomuscio

Multi-agent systemsPDFPublisher
BibTeX
@inproceedings{DBLP:conf/atal/KouvarosL16,
  author     = {Panagiotis Kouvaros and Alessio Lomuscio},
  title      = {{Formal Verification of Opinion Formation in Swarms}},
  booktitle  = {Proceedings of the 2016 International Conference on Autonomous Agents \& Multiagent Systems, Singapore, May 9-13, 2016},
  pages      = {1200--1208},
  publisher  = {ACM},
  year       = {2016},
  url        = {http://dl.acm.org/citation.cfm?id=2937099}
}
AAMAS 2016

Verifying Security Properties in Unbounded Multiagent Systems

I. Boureanu, P. Kouvaros, A. Lomuscio

Multi-agent systemsPDFPublisher
BibTeX
@inproceedings{DBLP:conf/atal/BoureanuKL16,
  author     = {Ioana Boureanu and Panagiotis Kouvaros and Alessio Lomuscio},
  title      = {{Verifying Security Properties in Unbounded Multiagent Systems}},
  booktitle  = {Proceedings of the 2016 International Conference on Autonomous Agents \& Multiagent Systems, Singapore, May 9-13, 2016},
  pages      = {1209--1217},
  publisher  = {ACM},
  year       = {2016},
  url        = {http://dl.acm.org/citation.cfm?id=2937100}
}
AIJ 2016

Parameterised verification for multi-agent systems

P. Kouvaros, A. Lomuscio

Multi-agent systemsDOIPublisher
BibTeX
@article{DBLP:journals/ai/KouvarosL16,
  author     = {Panagiotis Kouvaros and Alessio Lomuscio},
  title      = {{Parameterised verification for multi-agent systems}},
  journal    = {Artif. Intell.},
  volume     = {234},
  pages      = {152--189},
  year       = {2016},
  doi        = {10.1016/J.ARTINT.2016.01.008}
}

2015

IJCAI 2015

Verifying Emergent Properties of Swarms

P. Kouvaros, A. Lomuscio

Multi-agent systemsPDFPublisher
BibTeX
@inproceedings{DBLP:conf/ijcai/KouvarosL15,
  author     = {Panagiotis Kouvaros and Alessio Lomuscio},
  title      = {{Verifying Emergent Properties of Swarms}},
  booktitle  = {Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015, Buenos Aires, Argentina, July 25-31, 2015},
  pages      = {1083--1089},
  publisher  = {AAAI Press},
  year       = {2015},
  url        = {http://ijcai.org/Abstract/15/157}
}

2013

IJCAI 2013

A Cutoff Technique for the Verification of Parameterised Interpreted Systems with Parameterised Environments

P. Kouvaros, A. Lomuscio

Multi-agent systemsPDFPublisher
BibTeX
@inproceedings{DBLP:conf/ijcai/KouvarosL13,
  author     = {Panagiotis Kouvaros and Alessio Lomuscio},
  title      = {{A Cutoff Technique for the Verification of Parameterised Interpreted Systems with Parameterised Environments}},
  booktitle  = {IJCAI 2013, Proceedings of the 23rd International Joint Conference on Artificial Intelligence, Beijing, China, August 3-9, 2013},
  pages      = {2013--2019},
  publisher  = {IJCAI/AAAI},
  year       = {2013},
  url        = {http://ijcai.org/Abstract/13/297}
}
AAMAS 2013

Automatic Verification of Parametrised Interleaved Multi-Agent Systems

P. Kouvaros, A. Lomuscio

Multi-agent systemsPDF
BibTeX
@inproceedings{SAIL:2013-automatic-verification-of-parametrised-interleaved-multi,
  author     = {P. Kouvaros and A. Lomuscio},
  title      = {{Automatic Verification of Parametrised Interleaved Multi-Agent Systems}},
  booktitle  = {Proceedings of the 12th International Conference on Autonomous Agents and Multi-Agent systems (AAMAS13). Saint Paul, MN, USA. pp 861-868. IFAAMAS Press.},
  year       = {2013}
}