國立虎尾科技大學 |

Shortest path problems : = Domain restriction, anytime planning, and multi-objective optimization.

Record Type:	Language materials, manuscript : Monograph/item
Title/Author:	Shortest path problems :/
Reminder of title:	Domain restriction, anytime planning, and multi-objective optimization.
Author:	Clawson, Zachary.
Description:	1 online resource (164 pages)
Notes:	Source: Dissertation Abstracts International, Volume: 78-06(E), Section: B.
Subject:	Applied mathematics. -
Online resource:	click for full text (PQDT)
ISBN:	9781369561388

Shortest path problems : = Domain restriction, anytime planning, and multi-objective optimization.
Clawson, Zachary.

Shortest path problems :Domain restriction, anytime planning, and multi-objective optimization. - 1 online resource (164 pages)

Source: Dissertation Abstracts International, Volume: 78-06(E), Section: B.

Thesis (Ph.D.)--Cornell University, 2017.

Includes bibliographical references

Optimal path problems arise in many applications and several efficient methods are widely used for solving them on the whole domain. However, practitioners are often only interested in the solution at one specific source point, i.e. the shortest path to the exit-set from a particular starting location. This thesis will focus on three separate, but related, problems of this form. We employ solution methods that discretize the computational domain and recover an approximate solution to the shortest path problem. These methods either solve the problem on a geometrically embedded graph or approximate the viscosity solution to a static Hamilton-Jacobi PDE.

Electronic reproduction.
Ann Arbor, Mich. :
ProQuest,
2018

Mode of access: World Wide Web

ISBN: 9781369561388Subjects--Topical Terms:

1069907
Applied mathematics.
Index Terms--Genre/Form:

554714
Electronic books.

Shortest path problems : = Domain restriction, anytime planning, and multi-objective optimization.
LDR:03888ntm a2200349K 4500 001 914732
005 20180724121429.5
006 m o u
007 cr mn||||a|a||
008 190606s2017 xx obm 000 0 eng d
020 $a 9781369561388
035 $a (MiAaPQ)AAI10254223
035 $a (MiAaPQ)cornellgrad:10189
035 $a AAI10254223
040 $a MiAaPQ $b eng $c MiAaPQ
100 1 $a Clawson, Zachary. $3 1188060
245 1 0 $a Shortest path problems : $b Domain restriction, anytime planning, and multi-objective optimization.
264 0 $c 2017
300 $a 1 online resource (164 pages)
336 $a text $b txt $2 rdacontent
337 $a computer $b c $2 rdamedia
338 $a online resource $b cr $2 rdacarrier
500 $a Source: Dissertation Abstracts International, Volume: 78-06(E), Section: B.
500 $a Adviser: Alexander B. Vladimirsky.
502 $a Thesis (Ph.D.)--Cornell University, 2017.
504 $a Includes bibliographical references
520 $a Optimal path problems arise in many applications and several efficient methods are widely used for solving them on the whole domain. However, practitioners are often only interested in the solution at one specific source point, i.e. the shortest path to the exit-set from a particular starting location. This thesis will focus on three separate, but related, problems of this form. We employ solution methods that discretize the computational domain and recover an approximate solution to the shortest path problem. These methods either solve the problem on a geometrically embedded graph or approximate the viscosity solution to a static Hamilton-Jacobi PDE.
520 $a Such paths can be viewed as characteristics of static Hamilton-Jacobi equations, so we restrict the computations to a neighborhood of the characteristic. We explain how heuristic under/over-estimate functions can be used to obtain a causal domain restriction, significantly decreasing the computational work without sacrificing convergence under mesh refinement. The discussed techniques are inspired by an alternative version of the classical A* algorithm on graphs. We illustrate the advantages of our approach on continuous isotropic examples in 2D and 3D. We compare its efficiency and accuracy to previous domain restriction techniques and analyze the behavior of errors under the grid refinement.
520 $a However, if the heuristic functions used are very inaccurate this can lead to A*-type methods providing little to no restriction. One solution is to scale-up the underestimate functions used so that they become more accurate on parts of the domain. However, this will cause the algorithm to recover suboptimal, albeit locally optimal, solutions. These algorithms quickly produce an initial suboptimal solution that is iteratively improved. This ensures early availability of a good suboptimal path before the completion of the search for a globally optimal path. We illustrate the algorithm on examples where previous A*-FMM algorithms are unable to provide significant savings due to the poor quality of the heuristics.
520 $a Finally we present a related algorithm for finding optimal paths on graphs with respect to two criteria simultaneously. Our approach is based on augmenting the state space to keep track of the "budget" remaining to satisfy the constraints on secondary cost. The resulting augmented graph is acyclic and the primary cost can be then minimized by a simple upward sweep through budget levels. The efficiency and accuracy of our algorithm is tested on Probabilistic Roadmap graphs to minimize the distance of travel subject to a constraint on the overall threat exposure to enemy observers.
533 $a Electronic reproduction. $b Ann Arbor, Mich. : $c ProQuest, $d 2018
538 $a Mode of access: World Wide Web
650 4 $a Applied mathematics. $3 1069907
655 7 $a Electronic books. $2 local $3 554714
690 $a 0364
710 2 $a ProQuest Information and Learning Co. $3 1178819
710 2 $a Cornell University. $b Applied Mathematics. $3 1188061
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=10254223 $z click for full text (PQDT)