### Abstract

Given a collection of robots sharing a common environment, assume that each possesses an individual roadmap for its C-space and a cost function for attaining a goal. Vector-valued (or Pareto) optima for collision-free coordination are by no means unique: in fact, continua of optimal coordinations are possible. However, for cylindrical obstacles (those defined by pairwise interactions), we prove a finite bound on the number of optimal coordinations. For such systems, we present an exact algorithm for reducing a coordination scheme to its Pareto optimal representative.

Original language | English (US) |
---|---|

Title of host publication | Algorithmic Foundations of Robotics VI |

Pages | 171-186 |

Number of pages | 16 |

Volume | 17 |

State | Published - 2005 |

### Publication series

Name | Springer Tracts in Advanced Robotics |
---|---|

Volume | 17 |

ISSN (Print) | 1610-7438 |

ISSN (Electronic) | 1610-742X |

### Fingerprint

### ASJC Scopus subject areas

- Artificial Intelligence
- Electrical and Electronic Engineering

### Cite this

*Algorithmic Foundations of Robotics VI*(Vol. 17, pp. 171-186). (Springer Tracts in Advanced Robotics; Vol. 17).

**Pareto optimal coordination on Roadmaps.** / Ghrist, Robert; O'Kane, Jason M.; Lavalle, Steven M.

Research output: Chapter in Book/Report/Conference proceeding › Chapter

*Algorithmic Foundations of Robotics VI.*vol. 17, Springer Tracts in Advanced Robotics, vol. 17, pp. 171-186.

}

TY - CHAP

T1 - Pareto optimal coordination on Roadmaps

AU - Ghrist, Robert

AU - O'Kane, Jason M.

AU - Lavalle, Steven M

PY - 2005

Y1 - 2005

N2 - Given a collection of robots sharing a common environment, assume that each possesses an individual roadmap for its C-space and a cost function for attaining a goal. Vector-valued (or Pareto) optima for collision-free coordination are by no means unique: in fact, continua of optimal coordinations are possible. However, for cylindrical obstacles (those defined by pairwise interactions), we prove a finite bound on the number of optimal coordinations. For such systems, we present an exact algorithm for reducing a coordination scheme to its Pareto optimal representative.

AB - Given a collection of robots sharing a common environment, assume that each possesses an individual roadmap for its C-space and a cost function for attaining a goal. Vector-valued (or Pareto) optima for collision-free coordination are by no means unique: in fact, continua of optimal coordinations are possible. However, for cylindrical obstacles (those defined by pairwise interactions), we prove a finite bound on the number of optimal coordinations. For such systems, we present an exact algorithm for reducing a coordination scheme to its Pareto optimal representative.

UR - http://www.scopus.com/inward/record.url?scp=84862146102&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84862146102&partnerID=8YFLogxK

M3 - Chapter

AN - SCOPUS:84862146102

SN - 9783540257288

VL - 17

T3 - Springer Tracts in Advanced Robotics

SP - 171

EP - 186

BT - Algorithmic Foundations of Robotics VI

ER -