An efficient projected minimal conflict generator for projected prime implicate and implicant generation

Performing real-time reasoning on models of physical systems is essential in many situations, especially when human intervention is impossible. Since many deductive reasoning tasks take memory or time that is exponential in the number of variables that appear in the model, efforts need to be made to reduce the size of the models used online. The model can be reduced without sacrificing reasoning ability by targeting the model for a specific task, such as diagnosis or reconfiguration. A model may be reduced through model compilation, an offline process where relations and variables that have no bearing on the particular task are removed. This thesis introduces a novel approach to model compilation, through the generation of projected prime implicates and projected prime implicants. Prime implicates and prime implicants compactly represent the consequences of a logical theory. Projection eliminates model variables and their associated prime implicates or implicants that do not contribute to the particular task. This elimination process reduces the size and number of variables appearing in the model and therefore the complexity of the real-time reasoning problem. This thesis presents a minimal conflict generator that efficiently generates projected prime implicates and projected prime implicants. The projected minimal conflict generator uses a generate-and-test approach, in which the candidate generator finds potential minimal conflicts that are then accepted or rejected by the candidate tester. The candidate generator uses systematic search in combination with an iterative deepening algorithm, in order to reduce the space required by the algorithm to a space that is linear in the number of variables rather than exponential.

Department dc:contributor.department

Massachusetts Institute of Technology. Dept. of Aeronautics and Astronautics.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2004

Author dc:creator

• Elliott, Paul Harrison, 1979-

Advisor dc:contributor.advisor

• Brian C. Williams.

• Aeronautics and Astronautics.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/17766

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/17766