MAWA∗-a memory-bounded anytime heuristic-search algorithm

Area of Science:

• Artificial Intelligence
• Computer Science
• Heuristic Search Algorithms

Background:

• Heuristic search algorithms are crucial for solving complex problems in AI.
• Existing algorithms often face limitations in memory constraints or optimality.
• Anytime algorithms provide solutions that improve over time, but can be memory-intensive.

Purpose of the Study:

• To introduce a novel heuristic search algorithm, Memory-bounded Anytime Window A* (MAWA*).
• To address the challenge of restricted memory environments in AI search.
• To develop an algorithm that is complete, anytime, and memory-bounded.

Main Methods:

• MAWA* integrates the window-bounded anytime search framework of AWA*.
• It incorporates memory-bounded A*-like techniques to manage limited memory.
• Simplified and efficient tree-search versions of MAWA* are also developed.

Main Results:

• Experimental results demonstrate MAWA*'s effectiveness on the sliding-tile puzzle.
• MAWA* shows significant advantages over existing methods for the traveling salesman problem.
• The algorithm proves advantageous in memory-restricted scenarios.

Conclusions:

• MAWA* presents a significant advancement in heuristic search for AI.
• The algorithm offers a robust solution for problems with memory limitations.
• MAWA* provides a balance of completeness, anytime capability, and memory efficiency.