Multi-agent rendezvous on street networks

In this paper we present an algorithm for finding a distance optimal rendezvous location with respect to both initial and target locations of the mobile agents. These agents can be humans or robots, who need to meet and split while performing a collaborative task. Our aim is to embed the meeting process within a background activity such that the agents travel through the rendezvous location while taking the shortest paths to their respective target locations. We analyze this problem in a street network scenario with two agents who are given their individual scheduled routes to complete with an underlying common goal. The agents are allowed to select any combination of the waypoints along their routes as long as they travel the shortest path and pass through the same potential rendezvous location. The total number of path combinations that the agents need to evaluate for the shortest path increases rapidly with the number of waypoints along their routes. We address this computational cost by proposing a combination of Euclidean and street network distances for a trade-off between the number of queries and a distance optimal solution.

Authors

• Malika Meghjani
• Gregory Dudek

Keywords

• Robots
• Bridges
• Servers
• Roads
• Databases
• Google
• Euclidean distance
• Road Network
• Target Location
• Shortest Path
• Background Activity
• Position Of Agent
• Mobile Agents
• Reduction In The Number
• Path Length
• Real Applications
• Geographic Information System
• Goal Of This Work
• Load Balancing
• Hybrid Algorithm
• Total Path Length
• Original Path
• Online Problem