Efficient routing of multiple vehicles with no explicit communications

DOI10.1002/RNC.1258MaRDI QIDQ5443602zbMATH OpenOpenAlexFDO

Authors Alessandro Arsie, Emilio Frazzoli

Publication date 21 February 2008

Published in International Journal of Robust and Nonlinear Control (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0609624

zbMATH Keywords

cooperative controltask assignmentvehicle routing

Mathematics Subject Classification ID

Traffic problems in operations research (90B20) Decentralized systems (93A14) Stochastic systems in control theory (general) (93E03)

Abstract: 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 propose control strategies that, while making minimal or no assumptions on communications between agents, provide the same level of steady-state performance achieved by the best known decentralized strategies. In other words, we demonstrate that inter-agent communication does not improve the efficiency of such systems, but merely affects the rate of convergence to the steady state. Furthermore, the proposed strategies do not rely on the knowledge of the details of the underlying stochastic process. Finally, we show that our proposed strategies provide an efficient, pure Nash equilibrium in a game theoretic formulation of the problem, in which each agent's objective is to maximize the number of targets it visits. Simulation results are presented and discussed.

Recommendations

• Distributed stochastic multi-vehicle routing in the Euclidean plane with no communications
• Gossip algorithms for heterogeneous multi-vehicle routing problems
• Stochastic and Dynamic Vehicle Routing in the Euclidean Plane with Multiple Capacitated Vehicles
• Cooperative receding horizon strategies for the multivehicle routing problem
• Centralized and distributed cooperative receding horizon control of autonomous vehicle missions

Cites work

• Efficient Routing Algorithms for Multiple Vehicles With no Explicit Communications

Cited in

(12)

• Multiple UAV exploration of an unknown region
• The effects of regularity on the geometrical properties of Voronoi tessellations
• Stochastic control and time scheduling for irregular robots
• Gossip algorithms for heterogeneous multi-vehicle routing problems
• On the compression of locational and environmental data in multi-vehicle missions: a control systems approach
• Cloud conveyors system: a versatile application for exploring cyber-physical systems
• Distributed stochastic multi-vehicle routing in the Euclidean plane with no communications
• Cooperative receding horizon strategies for the multivehicle routing problem
• Efficient Routing Algorithms for Multiple Vehicles With no Explicit Communications
• A distributed protocol for motion coordination in free-range vehicular systems
• Spatio-temporal multi-robot routing
• Sufficient conditions for connectivity maintenance and rendezvous in leader-follower networks

This page was built for publication: Efficient routing of multiple vehicles with no explicit communications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5443602)