### Abstract

Any-angle pathfinding is a common problem from robotics and computer games: it requires finding a Euclidean shortest path between a pair of points in a grid map. Prior research has focused on approximate online solutions. A number of exact methods exist but they all require supra-linear space and preprocessing time. In this paper we describe Anya: a new optimal any-angle pathfinding algorithm which searches over sets of states represented as intervals. Each interval is identified online. From each we select a representative point to derive a corresponding f-value for the set. Anya always returns an optimal path. Moreover it does so entirely online, without any preprocessing or memory overheads. This result answers an open question from the areas of Artificial Intelligence and Game Development: is there an any-angle pathfinding algorithm which is online and optimal? The answer is yes.

Original language | English |
---|---|

Title of host publication | Proceedings of the Twenty-Third International Conference on Automated Planning and Scheduling |

Editors | Daniel Borrajo, Simone Fratini, Subbarao Kambhampati, Angelo Oddi |

Place of Publication | Menlo Park, California |

Publisher | AAAI Press |

Pages | 308-311 |

Number of pages | 4 |

ISBN (Print) | 9781577356097 |

Publication status | Published - 2013 |

Externally published | Yes |

Event | International Conference on Automated Planning and Scheduling 2013 - Auditorium Antonianum, Rome, Italy Duration: 10 Jun 2013 → 14 Jun 2013 Conference number: 23 http://icaps13.icaps-conference.org/ |

### Conference

Conference | International Conference on Automated Planning and Scheduling 2013 |
---|---|

Abbreviated title | ICAPS 2013 |

Country | Italy |

City | Rome |

Period | 10/06/13 → 14/06/13 |

Internet address |

### Cite this

*Proceedings of the Twenty-Third International Conference on Automated Planning and Scheduling*(pp. 308-311). Menlo Park, California: AAAI Press.

}

*Proceedings of the Twenty-Third International Conference on Automated Planning and Scheduling.*AAAI Press, Menlo Park, California, pp. 308-311, International Conference on Automated Planning and Scheduling 2013, Rome, Italy, 10/06/13.

**An optimal any-angle pathfinding algorithm.** / Harabor, Daniel; Grastien, Alban.

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Other › peer-review

TY - GEN

T1 - An optimal any-angle pathfinding algorithm

AU - Harabor, Daniel

AU - Grastien, Alban

PY - 2013

Y1 - 2013

N2 - Any-angle pathfinding is a common problem from robotics and computer games: it requires finding a Euclidean shortest path between a pair of points in a grid map. Prior research has focused on approximate online solutions. A number of exact methods exist but they all require supra-linear space and preprocessing time. In this paper we describe Anya: a new optimal any-angle pathfinding algorithm which searches over sets of states represented as intervals. Each interval is identified online. From each we select a representative point to derive a corresponding f-value for the set. Anya always returns an optimal path. Moreover it does so entirely online, without any preprocessing or memory overheads. This result answers an open question from the areas of Artificial Intelligence and Game Development: is there an any-angle pathfinding algorithm which is online and optimal? The answer is yes.

AB - Any-angle pathfinding is a common problem from robotics and computer games: it requires finding a Euclidean shortest path between a pair of points in a grid map. Prior research has focused on approximate online solutions. A number of exact methods exist but they all require supra-linear space and preprocessing time. In this paper we describe Anya: a new optimal any-angle pathfinding algorithm which searches over sets of states represented as intervals. Each interval is identified online. From each we select a representative point to derive a corresponding f-value for the set. Anya always returns an optimal path. Moreover it does so entirely online, without any preprocessing or memory overheads. This result answers an open question from the areas of Artificial Intelligence and Game Development: is there an any-angle pathfinding algorithm which is online and optimal? The answer is yes.

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

M3 - Conference Paper

SN - 9781577356097

SP - 308

EP - 311

BT - Proceedings of the Twenty-Third International Conference on Automated Planning and Scheduling

A2 - Borrajo, Daniel

A2 - Fratini, Simone

A2 - Kambhampati, Subbarao

A2 - Oddi, Angelo

PB - AAAI Press

CY - Menlo Park, California

ER -