Shortest Paths Among Dynamic Obstacles
Public Deposited- Resource Type
- Creator
- Abstract
The problem of collision-free motion planning in dynamic environments has received considerable attention in computational geometry. In this thesis, we study the point robot motion planning problems among dynamic obstacles. A growing disc is a disc obstacle that grows over time. A transient obstacle is an obstacle that appears at a particular time in the environment and may disappear at some later time. In the first part of this thesis, we study the problem of computing collision-free shortest paths among growing discs. This problem has previously been studied for discs where the growth rates are fixed. We study a more general problem variant, where: (1) the speeds at which the discs grow are polynomial functions of degree β and (2) the source and destination points are given as query points. We show how to preprocess a set ofngrowing discs so that, for two given query pointssandd, a shortest path fromstodcan be computed in O(n2log(βn)) time. The preprocessing time of our algorithm is O(n2log n + k log k) wherekis the number of intersections between the growing discs and the tangent paths (straight line paths that touch the boundaries of a pair of growing discs). We also establish an upper bound of O(n3β) onk.In the second part of the thesis, we study the problem of computing collision-free shortest paths among transient obstacles. First, we design an optimal Θ(n log n) algorithm for determining time-minimal rectilinear paths amongnnon-intersecting transient rectilinear obstacles. Next, we consider the variant of the shortest path problem among transient obstacles where the metric used to measure distances is Euclidean and the obstacles are non-intersecting polygons. We present an O(n2log n) time algorithm for computing the Euclidean shortest path map among transient polygonal obstacles in the plane. This improves the time complexity of the existing algorithm by a factor ofn. We show that the shortest path map contains Ω(n2) cells, and thus, proving that our algorithm is nearly optimal.
- Subject
- Language
- Publisher
- Thesis Degree Level
- Thesis Degree Name
- Thesis Degree Discipline
- Identifier
- Rights Notes
Copyright © 2019 the author(s). Theses may be used for non-commercial research, educational, or related academic purposes only. Such uses include personal study, research, scholarship, and teaching. Theses may only be shared by linking to Carleton University Institutional Repository and no part may be used without proper attribution to the author. No part may be used for commercial purposes directly or indirectly via a for-profit platform; no adaptation or derivative works are permitted without consent from the copyright owner.
- Date Created
- 2019
Relations
- In Collection:
Items
Thumbnail | Title | Date Uploaded | Visibility | Actions |
---|---|---|---|---|
nourisagharlou-shortestpathsamongdynamicobstacles.pdf | 2023-05-05 | Public | Download |