Approximate bi-criteria search by efficient representation of subsets of the Pareto-optimal frontier
| Bicriteria search Pareto frontier Approximate search |
PaperID: 17
pdf
poster
|
| We consider the bi-criteria shortest-path problem where we want to compute shortest paths on a graph that simultaneously balance two cost functions. While this problem has numerous applications, there is usually no path minimizing both cost functions simultaneously. Thus, we typically consider the set of paths where no path is strictly better than the others in both cost functions, a set called the Pareto-optimal frontier. Unfortunately, the size of this set may be exponential in the number of graph vertices and the general problem is NP-hard. While existing schemes to approximate this set exist, they may be slower than exact approaches when applied to relatively small instances and running them on graphs with even a moderate number of nodes is often impractical. The crux of the problem lies in how to efficiently approximate the Pareto-optimal frontier. Our key insight is that the Pareto-optimal frontier can be approximated using pairs of paths. This simple observation allows us to run a best-first-search while efficiently and effectively pruning away intermediate solutions in order to obtain an approximation of the Pareto frontier for any given approximation factor. We compared our approach with an adaptation of BOA*, the state-of-the-art algorithm for computing exact solutions to the bi-criteria shortest-path problem. Our experiments show that as the problem becomes harder, the speedup obtained becomes more pronounced. Specifically, on large roadmaps, when using an approximation factor of 10% we obtain a speedup on the average running time of more than X19. | |
Session 1: Search
Approximate bi-criteria search by efficient representation of subsets of the Pareto-optimal frontier
Authors: Oren Salzman and Boris Goldin
Keywords:
Bicriteria searchPareto frontierApproximate search
Conflict-Free Multi-Agent Meeting
Authors: Dor Atzmon, Shahar Idan Freiman, Oscar Epshtein, Oran Shichman and Ariel Felner
Keywords:
Conflict-Free Multi-Agent MeetingMulti-Agent MeetingMulti-Agent Path FindingIterative Meeting SearchMulti-Directional Heuristic SearchConflict-FreeConstraintMAMMAPFCF-MAPF
OMCoRP: An Online Mechanism for Competitive Robot Prioritization
Authors: Sankar Das, Swaprava Nath and Indranil Saha
Keywords:
Multi-Robot SystemCollision AvoidanceMechanism Design
Safe Multi-Agent Pathfinding with Time Uncertainty
Authors: Tomer Shahar, Shashank Shekhar, Dor Atzmon, Abdallah Saffidine, Brendan Juba and Roni Stern