Planning Optimal Paths for Multi-agent Systems on Graphs

Details Planning Optimal Paths for Multi-agent Systems on Graphs Planning Optimal Paths for Multi-agent Systems on Graphs

2012-04-17

arxiv.org/abs/1204.3830v1

Computer Science

Robotics

Scientific paper

For the problem of moving a set of agents on a connected graph with unit edge distance to agent-specific goal locations, free of collisions, we propose two multiflow based integer linear programming (ILP) models that find time optimal and distance optimal solutions, respectively. The resulting algorithms from our ILP models are complete and guaranteed to yield true optimal solutions. Focusing on the time optimal formulation, we evaluate its performance, both as a stand alone algorithm and as a generic heuristic for quickly solving large problem instances. The computational results confirm the effectiveness of our method.

Affiliated with

Also associated with

No associations

Rating

Planning Optimal Paths for Multi-agent Systems on Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Planning Optimal Paths for Multi-agent Systems on Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Planning Optimal Paths for Multi-agent Systems on Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-290363