Multi-criteria Shortest Paths in 3D among Vertical Obstacles

Show simple item record

dc.contributor.author Tran, N en
dc.contributor.author Dinneen, MJ en
dc.contributor.author Linz, S en
dc.date.accessioned 2020-01-10T01:36:48Z en
dc.date.available 2020-01-10T01:36:48Z en
dc.date.issued 2019 en
dc.identifier.citation CDMTCS Research Reports CDMTCS-538 (2019) en
dc.identifier.issn 1178-3540 en
dc.identifier.uri http://hdl.handle.net/2292/49487 en
dc.description.abstract This paper describes a new approach for finding an approximate Euclidean shortest path with additional constraints, which we call a multi-criteria shortest path, between two given points that avoids vertical obstacles in a three-dimensional space. Currently, there does not exist any polynomial-time algorithm that solves this problem exactly. Furthermore, existing approximation algorithms mostly fo- cus on reducing the running time at the expense of the accuracy with respect to the optimal length. Here, we aim at finding approximate shortest paths with re- duced lengths. To this end, our new algorithm is based on geometric principles to determine all obstacle segments and partial obstacle segments that are visible to each other. Using this information, we employ Mixed Integer Linear Programming to compute an approximate shortest path between two given points. We test our algorithm on a number of test cases and fi nd that our method returns approximate shortest paths that are shorter than those returned by other currently available algorithms. Moreover, our method is more flexible since it allows users to defi ne additional constraints or criteria in exploring different types of optimal paths. Our results can apply into path planning for unmanned aircraft vehicles or other sys- tems that require a near optimal shortest path. en
dc.publisher Department of Computer Science, The University of Auckland, New Zealand en
dc.relation.ispartofseries CDMTCS Research Report Series en
dc.rights Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher. en
dc.rights.uri https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm en
dc.source.uri https://www.cs.auckland.ac.nz/research/groups/CDMTCS/researchreports/index.php en
dc.title Multi-criteria Shortest Paths in 3D among Vertical Obstacles en
dc.type Technical Report en
dc.subject.marsden Fields of Research en
dc.rights.holder Copyright: The author(s) en
dc.rights.accessrights http://purl.org/eprint/accessRights/OpenAccess en


Files in this item

Find Full text

This item appears in the following Collection(s)

Show simple item record

Share

Search ResearchSpace


Browse

Statistics