• Sorted by Date • Classified by Publication Type • Classified by Topic • Grouped by Student (current) • Grouped by Former Students •
Eyal Weiss. Graph Search and Automated Planning with Multiple Cost Estimators. Ph.D. Thesis, Bar Ilan University,
2026.
(unavailable)
The fields of graph search and automated planning have long relied on the simplifying assumption that the cost of applying an action or traversing an edge is known precisely and can be obtained at negligible computational expense. While this abstraction has enabled decades of theoretical progress and practical applications, it is increasingly mismatched with real-world problems, where costs are uncertain, expensive to compute, or available only through learned or external models. This dissertation addresses this fundamental gap by introducing new theoretical frameworks, problem formulations, and algorithms for planning and shortest-path search with multiple action- or edge-cost estimates.The dissertation begins by establishing a formal background for reasoning about multiple estimators in graph search. It introduces estimated weighted digraphs (EWDGs) in which each edge is associated with a finite sequence of estimators that provide progressively tighter lower and upper bounds at increasing computational cost. This generalization allows classical search and planning problems to be reformulated in a way that explicitly accounts for estimation effort.Building on this foundation, the dissertation develops formulations and methods for solving two central problems: finding paths that achieve the tightest possible lower bound on the optimal cost, and identifying paths that offer the strongest admissibility guarantees under estimator uncertainty. Together, these problems generalize the classical notion of shortest paths to settings where costs are only partially known and must be refined through computation. The work establishes the theoretical connections between these formulations, provides strategies for solving them optimally, and demonstrates empirically that reasoning explicitly about estimation effort can greatly reduce computational overhead while maintaining rigorous guarantees on solution quality.The dissertation next broadens the scope from graph search to automated planning. It begins by introducing the paradigm of online modeling for offline planning, which challenges the traditional view of planning over a fixed, fully specified model. Instead, planning is treated as a process that dynamically invokes cost estimators as needed, thereby reasoning explicitly about the trade-off between computational effort and estimation accuracy.Finally, the framework is instantiated in practical automated planning systems, where concrete planning algorithms that leverage multiple cost estimators for actions are suggested and implemented in a state-of-the-art planner. These algorithms can efficiently identify plans that meet specified suboptimality guarantees while attempting to minimize reliance on costly estimations. Through both synthetic benchmarks and a real-world transportation logistics problem, it is demonstrated that substantial savings in estimation effort and overall planning time can be achieved without sacrificing solution quality. This work provided the first end-to-end demonstration of planning systems that explicitly reason about cost-estimation time as part of the planning process.Taken together, the contributions of this dissertation advance a unified theoretical and algorithmic foundation for shortest-path search and planning in settings where costs are uncertain, expensive, or incrementally estimable. By extending classical formulations to account for multiple estimators and their trade-offs, the work bridges the gap between elegant models of search and the realities of practical decision-making systems. Beyond their theoretical significance, these results are directly applicable to domains such as robotics, logistics, and autonomous systems, where estimation cost and accuracy are inseparable from the planning process.In broad terms, this research opens the door to search and planning frameworks that are more expressive, resource-aware, and robust to uncertainty. By integrating cost estimation into the very definition of the planning problem, the dissertation redefines how optimality, admissibility, and efficiency are understood in modern AI search.
@PhdThesis{eyalweiss-phd,
author = {Eyal Weiss},
title = {Graph Search and Automated Planning with Multiple Cost Estimators},
school = {{B}ar {I}lan {U}niversity},
year = {2026},
wwwnote = {},
OPTannote = {} ,
abstract = {
The fields of graph search and automated planning have long relied on the simplifying assumption that the cost of applying an action or traversing an edge is known precisely and can be obtained at negligible computational expense. While this abstraction has enabled decades of theoretical progress and practical applications, it is increasingly mismatched with real-world problems, where costs are uncertain, expensive to compute, or available only through learned or external models. This dissertation addresses this fundamental gap by introducing new theoretical frameworks, problem formulations, and algorithms for planning and shortest-path search with multiple action- or edge-cost estimates.
The dissertation begins by establishing a formal background for reasoning about multiple estimators in graph search. It introduces \textbf{estimated weighted digraphs (EWDGs)} in which each edge is associated with a finite sequence of estimators that provide progressively tighter lower and upper bounds at increasing computational cost. This generalization allows classical search and planning problems to be reformulated in a way that explicitly accounts for estimation effort.
Building on this foundation, the dissertation develops formulations and methods for solving two central problems: finding paths that achieve the tightest possible lower bound on the optimal cost, and identifying paths that offer the strongest admissibility guarantees under estimator uncertainty. Together, these problems generalize the classical notion of shortest paths to settings where costs are only partially known and must be refined through computation. The work establishes the theoretical connections between these formulations, provides strategies for solving them optimally, and demonstrates empirically that reasoning explicitly about estimation effort can greatly reduce computational overhead while maintaining rigorous guarantees on solution quality.
The dissertation next broadens the scope from graph search to automated planning. It begins by introducing the paradigm of online modeling for offline planning, which challenges the traditional view of planning over a fixed, fully specified model. Instead, planning is treated as a process that dynamically invokes cost estimators as needed, thereby reasoning explicitly about the trade-off between computational effort and estimation accuracy.
Finally, the framework is instantiated in practical automated planning systems, where concrete planning algorithms that leverage multiple cost estimators for actions are suggested and implemented in a state-of-the-art planner. These algorithms can efficiently identify plans that meet specified suboptimality guarantees while attempting to minimize reliance on costly estimations. Through both synthetic benchmarks and a real-world transportation logistics problem, it is demonstrated that substantial savings in estimation effort and overall planning time can be achieved without sacrificing solution quality. This work provided the first end-to-end demonstration of planning systems that explicitly reason about cost-estimation time as part of the planning process.
Taken together, the contributions of this dissertation advance a unified theoretical and algorithmic foundation for shortest-path search and planning in settings where costs are uncertain, expensive, or incrementally estimable. By extending classical formulations to account for multiple estimators and their trade-offs, the work bridges the gap between elegant models of search and the realities of practical decision-making systems. Beyond their theoretical significance, these results are directly applicable to domains such as robotics, logistics, and autonomous systems, where estimation cost and accuracy are inseparable from the planning process.
In broad terms, this research opens the door to search and planning frameworks that are more expressive, resource-aware, and robust to uncertainty. By integrating cost estimation into the very definition of the planning problem, the dissertation redefines how optimality, admissibility, and efficiency are understood in modern AI search.
},
}
Generated by bib2html.pl (written by Patrick Riley ) on Sun Feb 08, 2026 18:23:11