Best-First Heuristic Search for Multicore Machines

Abstract

To harness modern multicore processors, it is imperative to develop parallel versions of fundamental algorithms. In this paper, we compare different approaches to parallel best-first search in a shared-memory setting. We present a new method, PBNF, that uses abstraction to partition the state space and to detect duplicate states without requiring frequent locking. PBNF allows speculative expansions when necessary to keep threads busy. We identify and fix potential livelock conditions in our approach, proving its correctness using temporal logic. Our approach is general, allowing it to extend easily to suboptimal and anytime heuristic search. In an empirical comparison on STRIPS planning, grid pathfinding, and sliding tile puzzle problems using 8-core machines, we show that A*, weighted A* and Anytime weighted A* implemented using PBNF yield faster search than improved versions of previous parallel search proposals.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 2010
Accession Number
ADA536972

Entities

People

  • Ethan Burns
  • Rong Zhou
  • Sofia Lemons
  • Wheeler Ruml

Organizations

  • University of New Hampshire

Tags

Communities of Interest

  • Energy and Power Technologies
  • Space

DTIC Thesaurus Topics

  • Algorithms
  • Artificial Intelligence
  • Computer Science
  • Computers
  • Cost Models
  • Graphics Processing Unit
  • Hash Tables
  • Intelligent Systems
  • Language
  • Mathematics
  • Motion Planning
  • Operating Systems
  • Parallel Computing
  • Parallel Processing
  • Scheduling (Production)
  • Software Development
  • Systems Science

Fields of Study

  • Computer science

Readers

  • Economics
  • Operations Research
  • Parallel and Distributed Computing.

Technology Areas

  • Space