{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/19170"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/19170","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Base selection in analogical planning","abstract":"This thesis addresses the problem of efficiently selecting base cases for problem-solving analogies. The base selection task is one of the most severe limitations in current analogical reasoning systems, because of the complexity of the task and the ill-defined nature of the problem. This research addresses the complexity issue by designing a parallel base selection algorithm and verifying the efficiency of the design through empirical and theoretical analyses. By defining a formal model of the base selection task and analyzing the expected performance, the research provides a sound specification of the base selection process in analogical planning. This work also extends analogical planning by merging multiple similar base cases when no single base case provides a sufficiently accurate analogy. These ideas are implemented in the A scNAGRAM analogical planning system. A scNAGRAM solves novel problems by constructing analogical plans. Given a problem goal, A scNAGRAM finds a similar goal in a database of solved plans from which a solution can be derived. A scNAGRAM expresses plans as graphs and uses a graph matching algorithm to identify potential analogies and form the mapping between a base problem and the target problem. A scNAGRAM takes advantage of the massively parallel architecture of the Connection Machine to perform base selection with a computational complexity that is sublinear in the size of the base graphs. By analyzing the analogical planning process, extending the applicability of the method, and efficiently implementing the algorithms, this research offers a valuable step toward the automation of analogical planning.","abstract_html":"This thesis addresses the problem of efficiently selecting base cases for problem-solving analogies. The base selection task is one of the most severe limitations in current analogical reasoning systems, because of the complexity of the task and the ill-defined nature of the problem. This research addresses the complexity issue by designing a parallel base selection algorithm and verifying the efficiency of the design through empirical and theoretical analyses. By defining a formal model of the base selection task and analyzing the expected performance, the research provides a sound specification of the base selection process in analogical planning. This work also extends analogical planning by merging multiple similar base cases when no single base case provides a sufficiently accurate analogy. These ideas are implemented in the A scNAGRAM analogical planning system. A scNAGRAM solves novel problems by constructing analogical plans. Given a problem goal, A scNAGRAM finds a similar goal in a database of solved plans from which a solution can be derived. A scNAGRAM expresses plans as graphs and uses a graph matching algorithm to identify potential analogies and form the mapping between a base problem and the target problem. A scNAGRAM takes advantage of the massively parallel architecture of the Connection Machine to perform base selection with a computational complexity that is sublinear in the size of the base graphs. By analyzing the analogical planning process, extending the applicability of the method, and efficiently implementing the algorithms, this research offers a valuable step toward the automation of analogical planning.","abstract_has_math":false,"creators":["Cook, Diane Joyce"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Stepp, Robert E."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011-05-07T11:59:05Z","date_published":"2011-05-07T11:59:05Z","updated_at":"2026-07-22T22:25:12Z","subjects":["Artificial Intelligence","Computer Science"],"languages":["eng"],"rights":["Copyright 1990 Cook, Diane Joyce"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9114212","(UMI)AAI9114212"],"render_values":[{"text":"AAI9114212","href":null,"code":true},{"text":"(UMI)AAI9114212","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/19170","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Stepp, Robert E."]},{"key":"dc:creator","label":"Author","values":["Cook, Diane Joyce"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2011-05-07T11:59:05Z","10000-01-01","1990"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Artificial Intelligence","Computer Science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 1990 Cook, Diane Joyce"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9114212","(UMI)AAI9114212","http://hdl.handle.net/2142/19170"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["This thesis addresses the problem of efficiently selecting base cases for problem-solving analogies. The base selection task is one of the most severe limitations in current analogical reasoning systems, because of the complexity of the task and the ill-defined nature of the problem. This research addresses the complexity issue by designing a parallel base selection algorithm and verifying the efficiency of the design through empirical and theoretical analyses. By defining a formal model of the base selection task and analyzing the expected performance, the research provides a sound specification of the base selection process in analogical planning. This work also extends analogical planning by merging multiple similar base cases when no single base case provides a sufficiently accurate analogy. These ideas are implemented in the A scNAGRAM analogical planning system. A scNAGRAM solves novel problems by constructing analogical plans. Given a problem goal, A scNAGRAM finds a similar goal in a database of solved plans from which a solution can be derived. A scNAGRAM expresses plans as graphs and uses a graph matching algorithm to identify potential analogies and form the mapping between a base problem and the target problem. A scNAGRAM takes advantage of the massively parallel architecture of the Connection Machine to perform base selection with a computational complexity that is sublinear in the size of the base graphs. By analyzing the analogical planning process, extending the applicability of the method, and efficiently implementing the algorithms, this research offers a valuable step toward the automation of analogical planning.","Made available in DSpace on 2011-05-07T11:59:05Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9114212.pdf: 7353479 bytes, checksum: 1802e90613111f5fad68f3cfcddbdca5 (MD5) Previous issue date: 1990","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:35:08Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:13:43-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","ETDs are only available to UIUC Users without author permission","U of I Only"]},{"key":"dc:title","label":"Title","values":["Base selection in analogical planning"]}]}],"canonical_facts":{"dc:contributor":["Stepp, Robert E."],"dc:creator":["Cook, Diane Joyce"],"dc:date":["2011-05-07T11:59:05Z","10000-01-01","1990"],"dc:description":["This thesis addresses the problem of efficiently selecting base cases for problem-solving analogies. The base selection task is one of the most severe limitations in current analogical reasoning systems, because of the complexity of the task and the ill-defined nature of the problem. This research addresses the complexity issue by designing a parallel base selection algorithm and verifying the efficiency of the design through empirical and theoretical analyses. By defining a formal model of the base selection task and analyzing the expected performance, the research provides a sound specification of the base selection process in analogical planning. This work also extends analogical planning by merging multiple similar base cases when no single base case provides a sufficiently accurate analogy. These ideas are implemented in the A scNAGRAM analogical planning system. A scNAGRAM solves novel problems by constructing analogical plans. Given a problem goal, A scNAGRAM finds a similar goal in a database of solved plans from which a solution can be derived. A scNAGRAM expresses plans as graphs and uses a graph matching algorithm to identify potential analogies and form the mapping between a base problem and the target problem. A scNAGRAM takes advantage of the massively parallel architecture of the Connection Machine to perform base selection with a computational complexity that is sublinear in the size of the base graphs. By analyzing the analogical planning process, extending the applicability of the method, and efficiently implementing the algorithms, this research offers a valuable step toward the automation of analogical planning.","Made available in DSpace on 2011-05-07T11:59:05Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9114212.pdf: 7353479 bytes, checksum: 1802e90613111f5fad68f3cfcddbdca5 (MD5) Previous issue date: 1990","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:35:08Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:13:43-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","ETDs are only available to UIUC Users without author permission","U of I Only"],"dc:identifier":["AAI9114212","(UMI)AAI9114212","http://hdl.handle.net/2142/19170"],"dc:language":["eng"],"dc:rights":["Copyright 1990 Cook, Diane Joyce"],"dc:subject":["Artificial Intelligence","Computer Science"],"dc:title":["Base selection in analogical planning"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:12Z"}