Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Autonomous Robots
Erschienen in: Autonomous Robots 4/2015

01.12.2015

Decentralized probabilistic density control of autonomous swarms with safety constraints

verfasst von: Nazlı Demir, Utku Eren, Behçet Açıkmeşe

Erschienen in: Autonomous Robots | Ausgabe 4/2015

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

This paper presents a Markov chain based approach for the probabilistic density control of a large number, swarm, of autonomous agents. The proposed approach specifies the time evolution of the probabilistic density distribution by using a Markov chain, which guides the swarm to a desired steady-state distribution, while satisfying the prescribed ergodicity, motion, and safety constraints. This paper generalizes our previous results on density upper bound constraints and captures a general class of linear safety constraints that bound the flow of agents. The safety constraints are formulated as equivalent linear inequality conditions on the Markov chain matrices by using the duality theory of convex optimization which is our first contribution. With the safety constraints, we can facilitate proper low-level conflict avoidance policies to compute and execute the detailed agent state trajectories. Our second contribution is to develop (i) linear matrix inequality based offline methods, and (ii) quadratic programming based online methods that can incorporate these constraints into the Markov chain synthesis. The offline method provides a feasible solution for Markov matrix when there is no density feedback. The online method utilizes realtime estimates of the swarm density distribution to continuously update the Markov matrices to maximize the convergence rates within the problem constraints. The paper also introduces a decentralized method to compute the density estimates needed for the online synthesis method.
Vorheriger Artikel Constrained decision-making for low-count radiation detection by mobile sensors
Nächster Artikel Chance-constrained dynamic programming with application to risk-aware robotic space exploration

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren
Anhänge
Nur mit Berechtigung zugänglich
Literatur
Açıkmeşe, B., & Bayard, D. S. (2012). A Markov chain approach to probabilistic swarm guidance. In American control conference, montreal, Canada (pp. 6300–6307).
Açıkmeşe, B., & Bayard, D. S. (2015). Markov chain approach to probabilistic guidance for swarms of autonomous agents. Asian Journal of Control, 17(4), 1–20.MathSciNet
Açıkmeşe, B., Demir, N., & Harris, M. (2014). Convex necessary and sufficient conditions for density safety constraints in markov chain convex necessary and sufficient conditions for density safety constraints in markov chain synthesis. IEEE Transactions on Automatic Control (Accepted).
Açıkmeşe, B., Hadaegh, F. Y., Scharf, D. P., & Ploen, S. R. (2007). Formulation and analysis of stability for spacecraft formations. IET Control Theory & Applications, 1(2), 461–474.CrossRef
Arapostathis, A., Kumar, R., & Tangirala, S. (2003). Controlled markov chains with safety upper bound. IEEE Transactions on Automatic Control, 48(7), 1230–1234.MathSciNetCrossRef
Arslan, G., Marden, J. R., & Shamma, J. S. (2007). Autonomous vehicle-target assignment: A game-theoretical formulation. ASME Journal of Dynamic Systems, Measurement, and Control, 129(5), 197–584.CrossRef
Bai, H., Arcak, M., & Wen, J. T. (2008). Adaptive design for reference velocity recovery in motion coordination. Systems & Control Letters, 57(8), 602–610.MATHMathSciNetCrossRef
Berkovitz, L. D. (2002). Convexity and optimization in \(R^{n}\). New York: Wiley.
Berman, A., & Plemmons, R. J. (1994). Nonnegative matrices in the mathematical sciences. SIAM.
Bertsekas, D. P., & Tsitsiklis, J. N. (2007). Comments on on coordination of groups of mobile autonomous agents using nearest neighbor rules. IEEE Transaction on Automatic Control, 52(5), 968–969.MathSciNetCrossRef
Boyd, S., Diaconis, P., Parillo, P., & Xiao, L. (2009). Fastest mixing Markov chain on graphs with symmetries. SIAM Journal of Optimization, 20(2), 792–819.MATHCrossRef
Boyd, S., El Ghaoui, L., Feron, E., & Balakrishnan, V. (1994). Linear matrix inequalities in system and control theory. SIAM.
Boyd, S., & Vandenberghe, L. (2004). Convex optimization. Cambridge, MA: Cambridge University Press.MATHCrossRef
Chattopadhyay, I., & Ray, A. (2009). Supervised self-organization of homogeneous swarms using ergodic projections of markov chains. IEEE Transaction on Systems, Man, and Cybernetics, 39(6), 1505–1515.CrossRef
Chung, K. L. (2001). A course in probability theory. London: Academic Press.
Corless, M., & Frazho, A. E. (2003). Linear systems and control: An operator perspective. New York: Marcel Dekker.CrossRef
Cortés, J., Martínez, S., Karatas, T., & Bullo, F. (2004). Coverage control for mobile sensing networks. IEEE Transactions on Robotics and Automation, 20(2), 243–255.CrossRef
de Oliveira, M.C., Bernussou, J., & Geromel, J. C. (1999). Anew discrete-time robust stability condition. Systems and Control Letters, pages 261–265.
Demir, N., Açıkmeşe, B., & Harris, M. (2014). Convex optimization formulation of density upper bound constraints in Markov chain synthesis. In American control conference (pp. 483–488). June 4-6 2014.
Demir, N., Açıkmeşe, B., & Pehlivanturk, C. (2014). Density control for decentralized autonomous agents with conflict avoidance. In IFAC world congress (pp. 11715–11721).
Deo, N. (1974). Graph theory with applications to engineering and computer science. Englewood Cliffs, NJ: Prentice-Hall.MATH
Domahidi, A., Chu, E., & Boyd, S. (2013). ECOS: An SOCP solver for embedded systems. In European control conference (ECC) (pp. 3071–3076).
Dueri, D., Açıkmeşe, B., Baldwin, M., & Erwin, R. S. (2014). Finite-horizon controllability and reachability for deterministic and stochastic linear control systems with convex constraints. In American control conference (ACC), 2014 (pp. 5016–5023). IEEE.
Dueri, D., Zhang, J., & Açıkmeşe, B. (2014). Automated custom code generation for embedded, real-time second order cone programming. In IFAC world congress.
Fiedler, M. (1973). Algebraic connectivity of graphs. Czechoslovak Mathematical Journal, 23(2), 298–305.MathSciNet
Fiedler, M. (2008). Special matrices and their applications in numerical mathematics. New York: Dover.MATH
Girard, A., & Le Guernic, C. (2008). Zonotope/hyperplane intersection for hybrid systems reachability analysis. In M. Egerstedt & B. Mishra (Eds.), Hybrid systems: Computation and control. Lecture notes in computer science (Vol. 4981, pp. 215–228). Berlin, Heidelberg: Springer.CrossRef
Grant, M., & Boyd, S. (2013). CVX: Matlab software for disciplined convex programming, version 2.0 beta.
Hadaegh, F. Y., Açıkmeşe, B., Bayard, D. S., Singh, G., Mandic, M., Chung, S., & Morgan, D. (2013). Guidance and control of formation flying spacecraft: From two to thousands. Festschrift honoring John L. Junkins, Tech Science Press (pp. 327–371).
Horn, R. A., & Johnson, C. R. (1985). Matrix analysis. Cambridge, MA: Cambridge University Press.MATHCrossRef
Horn, R. A., & Johnson, C. R. (1991). Topics in matrix analysis. Cambridge, MA: Cambridge University Press.MATHCrossRef
Hsieh, M. A., Halasz, A., Berman, S., & Kumar, V. (2008). Biologically inspired redistribution of a swarm of robots among multiple sites. Swarm Intelligence, 2(2–4), 121–141.CrossRef
Hsieh, M. A., Kumar, V., & Chaimowicz, L. (2008). Decentralized controllers for shape generation with robotic swarms. Robotica, 26(5), 691–701.CrossRef
Hsu, S., Arapostathis, A., & Kumar, R. (2006). On optimal control of Markov chains with safety constraint. In Proceeding of the American control conference (pp. 4516–4521).
Roos, C., Peng, J., & Terlaky, T. (2002). Self-regularity—A new paradigm for primal-dual interior-point algorithms. Princeton, NJ: Princeton University Press.MATH
Jadbabaie, A., Lin, G. J., & Morse, A. S. (2003). Coordination of groups of mobile autonomous agents using nearest neighbor rules. IEEE Transaction on Automatic Control, 48(6), 988–1001.MathSciNetCrossRef
Kalman, R. E., & Bertram, J. E. (1960). Control system analysis and design via the second method of Lyapunov, II: Discrete-time systems. Journal of Basic Engineering, 82, 394–400.MathSciNetCrossRef
Kim, Y., Mesbahi, M., & Hadaegh, F. (2004). Multiple-spacecraft reconfiguration through collision avoidance, bouncing, and stalemate. Journal of Optimization Theory and Applications, 122(2), 323–343.MATHMathSciNetCrossRef
Lawford, M., & Wonham, W. (1993). Supervisory control of probabilistic discrete event systems. In Proceedings of the 36th midwest symposium on circuits systems (pp. 327–331).
Löfberg, J. (2004). YALMIP: A toolbox for modeling and optimization in MATLAB. In Proceedings of the CACSD Conference, Taipei, Taiwan.
Lumelsky, V. J., & Harinarayan, K. R. (1997). Decentralized motion planning for multiple mobile robots: The cocktail party model. Autonomous Robots, 4(1), 121–135.CrossRef
Maidens, J., Kaynama, S., Mitchell, I., Oishi, M., & Dumont, G. (2013). Lagrangian methods for approximating the viability kernel in high-dimensional systems. Automatica, 49(7), 2017–2029.MathSciNetCrossRef
Martínez, S., Bullo, F., Cortés, J., & Frazzoli, E. (2007). On synchronous robotic networks-part II: Time complexity of rendezvous and deployment algorithms. IEEE Transaction on Automatic Control, 52(12), 2214–2226.CrossRef
Martínez, S., Cortés, J., & Bullo, F. (2007). Motion coordination with distributed information. In IEEE Control system magazine (pp. 75–88).
Mattingley, J., & Boyd, S. (2010). Real-time convex optimization in signal processing. IEEE Signal Processing Magazine, 27(3), 50–61.CrossRef
Mattingley, J., & Boyd, S. (2012). Cvxgen: A code generator for embedded convex optimization. Optimization and Engineering, 13(1), 1–27.MATHMathSciNetCrossRef
Mesbahi, M., & Egerstedt, M. (2010). Graph theoretic methods in multiagent networks. Princeton, NJ: Princeton University Press.MATHCrossRef
Mesquita, A. R., Hespanha, J. P., & Astrom, K. (2008). Optimotaxis: A stochastic multi-agent on site optimization procedure. Hybrid systems: Computation and control. Lecture notes in computional science, 4981, 358–371.MathSciNet
Nesterov, Y., & Nemirovsky, A. (1994). Interior-point polynomial methods in convex programming. SIAM.
Pallottino, L., Scordio, V., Bicchi, A., & Frazzoli, E. (2007). Decentralized cooperative policy for conflict resolution in multivehicle systems. IEEE Transaction on Robotics, 23(6), 1170–1183.CrossRef
Pavone, M., & Frazzoli, E. (2007). Decentralized policies for geometric pattern formation and path coverage. ASME Journal of Dynamic Systems, Measurement, and Control, 129(5), 633–643.CrossRef
Pavone, M., Frazzoli, E., & Bullo, F. (2011). Adaptive and distributed algorithms for vehicle routing in a stochastic and dynamic environment. IEEE Transaction on Automatic Control, 56(6), 1259–1274.MathSciNetCrossRef
Ramirez, J., Pavone, M., Frazzoli, E., & Miller, D. W. (2010). Distributed control of spacecraft formations via cyclic pursuit: Theory and experiments. AIAA Journal of Guidance, Control, and Dynamics, 33(5), 1655–1669.CrossRef
Richards, A., Schouwenaars, T., How, J., & Feron, E. (2002). Spacecraft trajectory planning with avoidance constraints using mixed-integer linear programming. AIAA Journal of Guidance, Control, and Dynamics, 25(4), 755–764.CrossRef
Scharf, D. P., Hadaegh, F., & Ploen, S. R. (2003). A survey of spacecraft formation flying guidance and control (part I): Guidance. In Proceedings of the American control conference.
Tillerson, M., Inalhan, G., & How, J. (2002). Coordination and control of distributed spacecraft systems using convex optimization techniques. International Journal of Robust Nonlinear Control, 12(1), 207–242.MATHCrossRef
Tutuncu, R. H., Toh, K. C., & Todd, M. J. (2003). Solving semidefinite-quadratic-linear programs using sdpt3. Mathematical Programming, 95(2), 189–217.MathSciNetCrossRef
Metadaten
Titel
Decentralized probabilistic density control of autonomous swarms with safety constraints
verfasst von
Nazlı Demir
Utku Eren
Behçet Açıkmeşe
Publikationsdatum
01.12.2015
Verlag
Springer US
Erschienen in
Autonomous Robots / Ausgabe 4/2015
Print ISSN: 0929-5593
Elektronische ISSN: 1573-7527
DOI
https://doi.org/10.1007/s10514-015-9470-z

Weitere Artikel der Ausgabe 4/2015

Autonomous Robots 4/2015 Zur Ausgabe

OriginalPaper

Chance-constrained dynamic programming with application to risk-aware robotic space exploration

OriginalPaper

Computationally aware control of autonomous vehicles: a hybrid model predictive control approach

OriginalPaper

Cognitive robots learning failure contexts through real-world experimentation

OriginalPaper

Constrained decision-making for low-count radiation detection by mobile sensors

OriginalPaper

A mechanism for real-time decision making and system maintenance for resource constrained robotic systems through ReFrESH

EditorialNotes

Guest Editorial: Special issue on constrained decision-making in robotics

Neuer Inhalt

    Bildnachweise