No Access

Model predictive control with random batch methods for a guiding problem

Department of Mathematics, The Catholic University of Korea, Jibongro 43, Bucheon, Gyeonggido 14662, Republic of Korea

and

Chair of Dynamics, Control and Numerics, Alexander von Humboldt-Professorship, Department of Data Science, Friedrich-Alexander-Universität Erlangen-Nürnberg, 91058 Erlangen, Germany

Chair of Computational Mathematics, Fundación Deusto, University of Deusto, 48007 Bilbao, Basque Country, Spain

Departamento de Matemáticas, Universidad Autónoma de Madrid, Madrid 28049, Spain

E-mail Address: [email protected]

Corresponding author.

Search for more papers by this author

https://doi.org/10.1142/S0218202521500329Cited by:9 (Source: Crossref)

Abstract

We model, simulate and control the guiding problem for a herd of evaders under the action of repulsive drivers. The problem is formulated in an optimal control framework, where the drivers (controls) aim to guide the evaders (states) to a desired region of the Euclidean space. The numerical simulation of such models quickly becomes unfeasible for a large number of interacting agents, as the number of interactions grows $O (N^{2})$ for $N$ agents. For reducing the computational cost to $O (N)$ , we use the Random Batch Method (RBM), which provides a computationally feasible approximation of the dynamics. First, the considered time interval is divided into a number of subintervals. In each subinterval, the RBM randomly divides the set of particles into small subsets (batches), considering only the interactions inside each batch. Due to the averaging effect, the RBM approximation converges to the exact dynamics in the $L^{2}$ -expectation norm as the length of subintervals goes to zero. For this approximated dynamics, the corresponding optimal control can be computed efficiently using a classical gradient descent. The resulting control is not optimal for the original system, but for a reduced RBM model. We therefore adopt a Model Predictive Control (MPC) strategy to handle the error in the dynamics. This leads to a semi-feedback control strategy, where the control is applied only for a short time interval to the original system, and then compute the optimal control for the next time interval with the state of the (controlled) original dynamics. Through numerical experiments we show that the combination of RBM and MPC leads to a significant reduction of the computational cost, preserving the capacity of controlling the overall dynamics.

Communicated by N. Bellomo

Keywords:

AMSC: 49M29, 90C59, 93B51

References

1. J. A. E. Andersson, J. Gillis, G. Horn, J. B. Rawlings and M. Diehl , Casadi: A software framework for nonlinear optimization and optimal control, Math. Program. Comput. 11 (2019) 1–36. Crossref, Web of Science, Google Scholar
2. R. Bailo, M. Bongini, J. A. Carrillo and D. Kalise , Optimal consensus control of the Cucker-Smale model, IFAC-PapersOnLine 51 (2018) 1–6. Crossref, Google Scholar
3. U. Biccari, D. Ko and E. Zuazua , Dynamics and control for multi-agent networked systems: A finite-difference approach, Math. Models Methods Appl. Sci. 29 (2019) 755–790. Link, Web of Science, Google Scholar
4. M. Bongini, M. Fornasier, O. Junge and B. Scharf , Sparse control of alignment models in high dimension, Netw. Heterog. Media 10 (2015) 647–697. Crossref, Web of Science, Google Scholar
5. M. Bongini, M. Fornasier, F. Rossi and F. Solombrino , Mean-field Pontryagin maximum principle, J. Optim. Theory Appl. 175 (2017) 1–38. Crossref, Web of Science, Google Scholar
6. M. Burger, R. Pinnau, A. Roth, C. Totzeck and O. Tse, Controlling a self-organizing system of individuals guided by a few external agents — particle description and mean-field limit, preprint (2016), arXiv:1610.01325 [math]. Google Scholar
7. M. Caponigro, M. Fornasier, B. Piccoli and E. Trélat , Sparse stabilization and optimal control of the Cucker–Smale model, Math. Control. Relat. Fields 3 (2013) 447–466. Crossref, Web of Science, Google Scholar
8. J. A. Carrillo, Y.-P. Choi, P. B. Mucha and J. Peszek , Sharp conditions to avoid collisions in singular Cucker–Smale interactions, Nonlinear Anal. Real World Appl. 37 (2017) 317–328. Crossref, Web of Science, Google Scholar
9. J. A. Carrillo, Y.-P. Choi, C. Totzeck and O. Tse , An analytical framework for consensus-based global optimization method, Math. Models Methods Appl. Sci. 28 (2018) 1037–1066. Link, Web of Science, Google Scholar
10. J. A. Carrillo, S. Jin, L. Li and Y. Zhu , A consensus-based global optimization method for high dimensional machine learning problems, ESAIM Control Optim. Calc. Var. 27 (2021) S5. Crossref, Web of Science, Google Scholar
11. F. Cucker and J.-G. Dong , Avoiding Collisions in Flocks, IEEE Trans. Automat. Contr. 55 (2010) 1238–1243. Crossref, Web of Science, Google Scholar
12. F. Cucker and S. Smale , Emergent Behavior in Flocks, IEEE Trans. Automat. Contr. 52 (2007) 852–862. Crossref, Web of Science, Google Scholar
13. F. Dorfler and F. Bullo , Synchronization and transient stability in power networks and nonuniform kuramoto oscillators, SIAM J. Control. Optim. 50 (2012) 1616–1642. Crossref, Web of Science, Google Scholar
14. R. Escobedo, A. Ibañez and E. Zuazua , Optimal strategies for driving a mobile agent in a “guidance by repulsion” model, Commun. Nonlinear. Sci. 39 (2016) 58–72. Crossref, Web of Science, Google Scholar
15. J. A. Fax and R. M. Murray , Information flow and cooperative control of vehicle formations, IEEE Trans. Automat. Contr. 49 (2004) 1465–1476. Crossref, Web of Science, Google Scholar
16. S. Gade, A. A. Paranjape and S.-J. Chung , Herding a flock of birds approaching an airport using an unmanned aerial vehicle, in AIAA Guidance, Navigation, and Control Conf. (AIAA SciTech Forum, 2015), 1540. Crossref, Google Scholar
17. C. E. García, D. M. Prett and M. Morari , Model predictive control: Theory and practice—A survey, Automatica 25 (1989) 335–348. Crossref, Web of Science, Google Scholar
18. F. Golse , The mean-field limit for the dynamics of large particle systems, J. Équ. Dériv. Partielles 9 (2003) 1–47. Google Scholar
19. L. Grüne and J. Pannek , Nonlinear model predictive control, in Nonlinear Model Predictive Control (Springer, 2017), pp. 45–69. Crossref, Google Scholar
20. S.-Y. Ha, S. Jin and D. Kim , Convergence of a first-order consensus-based global optimization algorithm, Math. Models Methods Appl. Sci. 30 (2021) 2417–2444. Link, Web of Science, Google Scholar
21. S.-Y. Ha and J.-G. Liu , A simple proof of the Cucker–Smale flocking dynamics and mean-field limit, Commun. Math. Sci. 7 (2009) 297–325. Crossref, Web of Science, Google Scholar
22. S. Jin, L. Li and J.-G. Liu , Random Batch Methods (RBM) for interacting particle systems, J. Comput. Phys. 400 (2020) 108877. Crossref, Web of Science, Google Scholar
23. D. Ko and E. Zuazua , Asymptotic behavior and control of a “guidance by repulsion” model, Math. Models Methods Appl. Sci. 30 (2020) 765–804. Link, Web of Science, Google Scholar
24. J. M. Lien, O. B. Bayazit, R. T. Sowell, S. Rodriguez and N. M. Amato , Shepherding behaviors, in Proc. IEEE Int. Conf. Robotics and Automation, 2004, ICRA ’04. 2004, Vol. 4 (IEEE, New Orleans, LA, USA, 2004), pp. 4159–4164. Crossref, Google Scholar
25. J. Ma and E. M.-K. Lai , Finite-time flocking control of a swarm of Cucker–Smale agents with collision avoidance, in 2017 24th Int. Conf. Mechatronics and Machine Vision in Practice (M2VIP) (IEEE, Auckland, 2017), pp. 1–6. Crossref, Google Scholar
26. P. Mhaskar , Robust model predictive control design for fault-tolerant control of process systems, Ind. Eng. Chem. Res. 45 (2006) 8565–8574. Crossref, Web of Science, Google Scholar
27. S. Motsch and E. Tadmor , A new model for self-organized dynamics and its flocking behavior, J. Stat. Phys. 144 (2011) 923–947. Crossref, Web of Science, Google Scholar
28. M. Nikolaou , Model predictive controllers: A critical synthesis of theory and industrial needs, Adv. Chem. Eng. 26 (2001) 131–204. Crossref, Google Scholar
29. J. Park, H. J. Kim and S.-Y. Ha , Cucker–Smale flocking with inter-particle bonding forces, IEEE Trans. Automat. Contr. 55 (2010) 2617–2623. Crossref, Web of Science, Google Scholar
30. B. Piccoli, N. P. Duteil and E. Trélat , Sparse control of Hegselmann–Krause models: Black hole and declustering, SIAM J. Control. Optim. 57 (2019) 2628–2659. Crossref, Web of Science, Google Scholar
31. R. Pinnau and C. Totzeck , Interacting particles and optimization, PAMM 18 (2018) e201800182. Crossref, Google Scholar
32. L. S. Pontryagin , Mathematical Theory of Optimal Processes (Routledge, 2018). Crossref, Google Scholar
33. M. Porfiri and M. Di Bernardo , Criteria for global pinning-controllability of complex networks, Automatica 44 (2008) 3100–3106. Crossref, Web of Science, Google Scholar
34. D. M. Prett and C. E. Garcia , Design of robust process controllers, IFAC Proc. 20 (1987) 275–280. Crossref, Google Scholar
35. V. Rokhlin , Rapid solution of integral equations of classical potential theory, J. Comput. Phys. 60 (1985) 187–207. Crossref, Web of Science, Google Scholar
36. D. Strömbom, R. P. Mann, A. M. Wilson, S. Hailes, A. J. Morton, D. J. T. Sumpter and A. J. King , Solving the shepherding problem: Heuristics for herding autonomous, interacting agents, J. R. Soc. Interface 11 (2014) 20140719. Crossref, Web of Science, Google Scholar
37. H. G. Tanner, A. Jadbabaie and G. J. Pappas , Flocking in fixed and switching networks, IEEE Trans. Automat. Contr. 52 (2007) 863–868. Crossref, Web of Science, Google Scholar
38. E. Trélat , Contrôle Optimal: Théorie and Applications (Vuibert Paris, 2005). Google Scholar