Chance-constrained MPC for voronoi-based multi-agent system deployment

IFAC PapersOnLine 53-2 (2020) 6969–6974 ScienceDirect ScienceDirect Available online at www.sciencedirect.com 2405-8963 Copyright © 2020 The Authors. This is an open access article under the CC BY-NC-ND license . Peer review under responsibility of International Federation of Automatic Control. 10.1016/j.ifacol.2020.12.417 10.1016/j.ifacol.2020.12.417 2405-8963 Copyright © 2020 The Authors. This is an open access article under the CC BY-NC-ND license ( http://creativecommons.org/licenses/by-nc-nd/4.0 ) Chance-Constrained MPC for Voronoibased Multi-Agent System Deployment  Thomas Chevet ∗Cristina Stoica Maniu ∗Cristina Vlad ∗ Youmin Zhang ∗∗ Eduardo F. Camacho ∗∗∗ ∗Universit´e Paris-Saclay, CNRS, CentraleSup´elec, Laboratoire des signaux et syst`emes, 91190, Gif-sur-Yvette, France. (e-mail: {thomas.chevet, cristina.stoica, cristina.vlad}@l2s.centralesupelec.fr) ∗∗ Department of Mechanical, Industrial and Aerospace Engineering, Concordia University, 1455 Blvd. de Maisonneuve, Montr´eal, QC H3G 1M8, Canada. (e-mail: [email protected]) ∗∗∗ Departemento de Ingenier´ıa de Sistemas y Autom´atica, Universidad de Sevilla, Camino de los Descubrimientos, 41092 Sevilla, Spain. (e-mail: [email protected]) Abstract: This paper proposes a new chance-constrained model predictive control (CCMPC) algorithm with state estimation applied to the two-dimensional deployment of a multi-vehicle system where each agent is subject to process noise and measurement noise. The bounded convex area of deployment is partitioned into time-varying Voronoi cells defined by the position of each agent. Due to the presence of noise in the system model, stochastic constraints appear in the model predictive control problem. The proposed decentralized robust CCMPC algorithm drives the multi-agent system into a static Chebyshev configuration where each agent lies on the Chebyshev center of its Voronoi cell. Simulation results show the effectiveness of the proposed control strategy on a fleet of quadrotors subject to wind perturbations and measurement noise. Keywords: Multi-agent systems, Decentralized control, Model predictive control 1. INTRODUCTION To carry out monitoring or search missions, a multiagent system (MAS) composed of unmanned vehicles can be deployed over a bounded convex area (Cortes et al., 2004). Several solutions exist for the deployment problem (Schwager et al., 2011) but often rely on a dynamic Voronoi tessellation (Vorono¨ı, 1908) of the area of interest. The objective is usually to drive the MAS into a centroidal Voronoi configuration where the objective of each agent is to reach the center of mass of the Voronoi cell (Sharifi et al., 2015) or into a Chebyshev configuration where the objective is the Chebyshev center (Nguyen et al., 2017; Hatleskog et al., 2018; Chevet et al., 2020) of the cell, which is often less complex to compute than the center of mass. In this context, the Voronoi cells and objective points are time-varying due to the movement of the agents which are constrained to remain inside their cells. The control algorithm then has to drive each agent to its objective under this time-varying movement constraint. Generally, the literature deals with the nominal case, i.e. uncertainties/perturbations are not considered. However, real systems are subject to perturbations (e.g. wind gusts)  The authors acknowledge the LIA of the CNRS on Information, Learning and Control, MEECOD project (“Moderniser l’Enseignement par l’Exp´erimentation sur la COordination de Drones”) supported by UPSaclay, the Natural Sciences and Engineering Research Council of Canada, MEyC Spain (contract DPI2016- 76493-C3-1-R), the European Research Council and the UE ERDF (Advanced Grant OCONTSOLAR, Project ID: 789051). and noises (e.g. measurement noise from sensors). The perturbations acting on the system can be modeled using deterministic or stochastic approaches. The deterministic approach requires a model of the perturbation while the stochastic approach only requires a mean and a covariance. In order to deal with these stochastic perturbations, several control methods have been proposed for a single agent, such as H∞ (Ugrinovskii, 1998) or optimal control (Petersen et al., 2000), and for several agents, such as consensus (Ma et al., 2017) or predictive control (Dai et al., 2017). Model predictive control (MPC) is used for a wide variety of systems dealing with constraints, uncertainties, etc. MPC can also be used for the control of a multi-agent system either in a centralized, distributed or decentralized way. If the system is subject to bounded perturbations, robust MPC strategies have been developed (Limon et al., 2010) in order to further guarantee the feasibility and stability properties for a simple system. However, if these perturbations have a stochastic nature and an unbounded support such as normally distributed noises, the classical deterministic robust MPC strategies will be too conservative. To handle this situation, several stochastic MPC algorithms have been proposed to control a single system (Farina et al., 2016) or a multi-agent system (Dai et al., 2017) subject to perturbations and probabilistic constraints. However, these methods often rely on a known bound for the perturbation and fixed constraints over time. In this paper, a MAS composed of several unmanned vehicles is deployed inside a convex bounded two-dimensional Chance-Constrained MPC for Voronoibased Multi-Agent System Deployment  Thomas Chevet ∗Cristina Stoica Maniu ∗Cristina Vlad ∗ Youmin Zhang ∗∗ Eduardo F. Camacho ∗∗∗ ∗Universit´e Paris-Saclay, CNRS, CentraleSup´elec, Laboratoire des signaux et syst`emes, 91190, Gif-sur-Yvette, France. (e-mail: {thomas.chevet, cristina.stoica, cristina.vlad}@l2s.centralesupelec.fr) ∗∗ Department of Mechanical, Industrial and Aerospace Engineering, Concordia University, 1455 Blvd. de Maisonneuve, Montr´eal, QC H3G 1M8, Canada. (e-mail: [email protected]) ∗∗∗ Departemento de Ingenier´ıa de Sistemas y Autom´atica, Universidad de Sevilla, Camino de los Descubrimientos, 41092 Sevilla, Spain. (e-mail: [email protected]) Abstract: This paper proposes a new chance-constrained model predictive control (CCMPC) algorithm with state estimation applied to the two-dimensional deployment of a multi-vehicle system where each agent is subject to process noise and measurement noise. The bounded convex area of deployment is partitioned into time-varying Voronoi cells defined by the position of each agent. Due to the presence of noise in the system model, stochastic constraints appear in the model predictive control problem. The proposed decentralized robust CCMPC algorithm drives the multi-agent system into a static Chebyshev configuration where each agent lies on the Chebyshev center of its Voronoi cell. Simulation results show the effectiveness of the proposed control strategy on a fleet of quadrotors subject to wind perturbations and measurement noise. Keywords: Multi-agent systems, Decentralized control, Model predictive control 1. INTRODUCTION To carry out monitoring or search missions, a multiagent system (MAS) composed of unmanned vehicles can be deployed over a bounded convex area (Cortes et al., 2004). Several solutions exist for the deployment problem (Schwager et al., 2011) but often rely on a dynamic Voronoi tessellation (Vorono¨ı, 1908) of the area of interest. The objective is usually to drive the MAS into a centroidal Voronoi configuration where the objective of each agent is to reach the center of mass of the Voronoi cell (Sharifi et al., 2015) or into a Chebyshev configuration where the objective is the Chebyshev center (Nguyen et al., 2017; Hatleskog et al., 2018; Chevet et al., 2020) of the cell, which is often less complex to compute than the center of mass. In this context, the Voronoi cells and objective points are time-varying due to the movement of the agents which are constrained to remain inside their cells. The control algorithm then has to drive each agent to its objective under this time-varying movement constraint. Generally, the literature deals with the nominal case, i.e. uncertainties/perturbations are not considered. However, real systems are subject to perturbations (e.g. wind gusts)  The authors acknowledge the LIA of the CNRS on Information, Learning and Control, MEECOD project (“Moderniser l’Enseignement par l’Exp´erimentation sur la COordination de Drones”) supported by UPSaclay, the Natural Sciences and Engineering Research Council of Canada, MEyC Spain (contract DPI2016- 76493-C3-1-R), the European Research Council and the UE ERDF (Advanced Grant OCONTSOLAR, Project ID: 789051). and noises (e.g. measurement noise from sensors). The perturbations acting on the system can be modeled using deterministic or stochastic approaches. The deterministic approach requires a model of the perturbation while the stochastic approach only requires a mean and a covariance. In order to deal with these stochastic perturbations, several control methods have been proposed for a single agent, such as H∞ (Ugrinovskii, 1998) or optimal control (Petersen et al., 2000), and for several agents, such as consensus (Ma et al., 2017) or predictive control (Dai et al., 2017). Model predictive control (MPC) is used for a wide variety of systems dealing with constraints, uncertainties, etc. MPC can also be used for the control of a multi-agent system either in a centralized, distributed or decentralized way. If the system is subject to bounded perturbations, robust MPC strategies have been developed (Limon et al., 2010) in order to further guarantee the feasibility and stability properties for a simple system. However, if these perturbations have a stochastic nature and an unbounded support such as normally distributed noises, the classical deterministic robust MPC strategies will be too conservative. To handle this situation, several stochastic MPC algorithms have been proposed to control a single system (Farina et al., 2016) or a multi-agent system (Dai et al., 2017) subject to perturbations and probabilistic constraints. However, these methods often rely on a known bound for the perturbation and fixed constraints over time. In this paper, a MAS composed of several unmanned vehicles is deployed inside a convex bounded two-dimensional Chance-Constrained MPC for Voronoibased Multi-Agent System Deployment  Thomas Chevet ∗Cristina Stoica Maniu ∗Cristina Vlad ∗ Youmin Zhang ∗∗ Eduardo F. Camacho ∗∗∗ ∗Universit´e Paris-Saclay, CNRS, CentraleSup´elec, Laboratoire des signaux et syst`emes, 91190, Gif-sur-Yvette, France. (e-mail: {thomas.chevet, cristina.stoica, cristina.vlad}@l2s.centralesupelec.fr) ∗∗ Department of Mechanical, Industrial and Aerospace Engineering, Concordia University, 1455 Blvd. de Maisonneuve, Montr´eal, QC H3G 1M8, Canada. (e-mail: [email protected]) ∗∗∗ Departemento de Ingenier´ıa de Sistemas y Autom´atica, Universidad de Sevilla, Camino de los Descubrimientos, 41092 Sevilla, Spain. (e-mail: [email protected]) Abstract: This paper proposes a new chance-constrained model predictive control (CCMPC) algorithm with state estimation applied to the two-dimensional deployment of a multi-vehicle system where each agent is subject to process noise and measurement noise. The bounded convex area of deployment is partitioned into time-varying Voronoi cells defined by the position of each agent. Due to the presence of noise in the system model, stochastic constraints appear in the model predictive control problem. The proposed decentralized robust CCMPC algorithm drives the multi-agent system into a static Chebyshev configuration where each agent lies on the Chebyshev center of its Voronoi cell. Simulation results show the effectiveness of the proposed control strategy on a fleet of quadrotors subject to wind perturbations and measurement noise. Keywords: Multi-agent systems, Decentralized control, Model predictive control 1. INTRODUCTION To carry out monitoring or search missions, a multiagent system (MAS) composed of unmanned vehicles can be deployed over a bounded convex area (Cortes et al., 2004). Several solutions exist for the deployment problem (Schwager et al., 2011) but often rely on a dynamic Voronoi tessellation (Vorono¨ı, 1908) of the area of interest. The objective is usually to drive the MAS into a centroidal Voronoi configuration where the objective of each agent is to reach the center of mass of the Voronoi cell (Sharifi et al., 2015) or into a Chebyshev configuration where the objective is the Chebyshev center (Nguyen et al., 2017; Hatleskog et al., 2018; Chevet et al., 2020) of the cell, which is often less complex to compute than the center of mass. In this context, the Voronoi cells and objective points are time-varying due to the movement of the agents which are constrained to remain inside their cells. The control algorithm then has to drive each agent to its objective under this time-varying movement constraint. Generally, the literature deals with the nominal case, i.e. uncertainties/perturbations are not considered. However, real systems are subject to perturbations (e.g. wind gusts)  The authors acknowledge the LIA of the CNRS on Information, Learning and Control, MEECOD project (“Moderniser l’Enseignement par l’Exp´erimentation sur la COordination de Drones”) supported by UPSaclay, the Natural Sciences and Engineering Research Council of Canada, MEyC Spain (contract DPI2016- 76493-C3-1-R), the European Research Council and the UE ERDF (Advanced Grant OCONTSOLAR, Project ID: 789051). and noises (e.g. measurement noise from sensors). The perturbations acting on the system can be modeled using deterministic or stochastic approaches. The deterministic approach requires a model of the perturbation while the stochastic approach only requires a mean and a covariance. In order to deal with these stochastic perturbations, several control methods have been proposed for a single agent, such as H∞ (Ugrinovskii, 1998) or optimal control (Petersen et al., 2000), and for several agents, such as consensus (Ma et al., 2017) or predictive control (Dai et al., 2017). Model predictive control (MPC) is used for a wide variety of systems dealing with constraints, uncertainties, etc. MPC can also be used for the control of a multi-agent system either in a centralized, distributed or decentralized way. If the system is subject to bounded perturbations, robust MPC strategies have been developed (Limon et al., 2010) in order to further guarantee the feasibility and stability properties for a simple system. However, if these perturbations have a stochastic nature and an unbounded support such as normally distributed noises, the classical deterministic robust MPC strategies will be too conservative. To handle this situation, several stochastic MPC algorithms have been proposed to control a single system (Farina et al., 2016) or a multi-agent system (Dai et al., 2017) subject to perturbations and probabilistic constraints. However, these methods often rely on a known bound for the perturbation and fixed constraints over time. In this paper, a MAS composed of several unmanned vehicles is deployed inside a convex bounded two-dimensional Chance-Constrained MPC for Voronoibased Multi-Agent System Deployment  Thomas Chevet ∗Cristina Stoica Maniu ∗Cristina Vlad ∗ Youmin Zhang ∗∗ Eduardo F. Camacho ∗∗∗ ∗ Universit´e Paris-Saclay, CNRS, CentraleSup´elec, Laboratoire des signaux et syst`emes, 91190, Gif-sur-Yvette, France. (e-mail: {thomas.chevet, cristina.stoica, cristina.vlad}@l2s.centralesupelec.fr) ∗∗ Department of Mechanical, Industrial and Aerospace Engineering, Concordia University, 1455 Blvd. de Maisonneuve, Montr´eal, QC H3G 1M8, Canada. (e-mail: [email protected]) ∗∗∗ Departemento de Ingenier´ıa de Sistemas y Autom´atica, Universidad de Sevilla, Camino de los Descubrimientos, 41092 Sevilla, Spain. (e-mail: [email protected]) Abstract: This paper proposes a new chance-constrained model predictive control (CCMPC) algorithm with state estimation applied to the two-dimensional deployment of a multi-vehicle system where each agent is subject to process noise and measurement noise. The bounded convex area of deployment is partitioned into time-varying Voronoi cells defined by the position of each agent. Due to the presence of noise in the system model, stochastic constraints appear in the model predictive control problem. The proposed decentralized robust CCMPC algorithm drives the multi-agent system into a static Chebyshev configuration where each agent lies on the Chebyshev center of its Voronoi cell. Simulation results show the effectiveness of the proposed control strategy on a fleet of quadrotors subject to wind perturbations and measurement noise. Keywords: Multi-agent systems, Decentralized control, Model predictive control 1. INTRODUCTION To carry out monitoring or search missions, a multiagent system (MAS) composed of unmanned vehicles can be deployed over a bounded convex area (Cortes et al., 2004). Several solutions exist for the deployment problem (Schwager et al., 2011) but often rely on a dynamic Voronoi tessellation (Vorono¨ı, 1908) of the area of interest. The objective is usually to drive the MAS into a centroidal Voronoi configuration where the objective of each agent is to reach the center of mass of the Voronoi cell (Sharifi et al., 2015) or into a Chebyshev configuration where the objective is the Chebyshev center (Nguyen et al., 2017; Hatleskog et al., 2018; Chevet et al., 2020) of the cell, which is often less complex to compute than the center of mass. In this context, the Voronoi cells and objective points are time-varying due to the movement of the agents which are constrained to remain inside their cells. The control algorithm then has to drive each agent to its objective under this time-varying movement constraint. Generally, the literature deals with the nominal case, i.e. uncertainties/perturbations are not considered. However, real systems are subject to perturbations (e.g. wind gusts)  The authors acknowledge the LIA of the CNRS on Information, Learning and Control, MEECOD project (“Moderniser l’Enseignement par l’Exp´erimentation sur la COordination de Drones”) supported by UPSaclay, the Natural Sciences and Engineering Research Council of Canada, MEyC Spain (contract DPI2016- 76493-C3-1-R), the European Research Council and the UE ERDF (Advanced Grant OCONTSOLAR, Project ID: 789051). and noises (e.g. measurement noise from sensors). The perturbations acting on the system can be modeled using deterministic or stochastic approaches. The deterministic approach requires a model of the perturbation while the stochastic approach only requires a mean and a covariance. In order to deal with these stochastic perturbations, several control methods have been proposed for a single agent, such as H∞ (Ugrinovskii, 1998) or optimal control (Petersen et al., 2000), and for several agents, such as consensus (Ma et al., 2017) or predictive control (Dai et al., 2017). Model predictive control (MPC) is used for a wide variety of systems dealing with constraints, uncertainties, etc. MPC can also be used for the control of a multi-agent system either in a centralized, distributed or decentralized way. If the system is subject to bounded perturbations, robust MPC strategies have been developed (Limon et al., 2010) in order to further guarantee the feasibility and stability properties for a simple system. However, if these perturbations have a stochastic nature and an unbounded support such as normally distributed noises, the classical deterministic robust MPC strategies will be too conservative. To handle this situation, several stochastic MPC algorithms have been proposed to control a single system (Farina et al., 2016) or a multi-agent system (Dai et al., 2017) subject to perturbations and probabilistic constraints. However, these methods often rely on a known bound for the perturbation and fixed constraints over time. In this paper, a MAS composed of several unmanned vehicles is deployed inside a convex bounded two-dimensional Chance-Constrained MPC for Voronoibased Multi-Agent System Deployment  Thomas Chevet ∗ Cristina Stoica Maniu ∗ Cristina Vlad ∗ Youmin Zhang ∗∗ Eduardo F. Camacho ∗∗∗ ∗Universit´e Paris-Saclay, CNRS, CentraleSup´elec, Laboratoire des signaux et syst`emes, 91190, Gif-sur-Yvette, France. (e-mail: {thomas.chevet, cristina.stoica, cristina.vlad}@l2s.centralesupelec.fr) ∗∗ Department of Mechanical, Industrial and Aerospace Engineering, Concordia University, 1455 Blvd. de Maisonneuve, Montr´eal, QC H3G 1M8, Canada. (e-mail: [email protected]) ∗∗∗ Departemento de Ingenier´ıa de Sistemas y Autom´atica, Universidad de Sevilla, Camino de los Descubrimientos, 41092 Sevilla, Spain. (e-mail: [email protected]) Abstract: This paper proposes a new chance-constrained model predictive control (CCMPC) algorithm with state estimation applied to the two-dimensional deployment of a multi-vehicle system where each agent is subject to process noise and measurement noise. The bounded convex area of deployment is partitioned into time-varying Voronoi cells defined by the position of each agent. Due to the presence of noise in the system model, stochastic constraints appear in the model predictive control problem. The proposed decentralized robust CCMPC algorithm drives the multi-agent system into a static Chebyshev configuration where each agent lies on the Chebyshev center of its Voronoi cell. Simulation results show the effectiveness of the proposed control strategy on a fleet of quadrotors subject to wind perturbations and measurement noise. Keywords: Multi-agent systems, Decentralized control, Model predictive control 1. INTRODUCTION To carry out monitoring or search missions, a multiagent system (MAS) composed of unmanned vehicles can be deployed over a bounded convex area (Cortes et al., 2004). Several solutions exist for the deployment problem (Schwager et al., 2011) but often rely on a dynamic Voronoi tessellation (Vorono¨ı, 1908) of the area of interest. The objective is usually to drive the MAS into a centroidal Voronoi configuration where the objective of each agent is to reach the center of mass of the Voronoi cell (Sharifi et al., 2015) or into a Chebyshev configuration where the objective is the Chebyshev center (Nguyen et al., 2017; Hatleskog et al., 2018; Chevet et al., 2020) of the cell, which is often less complex to compute than the center of mass. In this context, the Voronoi cells and objective points are time-varying due to the movement of the agents which are constrained to remain inside their cells. The control algorithm then has to drive each agent to its objective under this time-varying movement constraint. Generally, the literature deals with the nominal case, i.e. uncertainties/perturbations are not considered. However, real systems are subject to perturbations (e.g. wind gusts)  The authors acknowledge the LIA of the CNRS on Information, Learning and Control, MEECOD project (“Moderniser l’Enseignement par l’Exp´erimentation sur la COordination de Drones”) supported by UPSaclay, the Natural Sciences and Engineering Research Council of Canada, MEyC Spain (contract DPI2016- 76493-C3-1-R), the European Research Council and the UE ERDF (Advanced Grant OCONTSOLAR, Project ID: 789051). and noises (e.g. measurement noise from sensors). The perturbations acting on the system can be modeled using deterministic or stochastic approaches. The deterministic approach requires a model of the perturbation while the stochastic approach only requires a mean and a covariance. In order to deal with these stochastic perturbations, several control methods have been proposed for a single agent, such as H∞ (Ugrinovskii, 1998) or optimal control (Petersen et al., 2000), and for several agents, such as consensus (Ma et al., 2017) or predictive control (Dai et al., 2017). Model predictive control (MPC) is used for a wide variety of systems dealing with constraints, uncertainties, etc. MPC can also be used for the control of a multi-agent system either in a centralized, distributed or decentralized way. If the system is subject to bounded perturbations, robust MPC strategies have been developed (Limon et al., 2010) in order to further guarantee the feasibility and stability properties for a simple system. However, if these perturbations have a stochastic nature and an unbounded support such as normally distributed noises, the classical deterministic robust MPC strategies will be too conservative. To handle this situation, several stochastic MPC algorithms have been proposed to control a single system (Farina et al., 2016) or a multi-agent system (Dai et al., 2017) subject to perturbations and probabilistic constraints. However, these methods often rely on a known bound for the perturbation and fixed constraints over time. In this paper, a MAS composed of several unmanned vehicles is deployed inside a convex bounded two-dimensional Chance-Constrained MPC for Voronoibased Multi-Agent System Deployment  Thomas Chevet ∗Cristina Stoica Maniu ∗Cristina Vlad ∗ Youmin Zhang ∗∗ Eduardo F. Camacho ∗∗∗ ∗Universit´e Paris-Saclay, CNRS, CentraleSup´elec, Laboratoire des signaux et syst`emes, 91190, Gif-sur-Yvette, France. (e-mail: {thomas.chevet, cristina.stoica, cristina.vlad}@l2s.centralesupelec.fr) ∗∗ Department of Mechanical, Industrial and Aerospace Engineering, Concordia University, 1455 Blvd. de Maisonneuve, Montr´eal, QC H3G 1M8, Canada. (e-mail: [email protected]) ∗∗∗ Departemento de Ingenier´ıa de Sistemas y Autom´atica, Universidad de Sevilla, Camino de los Descubrimientos, 41092 Sevilla, Spain. (e-mail: [email protected]) Abstract: This paper proposes a new chance-constrained model predictive control (CCMPC) algorithm with state estimation applied to the two-dimensional deployment of a multi-vehicle system where each agent is subject to process noise and measurement noise. The bounded convex area of deployment is partitioned into time-varying Voronoi cells defined by the position of each agent. Due to the presence of noise in the system model, stochastic constraints appear in the model predictive control problem. The proposed decentralized robust CCMPC algorithm drives the multi-agent system into a static Chebyshev configuration where each agent lies on the Chebyshev center of its Voronoi cell. Simulation results show the effectiveness of the proposed control strategy on a fleet of quadrotors subject to wind perturbations and measurement noise. Keywords: Multi-agent systems, Decentralized control, Model predictive control 1. INTRODUCTION To carry out monitoring or search missions, a multiagent system (MAS) composed of unmanned vehicles can be deployed over a bounded convex area (Cortes et al., 2004). Several solutions exist for the deployment problem (Schwager et al., 2011) but often rely on a dynamic Voronoi tessellation (Vorono¨ı, 1908) of the area of interest. The objective is usually to drive the MAS into a centroidal Voronoi configuration where the objective of each agent is to reach the center of mass of the Voronoi cell (Sharifi et al., 2015) or into a Chebyshev configuration where the objective is the Chebyshev center (Nguyen et al., 2017; Hatleskog et al., 2018; Chevet et al., 2020) of the cell, which is often less complex to compute than the center of mass. In this context, the Voronoi cells and objective points are time-varying due to the movement of the agents which are constrained to remain inside their cells. The control algorithm then has to drive each agent to its objective under this time-varying movement constraint. Generally, the literature deals with the nominal case, i.e. uncertainties/perturbations are not considered. However, real systems are subject to perturbations (e.g. wind gusts)  The authors acknowledge the LIA of the CNRS on Information, Learning and Control, MEECOD project (“Moderniser l’Enseignement par l’Exp´erimentation sur la COordination de Drones”) supported by UPSaclay, the Natural Sciences and Engineering Research Council of Canada, MEyC Spain (contract DPI2016- 76493-C3-1-R), the European Research Council and the UE ERDF (Advanced Grant OCONTSOLAR, Project ID: 789051). and noises (e.g. measurement noise from sensors). The perturbations acting on the system can be modeled using deterministic or stochastic approaches. The deterministic approach requires a model of the perturbation while the stochastic approach only requires a mean and a covariance. In order to deal with these stochastic perturbations, several control methods have been proposed for a single agent, such as H∞ (Ugrinovskii, 1998) or optimal control (Petersen et al., 2000), and for several agents, such as consensus (Ma et al., 2017) or predictive control (Dai et al., 2017). Model predictive control (MPC) is used for a wide variety of systems dealing with constraints, uncertainties, etc. MPC can also be used for the control of a multi-agent system either in a centralized, distributed or decentralized way. If the system is subject to bounded perturbations, robust MPC strategies have been developed (Limon et al., 2010) in order to further guarantee the feasibility and stability properties for a simple system. However, if these perturbations have a stochastic nature and an unbounded support such as normally distributed noises, the classical deterministic robust MPC strategies will be too conservative. To handle this situation, several stochastic MPC algorithms have been proposed to control a single system (Farina et al., 2016) or a multi-agent system (Dai et al., 2017) subject to perturbations and probabilistic constraints. However, these methods often rely on a known bound for the perturbation and fixed constraints over time. In this paper, a MAS composed of several unmanned vehicles is deployed inside a convex bounded two-dimensional 6970 Thomas Chevet et al. / IFAC PapersOnLine 53-2 (2020) 6969–6974 polyhedral area. Each agent is subject to modeling errors and perturbations, which are represented respectively by the covariance and the mean of a process noise, as well as measurement noise, both with unknown bounds. At each time instant, each agent computes its Voronoi cell based on the knowledge of the other agents’ positions. Each agent is also constrained to remain inside its cell, which can be formulated as an optimization problem subject to timevarying constraints. In this way, the agents are subject to time-varying constraints. In (Gavilan et al., 2012), the authors propose a chance-constrained MPC (CCMPC) algorithm able to deal with time-varying constraints and process noise with unknown bounds for a single system. The current paper extends the result of (Gavilan et al., 2012) to the Voronoi-based deployment of a multi-agent system subject to process and measurement noise, where the full state information is not available. Due to the noises considered in the agents’ dynamical model, stochastic constraints appear in the optimization problem. These stochastic constraints are transformed into algebraic constraints by computing a bound ensuring that the constraints are satisfied for almost all possible Gaussian noise signals. Each agent uses the CCMPC algorithm to track the Chebyshev center of its Voronoi cell and the MAS converges to a static Chebyshev configuration. The contribution of this paper covers: 1) the extension of the method proposed in (Gavilan et al., 2012) when the estimation of the state has to be performed; 2) the application to the Voronoi-based deployment of a MAS subject to process and measurement noise; 3) the validation of the proposed chance-constrained MPC with a simulated fleet of quadrotor unmanned aerial vehicles (UAVs). Notation. In the following, R is the set of the real numbers. The matrices 0n×m and 1n×m are the matrices of size n×m filled with zeros and ones respectively. The matrix In is the identity matrix of size n×n . The transpose of the matrix A is denoted by A . A matrix diag (a1,...,a n) is the diagonal matrix with diagonal elements a1 ,..., an . The vector |x| contains the absolute value of each element of x . The Euclidean norm of the vector x is x2 2=xx . The notation A0 (resp. A0 ) means that A is a positive semidefinite (resp. positive definite) matrix. The matrix A⊗B is the Kronecker product of the matrices A and B . If r is a random variable, then E(r) is the expected value of r and P(r≤α) is the probability of the event r≤α , µr and Σr are respectively the mean and covariance of r . The set of all integers from nto mis denoted by n, m. 2. PROBLEM FORMULATION In the context of a homogeneous multi-agent system 1 composed of N agents, this section presents the general model of an agent i∈1,N subject to process noise and measurement noise. Then, it introduces the control objective of the considered multi-agent system. 2.1 System model An agent i∈1,N obeys the continuous-time linear time invariant dynamics: 1 A homogeneous MAS is considered to simplify the reading of the paper. However, the results can be extended to the case of heterogeneous MAS. ˙ xi(t)=ACxi(t)+BCui(t)+di(t) yi(t)=Cxi(t)+γi(t)(1) with xi∈Rn the state vector, ui∈Rm the input vector, yi∈Rp the output vector, di∈Rn the process noise, γi∈Rp the measurement noise and AC , BC and C matrices of appropriate dimensions. The pairs (AC,BC) and (AC,C) are respectively controllable and observable. The system (1) is discretized with the sampling period Ts : xi(k+ 1) = Axi(k)+Bui(k)+δi(k) yi(k)=Cxi(k)+γi(k)(2) with A= exp (AC·Ts) , B=Ts 0exp (AC·τ)Bdτ , δi(k)=Ts 0exp(AC·τ)di((k+ 1)Ts−τ)dτ. Assumption 1. The process noise di(t)=p(t)+wi(t), where p(t) is an external perturbation and wi(t) represents the modeling errors, and the measurement noise γi(k) are independent and normally distributed with means µd(t)=p(t) and µγ(k)=0p×1and covariance matrices Σd=Σw0 and Σγ0, respectively 2. The value of p(t) is known at each time instant. For all the agents, the pair (A,C) is assumed to be observable. Let L∈Rn×m be the gain of a Luenberger observer such that AL=A−LC is stable. The dynamics of the estimated state  xi(k) is:  xi(k+ 1) = A xi(k)+Bui(k)+L(yi(k)− yi(k))  yi(k)=C xi(k)(3) The estimation error εi(k)=xi(k)− xi(k) has for dynamics: εi(k+ 1) = ALεi(k)+δi(k)−Lγi(k) (4) with the covariance matrix of the initial estimation error chosen such that Σε(0) 0. By introducing εi(k)in (3):  xi(k+ 1) = A xi(k)+Bui(k)+LCεi(k)+Lγi(k).(5) Proposition 1. The covariance matrix Σδof δi(k) is positive definite and the covariance matrix Σε(k) of the estimation error εi(k) is positive definite ∀k>0. Proof. The covariance matrix Σδ is such that Σδ= Ts 0exp(AC·τ)Σdexp(A C·τ)dτ (Franklin et al., 1998). The matrix exp(AC·t) has full rank for all t (Horn and Johnson, 1990) and, by Assumption 1, Σd0 , thus Σδ0 (Horn and Johnson, 1990). At time k>0 , the random vectors εi(k−1) , δi(k−1) and γi(k−1) are independent. From (4) , the covariance matrix of εi(k) is Σε(k)=ALΣε(k−1)A L+Σδ+LΣγL0 (Horn and Johnson, 1990). Since Σδ0, Σε(k)0.  2.2 Control objective The state vector of an agent is xi=xix 1,i yix 2,i with [xiyi] the position of the agent in the two-dimensional plane R2 , x1,i ∈Rn1 and x2,i ∈Rn2 possible additional states (e.g. speed) such that n1+n2+2 = n . Denote by W⊂ R2 the convex bounded deployment region. The position of each agent belongs to W , i.e. the restriction xr i=[ xiyi] 2 These means and covariances are considered to be the same for all the agents. However, the result can be generalized to the heterogeneous case where the means and covariances are different for each agent. of xi is such that xr i∈W . This region is divided into N Voronoi cells, one for each agent, such that W=N i=1 Vi(k) and Vi(k)∩Vj(k)=∅ , ∀i, j ∈1,N , i=j . The Voronoi cell of an agent i is the convex bounded polygon defined as Vi(k)=x∈Wxr i(k)−x2≤ xr j(k)−x 2,∀i=j where xr i(k) and xr j(k) are the restrictions of the state vectors xi(k) , xj(k)∈Rn of agents i and j . As a convex bounded polygon, the Voronoi cell of the agent i is the set: Vi(k)={x∈W|Hi,W(k)x≤θi(k)}(6) where Hi,W(k)∈Rs×2 and θi(k)∈Rs , with s the number of sides of the cell. Assumption 2. Each agent is equipped with sensors allowing it to know the other agents positions and is then able to compute its own Voronoi cell. The Chebyshev center ci(k) of the cell Vi(k) is the center of the largest disc lying in Vi(k) . This center is obtained by a linear optimization problem maximizing the value of the disc’s radius such that the radius is positive and each point of the disc is in the cell (Chevet et al., 2020). The objective is then the deployment of the multi-agent system inside a bounded convex polygon W into a static configuration such that the agents’ positions are at the Chebyshev centers of their Voronoi cells despite the considered process noise and measurement noise acting on the MAS. Each agent computes its own control signal and is driven towards an objective point x0 i(k),u0 i(k) solution of x0 i(k)=Ax0 i(k)+Bu0 i(k) such that the restriction of x0 i to the position in the plane R2 is equal to the Chebyshev center of its Voronoi cell. Moreover, an extended Voronoi cell Vi,x(k)={x∈Rn|Hi(k)x≤θi(k)} can be defined with Hi(k)∈Rs×n . Given the shape of the state vector, the matrix Hi is obtained by adding n1 columns of zeros after the first column of Hi,W and n2 columns of zeros after the second column of Hi,W . The matrix Hi and the vector θi will then be used as a polyhedral constraint on the state vector for the MPC problem 3. Since the positions of the agents evolve over time, the Voronoi cells and their associated Chebyshev centers are time-varying. With a state-feedback control law, the nominal multi-agent system has been shown to converge towards a static Chebyshev configuration (Hatleskog et al., 2018). Nevertheless, in the presence of process noise modeled as additive Gaussian noise, a robust control algorithm is required in order to ensure the noise rejection and the multiagent system convergence towards a static configuration. The next section then presents a decentralized robust MPC algorithm based on a chance-constrained approach. 3. MAIN RESULT In this section, a decentralized chance-constrained MPC algorithm is formulated based on the estimation of the agent’s state. The useful matrices for the definition of the optimization problem are defined. Then, the cost function and constraints of the optimization problem are expressed with the previously defined matrices. However, due to the presence of stochastic perturbations in the agent’s model, 3 Such constraints cause a coupling between the agents, thus the need for a decentralized control algorithm. the agent is subject to probabilistic constraints. A way to transform these probabilistic constraints into algebraic constraints is finally introduced. 3.1 State prediction Over a prediction horizon Np , the estimated state (5) and the estimation error (4) become respectively:  Xi(k)=F xi(k)+GuUi(k)+GεEi(k)+GγΓi(k) (7) Ei(k+ 1) = Fεεi(k)+Gε δ∆i(k)−Gε γΓi(k) (8) with  Xi(k)= xi(k+ 1)···  xi(k+Np) , Ui(k)= ui(k)··· ui(k+Np−1) and Ei(k) (resp. Γi(k) and ∆i(k) ) defined the same way as Ui(k) by replacing ui by εi (resp. γi and δi ). The matrix F is such that F=A··· ANp  and the matrix Fε is obtained by replacing Aby ALin F. The matrix Guis such that: Gu=       B0n×m··· 0n×m . . ........ . . . . ....0n×m ANp−1B··· ··· B      , (9) the matrices Gε and Gγ are obtained by replacing B in (9) respectively by LC and L , and the matrices Gε δ and Gε γ are obtained by replacing A by AL and B respectively by Inand L. 3.2 Chance-constrained MPC problem Based on (Gavilan et al., 2012), a decentralized robust chance-constrained model predictive controller for an agent i∈1,N following the dynamics (2) is expressed as follows: min Ui(k)J(k) (10a) s.t. xi(k+l)∈Vi,x(k),l∈1,N p,(10b) Ui(k)∈Ui,(10c) with J(k)=E Xobj i(k)Q Xobj i(k)+Ui(k)RUi(k) . The weights Q , R0 are diagonal matrices and  Xobj i(k)=  Xi(k)−X0 i , where X0 i=1Np⊗x0 i(k) with x0 i(k) the objective state vector defined in Section 2.2. For a vehicle, u0 i is often the null vector, thus it is not considered here. If u0 i=0m×1 , then Ui(k) is replaced in (10a) by Ui(k)− U0 i(k), where U0 i(k)=1Np⊗u0 i(k). Due to stochastic process and measurement noise, solving the optimization problem (10) requires to find a bound for the unknown terms appearing in the constraint (10b) as detailed hereafter. In Section 3.3, this bound is the solution of an optimization problem under probabilistic constraints. Given the expression of  Xi(k) from (7) , the cost function (10a) is rewritten by removing the terms that do not depend on Ui(k)and have no influence on the solution of (10): J(k)=Ui(k)G uQGu+RUi(k)+2(F xi(k) +GεµE(k)−X0 i)QGuUi(k)(11) with µE(k)=E(Ei(k)) . Since µγ(k)=0p×1 , the mean of Γi(k) is the null vector and it does not appear in the expression of the cost function J(k). Thomas Chevet et al. / IFAC PapersOnLine 53-2 (2020) 6969–6974 6971 of xi is such that xr i∈W . This region is divided into N Voronoi cells, one for each agent, such that W=N i=1 Vi(k) and Vi(k)∩Vj(k)=∅ , ∀i, j ∈1,N , i=j . The Voronoi cell of an agent i is the convex bounded polygon defined as Vi(k)=x∈Wxr i(k)−x2≤ xr j(k)−x 2,∀i=j where xr i(k) and xr j(k) are the restrictions of the state vectors xi(k) , xj(k)∈Rn of agents i and j . As a convex bounded polygon, the Voronoi cell of the agent i is the set: Vi(k)={x∈W|Hi,W(k)x≤θi(k)}(6) where Hi,W(k)∈Rs×2 and θi(k)∈Rs , with s the number of sides of the cell. Assumption 2. Each agent is equipped with sensors allowing it to know the other agents positions and is then able to compute its own Voronoi cell. The Chebyshev center ci(k) of the cell Vi(k) is the center of the largest disc lying in Vi(k) . This center is obtained by a linear optimization problem maximizing the value of the disc’s radius such that the radius is positive and each point of the disc is in the cell (Chevet et al., 2020). The objective is then the deployment of the multi-agent system inside a bounded convex polygon W into a static configuration such that the agents’ positions are at the Chebyshev centers of their Voronoi cells despite the considered process noise and measurement noise acting on the MAS. Each agent computes its own control signal and is driven towards an objective point x0 i(k),u0 i(k) solution of x0 i(k)=Ax0 i(k)+Bu0 i(k) such that the restriction of x0 i to the position in the plane R2 is equal to the Chebyshev center of its Voronoi cell. Moreover, an extended Voronoi cell Vi,x(k)={x∈Rn|Hi(k)x≤θi(k)} can be defined with Hi(k)∈Rs×n . Given the shape of the state vector, the matrix Hi is obtained by adding n1 columns of zeros after the first column of Hi,W and n2 columns of zeros after the second column of Hi,W . The matrix Hi and the vector θi will then be used as a polyhedral constraint on the state vector for the MPC problem 3. Since the positions of the agents evolve over time, the Voronoi cells and their associated Chebyshev centers are time-varying. With a state-feedback control law, the nominal multi-agent system has been shown to converge towards a static Chebyshev configuration (Hatleskog et al., 2018). Nevertheless, in the presence of process noise modeled as additive Gaussian noise, a robust control algorithm is required in order to ensure the noise rejection and the multiagent system convergence towards a static configuration. The next section then presents a decentralized robust MPC algorithm based on a chance-constrained approach. 3. MAIN RESULT In this section, a decentralized chance-constrained MPC algorithm is formulated based on the estimation of the agent’s state. The useful matrices for the definition of the optimization problem are defined. Then, the cost function and constraints of the optimization problem are expressed with the previously defined matrices. However, due to the presence of stochastic perturbations in the agent’s model, 3 Such constraints cause a coupling between the agents, thus the need for a decentralized control algorithm. the agent is subject to probabilistic constraints. A way to transform these probabilistic constraints into algebraic constraints is finally introduced. 3.1 State prediction Over a prediction horizon Np , the estimated state (5) and the estimation error (4) become respectively:  Xi(k)=F xi(k)+GuUi(k)+GεEi(k)+GγΓi(k) (7) Ei(k+ 1) = Fεεi(k)+Gε δ∆i(k)−Gε γΓi(k) (8) with  Xi(k)= xi(k+ 1)···  xi(k+Np) , Ui(k)= ui(k)··· ui(k+Np−1) and Ei(k) (resp. Γi(k) and ∆i(k) ) defined the same way as Ui(k) by replacing ui by εi (resp. γi and δi ). The matrix F is such that F=A··· ANp  and the matrix Fε is obtained by replacing Aby ALin F. The matrix Guis such that: Gu=       B0n×m··· 0n×m . . ........ . . . . ....0n×m ANp−1B··· ··· B      , (9) the matrices Gε and Gγ are obtained by replacing B in (9) respectively by LC and L , and the matrices Gε δ and Gε γ are obtained by replacing A by AL and B respectively by Inand L. 3.2 Chance-constrained MPC problem Based on (Gavilan et al., 2012), a decentralized robust chance-constrained model predictive controller for an agent i∈1,N following the dynamics (2) is expressed as follows: min Ui(k)J(k) (10a) s.t. xi(k+l)∈Vi,x(k),l∈1,N p,(10b) Ui(k)∈Ui,(10c) with J(k)=E Xobj i(k)Q Xobj i(k)+Ui(k)RUi(k) . The weights Q , R0 are diagonal matrices and  Xobj i(k)=  Xi(k)−X0 i , where X0 i=1Np⊗x0 i(k) with x0 i(k) the objective state vector defined in Section 2.2. For a vehicle, u0 i is often the null vector, thus it is not considered here. If u0 i=0m×1 , then Ui(k) is replaced in (10a) by Ui(k)− U0 i(k), where U0 i(k)=1Np⊗u0 i(k). Due to stochastic process and measurement noise, solving the optimization problem (10) requires to find a bound for the unknown terms appearing in the constraint (10b) as detailed hereafter. In Section 3.3, this bound is the solution of an optimization problem under probabilistic constraints. Given the expression of  Xi(k) from (7) , the cost function (10a) is rewritten by removing the terms that do not depend on Ui(k)and have no influence on the solution of (10): J(k)=Ui(k)G uQGu+RUi(k)+2(F xi(k) +GεµE(k)−X0 i)QGuUi(k)(11) with µE(k)=E(Ei(k)) . Since µγ(k)=0p×1 , the mean of Γi(k) is the null vector and it does not appear in the expression of the cost function J(k). 6972 Thomas Chevet et al. / IFAC PapersOnLine 53-2 (2020) 6969–6974 The extended Voronoi cell is such that Vi,x(k)= {x∈Rn|Hi(k)x≤θi(k)} as detailed in Section 2.2. To predict the evolution of the Voronoi cells over the prediction horizon, each agent would have to know at each time instant the input sequence of all the other agents. With Assumption 2, there is no need of communication between the agents. The extended Voronoi cell of each agent is then considered constant over the prediction horizon. Thus, the constraint (10b) can be rewritten over the prediction horizon by using (7) and replacing  X(k) by its expression: Hi,u(k)GuUi(k)≤Θi,u(k)−Hi,u(k)F xi(k) −Hi,u(k)(GεEi(k)+GγΓi(k)) (12) where Hi,u =INp⊗Hiand Θi,u =1Np⊗θi. In the constraint (10c) , Ui is a set of polyhedral constraints such that Ui=u∈RmNp|u|≤Umax , where Umax ∈ RmNpwith only positive components. With this formulation, the constraint (12) depends on the knowledge of the process noise and the measurement noise over the prediction horizon. However, the value of these signals is not known and the only available information are the mean and covariance of these noises. The constraint (12) then needs to be modified to depend only on the available information in order to solve the problem (10). 3.3 Noise bound for robust satisfaction of constraints In (12) , a bound for the uncertain term Hi,u(k)GεEi(k)+ GγΓi(k) , which is also written Hi,u(k)[ GεGγ]Ξi(k) , with Ξi(k)=Ei(k)Γi(k) the disturbance vector, has to be found in order to express the constraint (12) only based on known information. If the disturbance vector Ξi(k) is normally distributed with mean µΞ(k) and covariance matrix ΣΞ(k), then: Yi(k)=(Ξi(k)−µΞ(k))Σ−1 Ξ(k)(Ξi(k)−µΞ(k)) (13) follows a chi-squared law with (n+p)Np degrees of freedom (Flury, 1997), where (n+p)Np is the size of Ξi(k) . Then, finding the solution α of the chance constraint Pχ2((n+p)Np)≤α=P ensures that Yi(k) is bounded by αwith a probability P(Gavilan et al., 2012). The objective is then to find a bound bi(k) such that bi(k)≤−MiΞi(k) , where Mi=Hi,u(k)[ GεGγ] , with a probability P close to one. With this bound, the constraint (12) is satisfied for almost all disturbances. This bound is: (bi(k))l= min Ξi(k)−(Mi)lΞi(k) s.t.Yi(k)≤α (14) where (Mi)l and (bi(k))l are respectively the l -th row of Mi and the l -th element of bi(k) and Yi(k) defined in (13) . To guarantee the existence of the bound, Ξi(k) has to be normally distributed, thus ΣΞ has to be invertible. Since εi(k−1) , ∆i(k−1) and Γi(k−1) are independent, from the expression of Ei(k)in (8), this covariance is: ΣΞ(k)=ΣE(k)−Gε γΣΓ,L −ΣΓ,L Gε γ ΣΓ(15) where: ΣE(k)=FεΣε(k−1)F ε+Gε δΣ∆Gε δ +Gε γΣΓGε γ ,(16) with ΣΓ=INp⊗Σγ , Σ∆=INp⊗Σδ and ΣΓ,L a block lower diagonal matrix with Σγ the element at line l and column l−1, where l>1. Proposition 2. The covariance matrix ΣΞ(k) is positive definite ∀k>0. Proof. By taking the Schur complement (Boyd et al., 1994) in (15) , ΣΞ(k)0 if and only if ΣΓ0 (which is always true) and S(k)0 with S(k)=ΣE(k)− Gε γΣΓ,LΣΓ −1ΣΓ,L Gε γ  . Since Σγ0 , Σγ is invertible and ΣΓ −1=INp⊗Σγ −1 . Using (16) , S(k) becomes S(k)=FεΣε(k−1)F ε+Gε δΣ∆Gε δ +Gε γΣΓ,1Gε γ  , with ΣΓ,1= diag Σγ,0(p−1)Np×(p−1)Np . To have S(k)0 , at least one of the matrices defining S(k) has to be positive definite while the others only need to be positive semidefinite. Proposition 1 gives Σε(k−1) 0 thus FεΣε(k−1)F ε0 (Horn and Johnson, 1990). Since ΣΓ,10 , it is verified that Gε γΣΓ,1Gε γ 0 . It remains to prove that Gε δΣ∆Gε δ 0 . The matrix Gε δ defined in Section 3.1 is Gε δ=InNp+T where T is a strictly lower triangular matrix. Thus, Gε δΣ∆Gε δ =Σ∆+TΣ∆T+ TΣ∆+Σ∆T , with the last two terms positive semidefinite because Σ∆ is a block diagonal matrix and T is strictly lower triangular, thus their eigenvalues are all 0 . In addition, TΣ∆T0 and Σ∆0thus ΣΞ(k)0.  With Proposition 2, ΣΞ(k) is invertible. By applying a similar procedure to the one presented in (Gavilan et al., 2012), the optimization problem (14) is explicitly solved and the l-th element of bi(k) is: (bi(k))l=−(Mi)lαΣΞ(k)(Mi) l−(Mi)lµΞ(k).(17) Then, by replacing the constraint (10b) by (12) with the bound defined in (17) , it is now possible to find a solution to the proposed decentralized CCMPC (10). 4. SIMULATIONS In this paper, the considered multi-agent system is a fleet of four quadrotor UAVs. The nonlinear continuous-time state-space model of a UAV agent is presented in (Chevet et al., 2020). This model is the one used to simulate the behavior of an agent. The control architecture for this system is as follows: a position reference is provided to the position controller which computes pitch and roll references for the orientation controller. The yaw reference is constant during the flight. Then, the orientation and the altitude controllers provide torque and upward thrust inputs to the nonlinear UAV model. The chance-constrained MPC algorithm described in Section 3 is used for the position controller, while the orientation and altitude controllers are obtained by feedback linearization as in (Voos, 2009). 4.1 Position subsystem model To design the position controller, the position subsystem is obtained from the linearized and discretized state-space model (Chevet et al., 2020) to fit the system (2) . For one UAV agent, the state vector is xi=[ xivx,i yivy,i] , with i∈1,4 , xi , yi the agent’s position and vx,i , vy,i the components of its horizontal speed. The input vector is ui=[ φiθi] , with φi and θi the agent’s roll and pitch angles. The yaw reference remains equal to 0◦ during the flight, thus the state matrices defined in (2) are: A=I2⊗1Ts 01 B=1 2gTs01 −10 ⊗Ts 2, C=I2⊗[10 ] (18) with g=9.81 m ·s−2 the gravitational acceleration and Ts the sampling period. The noise covariances are Σd= diag(0.001,0.025,0.001,0.025) and Σγ=0.0011 ·I2 and µdwill be described in Section 4.4. 4.2 Position controller The chance-constrained model predictive controller runs at Tout s=0.2 s with a prediction horizon Np= 10 , while the inner loop (the orientation controller) runs at Tin s=0.001 s. Thus, to accurately estimate the system’s state, the structure from Fig. 1 is used. On a real UAV, the variation rate of the angle reference is limited to avoid important variations on the actuators’ inputs. Thus, here, the variation rate of the angle reference is limited to ±100◦/s . Then, this reference φref i(k)θref i(k) is sent to the inner loop controller and an observer, both running at Tin s as shown in Fig. 1. This observer is meant to provide an accurate value of the state to the outer loop controller and thus runs at the same rate as the inner loop controller. The state estimate is then sent to the position controller every Tout sseconds. With this structure, the prediction model (3) considered for the chance-constrained MPC design uses the matrices in (18) with Ts=Tout s , while the second observer’s model is obtained from the matrices in (18) with Ts=Tin s . The observer gain L in (3) is a linear quadratic estimator obtained with the weights Q= 100I4 and R=I2 . The observer in Fig. 1 is also a linear quadratic estimator obtained with the weights Q= 10I4and R=I2. The objective point x0 i(k) is a vector with four elements: the coordinates of the Chebyshev center of the cell as first and third elements and zeros as second and fourth elements. Moreover, the weights Q and R for the cost function (10a) are chosen to be Q=INp⊗diag(10,1,10,1) and R= 100I2Np . The angle reference is limited to ±30◦ such that Ui=u∈R2Np|u|≤π/6·12Np. Finally, with the considered dimensions for the problem, the chi-squared variable presented in Section 3.3 has 60 degrees of freedom. Thus, if P is chosen to be 0.999 , nearly all the disturbances are bounded by α= 99.607 in (14). 4.3 Orientation and altitude controllers The following orientation and altitude controllers are obtained as presented in (Voos, 2009). Further description CCMPC ZOH Rate limiter Observer ZOH Tout sTin s Tin s Angle reference Measurement Tout s Position reference Fig. 1. Structure of the position controller. −10 −5 0 5 10 −10 −5 0 5 10 1 2 3 4 x(m) y(m) Agent’s estimated position [xiyi] Agent’s initial position Agent’s real position [xiyi] Chebyshev center ci Fig. 2. Evolution of the agents’ real and estimated position and Chebyshev center from t=0stot=9.8 s. is out of the scope of this paper and these are given for reproducibility of the results. The torque on the x axis is computed as τx,i(k)=(Iz−Iy)ωy,i(k)ωz,i(k)+ IxK1ωx,i(k)+K2φref i(k)−φi(k) where ωx,i , ωy,i and ωz,i are the angular speeds Ix=Iy=0.03 kg ·m2 and Iz=0.04 kg ·m2 are the moments of inertia along the three axes and K1 and K2 are parameters chosen to obtain the desired dynamics for the inner loop. Here, the values K1=−200 and K2= 100 are considered for the parameters. The torques τy,i(k) and τz,i(k) are obtained with a cyclic permutation of x , y and z in the expression of τx,i(k) and by replacing φ by θ and ψ (the yaw angle) respectively, with ψref i(k)=0 . With the same approach, the total upward thrust is Ft,i(k)=m·(g+K3vz,i(k)+ K4zref i(k)−zi(k))/(cos φi(k) cos θi(k))−1 where zi and vz,i are the altitude and vertical speed, zref i is the altitude reference, m=1.4 kg is the mass of the UAV and K3 and K4 are parameters chosen to obtain the desired dynamics for the altitude loop. Here, the values K3=−3.6 and K4=4are considered for the parameters. 4.4 Simulation results A fleet of four quadrotor UAVs is deployed inside a square of 20 m of side length: W=x∈R2|x|≤10 ·12 . They all start from a hovering position with zi(0) = 5 m, with i∈1,4 , at x1(0) = [1010 ] , x2(0) = [10−10 ] , x3(0)=[ −1010 ],x4(0)=[ −10−10 ]. At t=0 s, they start tracking the Chebyshev center of their associated Voronoi cell and are subject to a process noise and a measurement noise having a mean µd(t)=µγ(k)=04×1 and the covariances Σδ and Σγ described in Section 4.1. From t= 12 s to t= 20 s, each UAV is subject to a wind gust of 2 m/s on each axis such that µd(t)=[ 0202 ] which is assumed to be known by the agents as stated in Assumption 1. The first part of the movement, from t=0 s to t=9.8 s, is shown in Fig. 2. The initial positions [xi(0) yi(0)] are represented by discs (red discs). The evolution of the real positions [xiyi] (blue circles) as well as the evolution of the estimated positions [xiyi] (red circles) and the Chebyshev centers ci (black asterisks) of the four agents every 0.2 s are presented inside the Voronoi partition at Thomas Chevet et al. / IFAC PapersOnLine 53-2 (2020) 6969–6974 6973 components of its horizontal speed. The input vector is ui=[ φiθi] , with φi and θi the agent’s roll and pitch angles. The yaw reference remains equal to 0◦ during the flight, thus the state matrices defined in (2) are: A=I2⊗1Ts 01 B=1 2gTs01 −10 ⊗Ts 2, C=I2⊗[10 ] (18) with g=9.81 m ·s−2 the gravitational acceleration and Ts the sampling period. The noise covariances are Σd= diag(0.001,0.025,0.001,0.025) and Σγ=0.0011 ·I2 and µdwill be described in Section 4.4. 4.2 Position controller The chance-constrained model predictive controller runs at Tout s=0.2 s with a prediction horizon Np= 10 , while the inner loop (the orientation controller) runs at Tin s=0.001 s. Thus, to accurately estimate the system’s state, the structure from Fig. 1 is used. On a real UAV, the variation rate of the angle reference is limited to avoid important variations on the actuators’ inputs. Thus, here, the variation rate of the angle reference is limited to ±100◦/s . Then, this reference φref i(k)θref i(k) is sent to the inner loop controller and an observer, both running at Tin s as shown in Fig. 1. This observer is meant to provide an accurate value of the state to the outer loop controller and thus runs at the same rate as the inner loop controller. The state estimate is then sent to the position controller every Tout sseconds. With this structure, the prediction model (3) considered for the chance-constrained MPC design uses the matrices in (18) with Ts=Tout s , while the second observer’s model is obtained from the matrices in (18) with Ts=Tin s . The observer gain L in (3) is a linear quadratic estimator obtained with the weights Q= 100I4 and R=I2 . The observer in Fig. 1 is also a linear quadratic estimator obtained with the weights Q= 10I4and R=I2. The objective point x0 i(k) is a vector with four elements: the coordinates of the Chebyshev center of the cell as first and third elements and zeros as second and fourth elements. Moreover, the weights Q and R for the cost function (10a) are chosen to be Q=INp⊗diag(10,1,10,1) and R= 100I2Np . The angle reference is limited to ±30◦ such that Ui=u∈R2Np|u|≤π/6·12Np. Finally, with the considered dimensions for the problem, the chi-squared variable presented in Section 3.3 has 60 degrees of freedom. Thus, if P is chosen to be 0.999 , nearly all the disturbances are bounded by α= 99.607 in (14). 4.3 Orientation and altitude controllers The following orientation and altitude controllers are obtained as presented in (Voos, 2009). Further description CCMPC ZOH Rate limiter Observer ZOH Tout sTin s Tin s Angle reference Measurement Tout s Position reference Fig. 1. Structure of the position controller. −10 −5 0 5 10 −10 −5 0 5 10 1 2 3 4 x(m) y(m) Agent’s estimated position [xiyi] Agent’s initial position Agent’s real position [xiyi] Chebyshev center ci Fig. 2. Evolution of the agents’ real and estimated position and Chebyshev center from t=0stot=9.8 s. is out of the scope of this paper and these are given for reproducibility of the results. The torque on the x axis is computed as τx,i(k)=(Iz−Iy)ωy,i(k)ωz,i(k)+ IxK1ωx,i(k)+K2φref i(k)−φi(k) where ωx,i , ωy,i and ωz,i are the angular speeds Ix=Iy=0.03 kg ·m2 and Iz=0.04 kg ·m2 are the moments of inertia along the three axes and K1 and K2 are parameters chosen to obtain the desired dynamics for the inner loop. Here, the values K1=−200 and K2= 100 are considered for the parameters. The torques τy,i(k) and τz,i(k) are obtained with a cyclic permutation of x , y and z in the expression of τx,i(k) and by replacing φ by θ and ψ (the yaw angle) respectively, with ψref i(k)=0 . With the same approach, the total upward thrust is Ft,i(k)=m·(g+K3vz,i(k)+ K4zref i(k)−zi(k))/(cos φi(k) cos θi(k))−1 where zi and vz,i are the altitude and vertical speed, zref i is the altitude reference, m=1.4 kg is the mass of the UAV and K3 and K4 are parameters chosen to obtain the desired dynamics for the altitude loop. Here, the values K3=−3.6 and K4=4are considered for the parameters. 4.4 Simulation results A fleet of four quadrotor UAVs is deployed inside a square of 20 m of side length: W=x∈R2|x|≤10 ·12 . They all start from a hovering position with zi(0) = 5 m, with i∈1,4 , at x1(0) = [1010 ] , x2(0) = [10−10 ] , x3(0)=[ −1010 ],x4(0)=[ −10−10 ]. At t=0 s, they start tracking the Chebyshev center of their associated Voronoi cell and are subject to a process noise and a measurement noise having a mean µd(t)=µγ(k)=04×1 and the covariances Σδ and Σγ described in Section 4.1. From t= 12 s to t= 20 s, each UAV is subject to a wind gust of 2 m/s on each axis such that µd(t)=[ 0202 ] which is assumed to be known by the agents as stated in Assumption 1. The first part of the movement, from t=0 s to t=9.8 s, is shown in Fig. 2. The initial positions [xi(0) yi(0)] are represented by discs (red discs). The evolution of the real positions [xiyi] (blue circles) as well as the evolution of the estimated positions [xiyi] (red circles) and the Chebyshev centers ci (black asterisks) of the four agents every 0.2 s are presented inside the Voronoi partition at 6974 Thomas Chevet et al. / IFAC PapersOnLine 53-2 (2020) 6969–6974 0 5 10 15 20 25 30 0 2 4 6 t(s) d(m) [x2y2]−c22 15 20 25 0 0.5 1 0 5 10 15 20 25 30 0 2 4 6 ·10−3 t(s) d(m)   [x2y2]−[x2y2]  2 Fig. 3. Distance between the agent 2 real position and its Chebyshev center (top) and between the agent 2 real position and its estimated position (bottom). t=9.8 s. The position of each agent converges to its Chebyshev center as expected from (Hatleskog et al., 2018), while the estimated position converges quickly to the real position. In the following, since the formation is symmetric, only the results for the agent 2 are provided, the results for the other agents being similar. Figure 3 presents the distance between the real position [x2y2] of agent 2 and its Chebyshev center c2 and the distance between the real position and the estimated position [x2y2] of agent 2. The estimated position is initialized to the agent’s real position. The bottom plot of Fig. 3 shows that the estimation error is relatively small (ε2(k)2<6·10−3) during the entire movement. The top plot of Fig. 3 shows that the agent converges to its Chebyshev center since the distance between the real position of agent 2 and c2 is close to 0 m after 2 s. However, from t= 12 s to t= 20 s, the system is subject to wind perturbations. Because there is no integral action in the proposed control algorithm, a static error appears while the system is perturbed. Without perturbation, the agent converges back to its Chebyshev center. 5. CONCLUSION This paper presents a decentralized chance-constrained model predictive control algorithm with state estimation meant to drive a multi-agent system subject to process noise and measurement noise into a static configuration when deployed inside a bounded convex two-dimensional area. At each time instant, each agent computes a Voronoi cell in which it will evolve and the Chebyshev center of this Voronoi cell. Then, with the proposed approach, the system converges towards a static configuration in which each agent lies on its Chebyshev center despite model mismatch and perturbations (represented respectively by the covariance and the mean of the process noise) and measurement noise. Simulation results show the efficiency of the proposed approach. Future work will extend this result to the case of biased measurements corresponding, for example, to sensor faults. REFERENCES Boyd, S., El Ghaoui, L., Feron, E., and Balakrishnan, V. (1994). Linear matrix inequalities in system and control theory. SIAM. Chevet, T., Vlad, C., Stoica Maniu, C., and Zhang, Y. (2020). Decentralized MPC for UAVs formation deployment and reconfiguration with multiple outgoing agents. J. Intell. Robot. Syst., 97(1), 155–170. Cortes, J., Martinez, S., Karatas, T., and Bullo, F. (2004). Coverage control for mobile sensing networks. IEEE Trans. Robot. Autom., 20(2), 243–255. Dai, L., Xia, Y., Gao, Y., and Cannon, M. (2017). Distributed stochastic MPC of linear systems with additive uncertainty and coupled probabilistic constraints. IEEE Trans. Autom. Control, 62(7), 3474–3481. Farina, M., Giulioni, L., and Scattolini, R. (2016). Stochastic linear model predictive control with chance constraints – A review. J. Process Control, 44, 53–67. Flury, B. (1997). A first course in multivariate statistics. Springer. Franklin, G.F., Powell, J.D., Workman, M.L., et al. (1998). Digital Control of Dynamic Systems. Addison-Wesley. Gavilan, F., Vazquez, R., and Camacho, E.F. (2012). Chance-constrained model predictive control for spacecraft rendezvous with disturbance estimation. Control Eng. Pract., 20(2), 111–122. Hatleskog, J., Olaru, S., and Hovd, M. (2018). Voronoibased deployment of multi-agent system. In 57th CDC, 5403–5408. Horn, R.A. and Johnson, C.R. (1990). Matrix analysis. Cambridge University Press. Limon, D., Alvarado, I., Alamo, T., and Camacho, E.F. (2010). Robust tube-based MPC for tracking of constrained linear systems with additive disturbances. J. Process Control, 20(3), 248–260. Ma, L., Wang, Z., Han, Q.L., and Liu, Y. (2017). Consensus control of stochastic multi-agent systems: a survey. Sci. China Inf. Sci., 60(12), 120–201. Nguyen, M.T., Stoica Maniu, C., and Olaru, S. (2017). Optimization-based control for multi-agent deployment via dynamic Voronoi partition. IFAC-PapersOnLine, 50(1), 1828–1833. Petersen, I.R., James, M.R., and Dupuis, P. (2000). Minimax optimal control of stochastic uncertain systems with relative entropy constraints. IEEE Trans. Autom. Control, 45(3), 398–412. Schwager, M., Rus, D., and Slotine, J.J. (2011). Unifying geometric, probabilistic, and potential field approaches to multi-robot deployment. Int. J. Robot. Res., 30(3), 371–383. Sharifi, F., Mirzaei, M., Zhang, Y., and Gordon, B.W. (2015). Cooperative multi-vehicle search and coverage problem in an uncertain environment. Unmanned Syst., 3(1), 35–47. Ugrinovskii, V.A. (1998). Robust H infinity control in the presence of stochastic uncertainty. Int. J. Control, 71(2), 219–237. Voos, H. (2009). Nonlinear control of a quadrotor microuav using feedback-linearization. In IEEE Int. Conf. Mechatronics, 1–6. Vorono¨ı, G. (1908). Nouvelles applications des param`etres continus `a la th´eorie des formes quadratiques. Journal f¨ur die reine und angewandte Mathematik, 134, 198–287.