Back to search

University of Southampton

Incremental search algorithms for on-line planning

Abstract

dc:description.abstract

<p>An <i>on-line </i>planning problem is one where an agent must optimise some objective criterion by making a sequence of action selection decisions, where the time and resources used in making decisions count in assessing overall solution quality. Typically in these problems it is not possible to find an optimal complete solution before an initial action must be executed, instead to maximise its performance the agent must interleave decision making and execution. This thesis investigates using decision theoretic techniques to solve these problems by equipping the agent with the ability to reason about the “complexity induced” uncertainties in its information and the costs of computation.</p> <p>The major sub-problems such an agent must solve are: i) decision making – how to make decisions whilst in a state of “complexity induced uncertainty”, ii) search control – which node to expand next, iii) stopping – when to stop searching. Decision making is treated as a value estimation problem. By representing the agent’s uncertainty in probabilistic terms this can be solved using decision theoretic techniques. Existing decision making systems are analysed and new low computational cost approximate decision theoretic algorithms developed. These are shown to give significant improvements in decision quality. Search control is also treated as an estimation problem, in this case estimating the expected value of computation (EVC), which is the expected benefit of a computation in reducing the agent’s uncertainty (hence improving action selection). New, low computational cost, approximations for the EVC are also developed and shown to give significant improvements in decision quality. Sophisticated stopping can be achieved by trading-off the EVC of further search against its computational cost. Experimental results show that integration of the sub-problem solutions is critical to agent performance. The results also show that (assuming no adverse interactions) improving decision making gives the greatest improvements, with search control and stopping offering more modest benefits.</p>

Degree

thesis:*
Name dc:type.qualificationname
Ph.D.
Level dc:type.qualificationlevel
doctoral
Grantor dc:publisher.institution
University of Southampton
Year dc:date.issued
2004

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Farquhar, Jason D.R

Rights

Language dc:language
English, eng

Chain of custody

source
Harvested from
University of Southampton
Base URL
eprints.soton.ac.uk/cgi/oai2
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Farquhar, Jason D.R. Incremental search algorithms for on-line planning. doctoral thesis, University of Southampton, 2004.