Julia Search Algorithms

A high-performance implementation of search algorithms in Julia for pathfinding for the vacuum world problem. Extensible to other domains.

Overview

This repository implements several search algorithms aiming to compare the speeds of solving numerous problems. Currently there is only vacuum world, where an agent (vacuum) must navigate through a grid world to collect all dirt particles while avoiding obstacles, but was built with extensibiltiy in mind. The project includes:

• A* Search: Classic informed search algorithm
• PA* Search: Naive implementation of a parallel A*
• K-Best-First Search (KBFS): Parallel extension of best-first search using batches
• Speculative-Parallel Best-First Search (SPBFS): Experimental Parallel best-first search built with the goal of parallellizing search in domains with very fast expansions

Features

• 🚀 Multi-threaded parallel search with K-Best-First Search and SPBFS
• 📊 Benchmark tools for performance analysis
• 🎯 Multiple search algorithms for comparison

Files Structure

Core Algorithm Files

• astar.jl - A* search implementation
• pastar.jl - Naive Parallel A*
• kbfs.jl - K-Best-First Search
• spbfs.jl - Speculative-Parallel Best-First Search

Problem Definition

• problem.jl - Abstract problem interface
• vacuum_world.jl - Vacuum world problem implementation with state representation

Entry Point

• main.jl - Main execution file with benchmarking examples

Data

• data/ - Contains test instances and world maps
  • world.dat, world2.dat - Sample world files
  • 100/ - Hierarchical test data with varying parameters

Problem Format

Vacuum World

Vacuum World files use the following format:

16 16          # Grid dimensions (rows cols)
Map:
################
#####  ### # # #
#     #       V#   # V = Vacuum (start position)
## #  #  #   # #   # # = Wall/obstacle
#         #    #   # * = Dirt (goal)
# #  # #  #  # #   #   = Empty space
#### #  # #  ###
#              #
#  # ####    # #
##### ##  #  # #
## # # # # ### #
#       #      #
##   #  #   #  #
##  #  # #  # ##
#*  #  # #  # ##   
################

Usage

Basic Example

# Load a world file
file = "data/100/0./10/5"
m::Matrix, n = VacuumWorld.parse_file(file)
problem = VacuumWorld.createVWProblem(m)

# Run A* search
res, expanded = astar(problem)
path = reconstruct_path(res)

# Run parallel K-Best-First Search
solution_kbfs = kbfs(start_state, problem, 8)  # 8 threads

Algorithm Details

A* Search

• Classic informed search using f(n) = g(n) + h(n)
• Euclidean distance heuristic to remaining dirt particles
• Optimal solution guarantee

PA* Search

• Same as A* but locking the open and closed lists to allow for parallel computation
• Not the same search order as A* could cause admissability issues

K-Best-First Search (KBFS)

• Parallel extension of best-first search
• Expands k nodes simultaneously using multiple threads
• Maintains optimality while improving performance
• Suffers from needing to wait for every expansion in the batch to proceed with the search

Speculative-Parallel Best-First Search (SPBFS)

• Uses worker threads to speculatively expand nodes in the open list
• Search order remains the same as A* so SPBFS has all the same admissibility guarantees
• Built to minimize or even remove blocking entirely from the parallel search

Dependencies

• Julia 1.6+
• DataStructures.jl
• BenchmarkTools.jl (for performance testing)

Installation

1. Clone the repository
2. Install Julia dependencies:

   using Pkg
   Pkg.add("DataStructures")
   Pkg.add("BenchmarkTools")