• Login
    View Item 
    •   oURspace Home
    • Faculty of Graduate Studies and Research
    • Theses and Dissertations
    • Doctoral Theses and Dissertations
    • View Item
    •   oURspace Home
    • Faculty of Graduate Studies and Research
    • Theses and Dissertations
    • Doctoral Theses and Dissertations
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Granular State Space Search

    Thumbnail
    View/Open
    Luo_Jigang_200283167_PhD_CS_Spring2014.pdf (840.8Kb)
    Date
    2013-08
    Author
    Luo, Jigang
    Metadata
    Show full item record
    URI
    http://hdl.handle.net/10294/5416
    Abstract
    Granular 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.
    Collections
    • Doctoral Theses and Dissertations

    Copyright © 2020 University of Regina
    Contact Us | Send Feedback | Archer Library | University of Regina

     

     

    Browse

    All of oURspaceCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    LoginRegister

    About

    About oURspacePoliciesLicensesContacts

    Statistics

    View Usage Statistics

    Copyright © 2020 University of Regina
    Contact Us | Send Feedback | Archer Library | University of Regina