Game-theoretic learning algorithm for a spatial coverage problem
In this paper we consider a class of dynamic vehicle routing problems, in which a number of mobile agents in the plane must visit target points generated over time by a stochastic process. It is desired to design motion coordination strategies in order to minimize the expected time between the appea...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers
2010
|
| Online Access: | http://hdl.handle.net/1721.1/60305 https://orcid.org/0000-0002-0505-1400 |
| _version_ | 1826196752571564032 |
|---|---|
| author | Savla, Ketan Frazzoli, Emilio |
| author2 | Massachusetts Institute of Technology. Department of Aeronautics and Astronautics |
| author_facet | Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Savla, Ketan Frazzoli, Emilio |
| author_sort | Savla, Ketan |
| collection | MIT |
| description | In this paper we consider a class of dynamic vehicle routing problems, in which a number of mobile agents in the plane must visit target points generated over time by a stochastic process. It is desired to design motion coordination strategies in order to minimize the expected time between the appearance of a target point and the time it is visited by one of the agents. We cast the problem as a spatial game in which each agent's objective is to maximize the expected value of the à ¿time spent aloneà ¿ at the next target location and show that the Nash equilibria of the game correspond to the desired agent configurations. We propose learning-based control strategies that, while making minimal or no assumptions on communications between agents as well as the underlying distribution, provide the same level of steady-state performance achieved by the best known decentralized strategies. |
| first_indexed | 2024-09-23T10:37:28Z |
| format | Article |
| id | mit-1721.1/60305 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T10:37:28Z |
| publishDate | 2010 |
| publisher | Institute of Electrical and Electronics Engineers |
| record_format | dspace |
| spelling | mit-1721.1/603052022-09-30T21:50:38Z Game-theoretic learning algorithm for a spatial coverage problem Savla, Ketan Frazzoli, Emilio Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Frazzoli, Emilio Frazzoli, Emilio Savla, Ketan In this paper we consider a class of dynamic vehicle routing problems, in which a number of mobile agents in the plane must visit target points generated over time by a stochastic process. It is desired to design motion coordination strategies in order to minimize the expected time between the appearance of a target point and the time it is visited by one of the agents. We cast the problem as a spatial game in which each agent's objective is to maximize the expected value of the à ¿time spent aloneà ¿ at the next target location and show that the Nash equilibria of the game correspond to the desired agent configurations. We propose learning-based control strategies that, while making minimal or no assumptions on communications between agents as well as the underlying distribution, provide the same level of steady-state performance achieved by the best known decentralized strategies. 2010-12-17T16:38:31Z 2010-12-17T16:38:31Z 2010-01 2009-09 Article http://purl.org/eprint/type/ConferencePaper 978-1-4244-5870-7 INSPEC Accession Number: 11089501 http://hdl.handle.net/1721.1/60305 Savla, K., and E. Frazzoli. “Game-theoretic learning algorithm for a spatial coverage problem.” Communication, Control, and Computing, 2009. Allerton 2009. 47th Annual Allerton Conference on. 2009. 984-990. © 2010 IEEE. https://orcid.org/0000-0002-0505-1400 en_US http://dx.doi.org/10.1109/ALLERTON.2009.5394888 47th Annual Allerton Conference on Communication, Control, and Computing, 2009. Allerton 2009 Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Institute of Electrical and Electronics Engineers IEEE |
| spellingShingle | Savla, Ketan Frazzoli, Emilio Game-theoretic learning algorithm for a spatial coverage problem |
| title | Game-theoretic learning algorithm for a spatial coverage problem |
| title_full | Game-theoretic learning algorithm for a spatial coverage problem |
| title_fullStr | Game-theoretic learning algorithm for a spatial coverage problem |
| title_full_unstemmed | Game-theoretic learning algorithm for a spatial coverage problem |
| title_short | Game-theoretic learning algorithm for a spatial coverage problem |
| title_sort | game theoretic learning algorithm for a spatial coverage problem |
| url | http://hdl.handle.net/1721.1/60305 https://orcid.org/0000-0002-0505-1400 |
| work_keys_str_mv | AT savlaketan gametheoreticlearningalgorithmforaspatialcoverageproblem AT frazzoliemilio gametheoreticlearningalgorithmforaspatialcoverageproblem |