Granular State Space Search

dc.contributor.advisorYao, Yiyu
dc.contributor.authorLuo, Jigang
dc.contributor.committeememberZilles, Sandra
dc.contributor.committeememberYao, Jing Tao
dc.contributor.committeememberBenedicenti, Luigi
dc.contributor.externalexaminerPedrycz, Witold
dc.date.accessioned2014-10-17T17:45:56Z
dc.date.available2014-10-17T17:45:56Z
dc.date.issued2013-08
dc.descriptionA Thesis Submitted to the Faculty of Graduate Studies and Research In Partial Fulfillment of the Requirements For the Degree of Doctor of Philosophy in Computer Science, University of Regina. xxi, 206 p.en_US
dc.description.abstractGranular computing is an emerging field of study that derives general principles and models from a wide range of disciplines and uses these principles and models to solve problems. One basic structure in granular computing is a granular struc- ture, which is a hierarchical multi-level structure made of granules. The granular structure implies important ways to problem solving such as hierarchical problem solving and top-down progressive processing. These ways can be used in artifi- cial intelligence. This thesis focuses on how to use granular computing to solve problems in state space search. State space search is a classical approach to problem solving in artificial in- telligence. A problem solving process is modeled by a state space and a search for a path from the start state to a goal state. One promising method for state space search is hierarchical state space search, which creates abstraction hierar- chies as representations of state spaces and uses a procedure, called refinement procedure, to find solutions with the help of abstraction hierarchies. Good ab- straction hierarchies and refinement procedures can speed up state space search while bad abstraction hierarchies and refinement procedures can slow down state space search. This thesis proposes granular computing based methods that can construct good abstraction hierarchies quickly and a new refinement procedure. We first identify two main issues in hierarchical problem solving, namely, back-tracking and incompleteness. Backtracking degrades the efficiency of state space search while incompleteness decreases the effectiveness and reliability. Based on the two issues, we propose a concept of completeness degree and give criteria for evaluating good abstraction hierarchies. We argue that a good abstraction hierarchy should have few backtrackings and a high completeness degree. To apply granular computing in state space search, we propose two new con- cepts, called an attributed graph and a granulated attributed graph, respectively. An attributed graph can be mapped into a state space and a granulated at- tributed graph can be mapped into an abstraction. We analyze characteristics of attributed graphs and granulated attributed graphs and identify an important property of granulated attributed graphs known as inner connectivity. We argue that if a granulated attributed graph satisfies the inner connectivity property, the mapped abstraction hierarchy is free of backtrackings and incompleteness. Based on the attributed graphs and granulated attributed graphs, we propose a new genre of methods for state space search called granular state space search. Granular state space search can create good abstraction hierarchies that have fewer backtrackings and a higher completeness degree. Furthermore, we improve granular state space search by applying the machine learning techniques so that good abstraction hierarchies can be generated fast. Finally, we compare our granular state space search with existing hierarchical state space search methods and demonstrate the superiority of granular state space search by experimental results.en_US
dc.description.authorstatusStudenten
dc.description.peerreviewyesen
dc.description.uriA Thesis Submitted to the Faculty of Graduate Studies and Research In Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy *, University of Regina. *, * p.en
dc.identifier.tcnumberTC-SRU-5416
dc.identifier.thesisurlhttp://ourspace.uregina.ca/bitstream/handle/10294/5416/Luo_Jigang_200283167_PhD_CS_Spring2014.pdf
dc.identifier.urihttps://hdl.handle.net/10294/5416
dc.language.isoenen_US
dc.publisherFaculty of Graduate Studies and Research, University of Reginaen_US
dc.titleGranular State Space Searchen_US
dc.typeThesisen
thesis.degree.departmentDepartment of Computer Scienceen_US
thesis.degree.disciplineComputer Scienceen_US
thesis.degree.grantorUniversity of Reginaen
thesis.degree.levelDoctoralen
thesis.degree.nameDoctor of Philosophy (PhD)en_US
Files
Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
Luo_Jigang_200283167_PhD_CS_Spring2014.pdf
Size:
840.84 KB
Format:
Adobe Portable Document Format
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
2.22 KB
Format:
Item-specific license agreed upon to submission
Description: