• Login
    View Item 
    •   SMARTech Home
    • Georgia Tech Theses and Dissertations
    • Georgia Tech Theses and Dissertations
    • View Item
    •   SMARTech Home
    • Georgia Tech Theses and Dissertations
    • Georgia Tech Theses and Dissertations
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Speeding Up the Convergence of Online Heuristic Search and Scaling Up Offline Heuristic Search

    Thumbnail
    View/Open
    furcy_david_a_200412_phd.pdf (2.121Mb)
    Date
    2004-11-25
    Author
    Furcy, David Andre
    Metadata
    Show full item record
    Abstract
    The most popular methods for solving the shortest-path problem in Artificial Intelligence are heuristic search algorithms. The main contributions of this research are new heuristic search algorithms that are either faster or scale up to larger problems than existing algorithms. Our contributions apply to both online and offline tasks. For online tasks, existing real-time heuristic search algorithms learn better informed heuristic values and in some cases eventually converge to a shortest path by repeatedly executing the action leading to a successor state with a minimum cost-to-goal estimate. In contrast, we claim that real-time heuristic search converges faster to a shortest path when it always selects an action leading to a state with a minimum f-value, where the f-value of a state is an estimate of the cost of a shortest path from start to goal via the state, just like in the offline A* search algorithm. We support this claim by implementing this new non-trivial action-selection rule in FALCONS and by showing empirically that FALCONS significantly reduces the number of actions to convergence of a state-of-the-art real-time search algorithm. For offline tasks, we improve on two existing ways of scaling up best-first search to larger problems. First, it is known that the WA* algorithm (a greedy variant of A*) solves larger problems when it is either diversified (i.e., when it performs expansions in parallel) or committed (i.e., when it chooses the state to expand next among a fixed-size subset of the set of generated but unexpanded states). We claim that WA* solves even larger problems when it is enhanced with both diversity and commitment. We support this claim with our MSC-KWA* algorithm. Second, it is known that breadth-first search solves larger problems when it prunes unpromising states, resulting in the beam search algorithm. We claim that beam search quickly solves even larger problems when it is enhanced with backtracking based on limited discrepancy search. We support this claim with our BULB algorithm. We show that both MSC-KWA* and BULB scale up to larger problems than several state-of-the-art offline search algorithms in three standard benchmark domains. Finally, we present an anytime variant of BULB and apply it to the multiple sequence alignment problem in biology.
    URI
    http://hdl.handle.net/1853/4855
    Collections
    • College of Computing Theses and Dissertations [1156]
    • Georgia Tech Theses and Dissertations [23403]

    Related items

    Showing items related by title, author, creator and subject.

    • CrossSearch at the Crossroads: Implementing Federated Searching at Georgia Tech 

      Critz, Lori; Hansard, Larry; Leach, Guy (Georgia Institute of Technology, 2010-05-20)
      The implementation of CrossSearch, at the Georgia Tech Library, was a team effort between technical services and public services personnel to blend vendor-based (MetaLib) and open source (Xerxes) software into a customized ...
    • Part I. The relative reactivities of common nucleophilic reagents toward difluoromethylene : a search for bifunctional catalysis ; Part II. the reactions of the methylene halides with alkoxides in alcoholic solvents : a search for an [alpha]-elimination mechanism and methylene intermediates ; Part III. The reaction of methylmagnesium bromide with benzophenone : the mechanism of the Grignard reaction 

      Duke, Roy Burt (Georgia Institute of Technology, 1967-05)
    • Contextualized web search: query-dependent ranking and social media search 

      Bian, Jiang (Georgia Institute of Technology, 2010-09-29)
      Due to the information explosion on the Internet, effective information search techniques are required to retrieve the desired information from the Web. Based on much analysis on users' search intention and the variant ...

    Browse

    All of SMARTechCommunities & CollectionsDatesAuthorsTitlesSubjectsTypesThis CollectionDatesAuthorsTitlesSubjectsTypes

    My SMARTech

    Login

    Statistics

    View Usage StatisticsView Google Analytics Statistics
    facebook instagram twitter youtube
    • My Account
    • Contact us
    • Directory
    • Campus Map
    • Support/Give
    • Library Accessibility
      • About SMARTech
      • SMARTech Terms of Use
    Georgia Tech Library266 4th Street NW, Atlanta, GA 30332
    404.894.4500
    • Emergency Information
    • Legal and Privacy Information
    • Human Trafficking Notice
    • Accessibility
    • Accountability
    • Accreditation
    • Employment
    © 2020 Georgia Institute of Technology