University of Illinois Urbana-Champaign

Goal-directed qualitative reasoning with partial states

Decoste, Dennis Martin

This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.

Permalink

https://hdl.handle.net/2142/19612

Description

Title
Goal-directed qualitative reasoning with partial states
Author(s)
Decoste, Dennis Martin
Issue Date
1994
Doctoral Committee Chair(s)
Winseus, Marianne
Department of Study
Computer Science
Discipline
Computer Science
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
Computer Science
Language
eng
Abstract
  • This research explores the representational and computational complexities of qualitative reasoning about time-varying behavior. Traditional techniques employ qualitative simulation (QS) to compute envisionments (i.e. state-transition graphs) representing all possible behaviors. Unfortunately, QS exhaustively case-splits on all choices, regardless of specific task goals. It reasons with completely described states and explores every (ambiguous) future of each.
  • In this thesis we introduce a new representation, called sufficient discriminatory envisionments (SUDE's), which addresses these problems. SUDE's discriminate the possible behavior space by whether the goal is possible, impossible, or inevitable from each state in that space. Our techniques for generating SUDE's strive to reason with the smallest state descriptions which are sufficient for making these discriminations.
  • We present algorithms for generating SUDE's via a two-stage process. First, exhaustive regression sketches the space of possible paths between the initial and goal states. Second, we qualify these possible paths, identifying conditions under which the goal is impossible or inevitable and finding all possible transitions between these paths.
  • We formulate Nature's regression operators in terms of minimal chunks of causality, exploiting the causal, compositional nature of Qualitative Process Theory models. We integrate continuity-based and minimality-based theories of change to support discontinuous change due to actions and modelling simplifications.
  • We discuss our implementation of these techniques and our test examples in three domains, which we call ball-world, tank-world, and kitchen-world.
Type of Resource
text
Permalink
http://hdl.handle.net/2142/19612
Copyright and License Information
Copyright 1994 Decoste, Dennis Martin

Owning Collections

Graduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at Illinois
Dissertations and Theses - Computer Science
Dissertations and Theses from the Dept. of Computer Science