Author name cluster

Mike Williamson

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

2 author rows

ICAPS Conference 1996 Conference Paper

Flaw Selection Strategies for Value-Directed Planning

Mike Williamson
Steve Hanks

The PYRRHUS planning system is a decision-theoretic extension to POCL planners that finds optimal plans for a class of goal-directed value functions. Although PYRRHUS uses a branch-and-bound algorithm instead of best-first satisficing search, it is faced with the same flaw selection decision as other POCL planners. This paper explains why popular domain-independent flaw-selection strategies are ineffective within an optimizing framework, and presents two new strategies that exploit the additional value information available to PYRRHUS.

Details

ICAPS Conference 1994 Conference Paper

Optimal Planning with a Goal-directed Utility Model

Mike Williamson
Steve Hanks

ClassicMAI planning adopts L very narrow notion of plan quality, namelythat a plan is goodjust in case it achieves a specified goal. Despite the fact that planning is intractable in the worst case, goal-satisfying planning algorithms can effectively solve classes of problems by using the goal to focus the search for a solution (by using backward-chaining techniques), and by exploiting domain-specific heuristic knowledge to control search. Our work extends the definition of plan quality to take into account partial satisfaction of the goal and the cost of resources used by the plan, while at the sametime building an effective planning algorithm by exploiting classical plamningtechniques like backward chaining aatd knowledge-based search control rules. This paper presents PYRRHUS, a~ extension to the ucPoe planning system (Barrett et ai. 1993) that finds optimal plans for a class of goal-directed utility models suggested by Hadd~wyand Hanks (Haddawy &Hanks1993). Our empirical results suggest that optimal plans can be generated effectively by a planner using domain-specific heuristic knowledge, and furthermore that the planner can use the sameknowledge as a goal-satisfying planner to solve correspondingoptimization problems.

Details

AAAI Conference 1994 Short Paper

Utility-Directed Planning

Mike Williamson

Classical AI planning has adopted a very narrow notion of plan quality, namely that a plan is good just in case it achieves a specified goal. Goals provide a valuable point of computational leverage: despite the fact that planning is intractable in the worst case, goal-satisfying planning algorithms can effectively solve classes of problems by using the goal to focus the search for a solution (using backward-chaining techniques), and by exploiting domain-specific heuristic knowledge to control search.

PDF Details

IJCAI Conference 1993 Conference Paper

Exploiting Domain Structure to Achieve Efficient Temporal Reasoning

Mike Williamson
Steve Hanks

We take temporal reasoning to be the problem of maintaining a set of constraints between time points and/or intervals, and responding to queries about the temporal separation between those individuals. Formal investigations of this constraint-satisfaction problem have demonstrated tradeoffs between the expressive power of the constraint language and the time required to answer queries. A simple constraint language admits an algorithm cubic in the number of individuals; allowing unrestricted disjunctive constraints makes the algorithm exponential. The problem is that applications of temporal reasoning, e. g. plan projection, need both disjunctive constraints and an algorithm much faster than 0 ( n 3 ). It is significant, however, that the nature of the constraints added by and the queries posed by an application tend to be structured and predictable. Our solution to the problem is to exploit the structure of the application domain to provide fast responses to typical queries. We consider the problem of plan projection under uncertainty and build a temporal representation—hierarchical interval constraints ( H I C ) — t h a t allows appropriate disjunctive constraints. We then implement the H I C representation in a temporal-reasoning module, and test it using a plan-projection application. A p p l y i n g the H I C module to a simple temporal projection problem shows orders-of-magnitude improvement over running the same projector using current implementations of domain-independent temporal constraint propagators.

PDF