An efficient projected minimal conflict generator for projected prime implicate and implicant generation
Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Aeronautics and Astronautics, 2004.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2005
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/17766 |
| _version_ | 1826213429038284800 |
|---|---|
| author | Elliott, Paul Harrison, 1979- |
| author2 | Brian C. Williams. |
| author_facet | Brian C. Williams. Elliott, Paul Harrison, 1979- |
| author_sort | Elliott, Paul Harrison, 1979- |
| collection | MIT |
| description | Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Aeronautics and Astronautics, 2004. |
| first_indexed | 2024-09-23T15:48:57Z |
| format | Thesis |
| id | mit-1721.1/17766 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T15:48:57Z |
| publishDate | 2005 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/177662019-04-12T14:43:54Z An efficient projected minimal conflict generator for projected prime implicate and implicant generation Elliott, Paul Harrison, 1979- Brian C. Williams. Massachusetts Institute of Technology. Dept. of Aeronautics and Astronautics. Massachusetts Institute of Technology. Dept. of Aeronautics and Astronautics. Aeronautics and Astronautics. Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Aeronautics and Astronautics, 2004. Includes bibliographical references (p. 109-111). 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. (cont.) In order to make the algorithm more time efficient, the candidate generator prunes the search space using previously found implicants, as well as minimal conflicts, which identify the sub-spaces that contain no new minimal conflicts. The candidate tester identifies implicants of the model by testing for validity. The tester uses a clause-directed approach along with finite-domain variables to efficiently test for validity. Combined, these techniques allow the tester to test for validity without assigning a value to every variable. The conflict generator was evaluated on randomly generated models; problems in which models with 20 variables, 5 domain elements each, were projected onto 5 variables. All projected prime implicates were generated from models with 20 clauses within 2 seconds, and from models with 80 clauses within 13 seconds. by Paul Harrison Elliott. S.M. 2005-06-02T18:34:09Z 2005-06-02T18:34:09Z 2004 2004 Thesis http://hdl.handle.net/1721.1/17766 56526173 eng 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. http://dspace.mit.edu/handle/1721.1/7582 111 p. 4976969 bytes 4988252 bytes application/pdf application/pdf application/pdf Massachusetts Institute of Technology |
| spellingShingle | Aeronautics and Astronautics. Elliott, Paul Harrison, 1979- An efficient projected minimal conflict generator for projected prime implicate and implicant generation |
| title | An efficient projected minimal conflict generator for projected prime implicate and implicant generation |
| title_full | An efficient projected minimal conflict generator for projected prime implicate and implicant generation |
| title_fullStr | An efficient projected minimal conflict generator for projected prime implicate and implicant generation |
| title_full_unstemmed | An efficient projected minimal conflict generator for projected prime implicate and implicant generation |
| title_short | An efficient projected minimal conflict generator for projected prime implicate and implicant generation |
| title_sort | efficient projected minimal conflict generator for projected prime implicate and implicant generation |
| topic | Aeronautics and Astronautics. |
| url | http://hdl.handle.net/1721.1/17766 |
| work_keys_str_mv | AT elliottpaulharrison1979 anefficientprojectedminimalconflictgeneratorforprojectedprimeimplicateandimplicantgeneration AT elliottpaulharrison1979 efficientprojectedminimalconflictgeneratorforprojectedprimeimplicateandimplicantgeneration |