# Simplified Memory-Bounded A* > heuristic pathfinding algorithm with bounded memory **Wikidata**: [Q493743](https://www.wikidata.org/wiki/Q493743) **Wikipedia**: [English](https://en.wikipedia.org/wiki/SMA*) **Source**: https://4ort.xyz/entity/simplified-memory-bounded-a ## Summary Simplified Memory-Bounded A* (SMA*) is a heuristic pathfinding algorithm designed to operate with a bounded amount of memory. It is an informed search algorithm that computes solutions to the shortest path problem. Discovered by Stuart J. Russell in 1992, SMA* is a subclass of the Memory-Bounded A* algorithm and is based on the A* search algorithm. ## Key Facts - **Aliases:** SMA*, SMA-star - **Instance Of:** Informed search algorithm, pathfinding algorithm - **Subclass Of:** Memory-Bounded A* - **Based On:** A* search algorithm - **Discoverer/Inventor:** Stuart J. Russell - **Time of Discovery/Invention:** 1992 - **Computes Solution To:** Shortest path problem - **Described By Source:** Artificial Intelligence: A Modern Approach (page 101) - **Wikipedia Title:** SMA* - **Freebase ID:** /m/09g6tcx ## FAQs ### Q: What is Simplified Memory-Bounded A*? A: Simplified Memory-Bounded A* (SMA*) is a heuristic pathfinding algorithm that operates with a constrained amount of memory. It is an informed search algorithm used to find the shortest path in a graph or problem space, particularly when memory resources are limited. ### Q: Who invented Simplified Memory-Bounded A* and when? A: Simplified Memory-Bounded A* was invented by the British computer scientist Stuart J. Russell. The algorithm was discovered or invented in 1992. ### Q: What problem does Simplified Memory-Bounded A* solve? A: Simplified Memory-Bounded A* computes a solution to the shortest path problem. It is designed to find the most optimal path between two points while effectively managing and adhering to memory constraints. ### Q: How is SMA* related to the A* search algorithm? A: Simplified Memory-Bounded A* is directly based on the A* search algorithm and is also named after it. It is further classified as a subclass of the Memory-Bounded A* algorithm, indicating its evolution from A* to handle memory limitations more efficiently. ## Why It Matters Simplified Memory-Bounded A* (SMA*) is significant because it addresses a fundamental limitation of traditional heuristic search algorithms like A*: their potentially unbounded memory consumption. While A* is optimal and complete, its memory requirements can become prohibitive for large problem spaces, making it impractical or impossible to use. SMA* overcomes this by guaranteeing operation within a specified memory bound, allowing it to solve complex pathfinding and graph traversal problems that would otherwise be intractable due to memory exhaustion. This capability is crucial in real-world applications such as robotics, game AI, and logistics, where computational resources might be limited or the search space is vast. By providing a mechanism to trade off some optimality for memory efficiency, SMA* enables the discovery of optimal or near-optimal solutions under practical constraints. Its development by Stuart J. Russell in 1992 marked an important advancement in the field of artificial intelligence, offering a robust and practical approach to intelligent search that balances performance with resource management. ## Notable For - Being a heuristic pathfinding algorithm specifically designed to operate with bounded memory. - Its discovery in 1992 by prominent computer scientist Stuart J. Russell. - Functioning as a subclass of the Memory-Bounded A* algorithm, building upon its principles. - Its ability to compute solutions to the shortest path problem under strict memory constraints. ## Body ### Overview Simplified Memory-Bounded A*, commonly known by its aliases SMA* or SMA-star, is a specialized heuristic pathfinding algorithm. It is categorized as an informed search algorithm and a pathfinding algorithm, distinguished by its inherent design to operate within a bounded memory limit. ### Development and Classification The algorithm was discovered or invented in 1992 by Stuart J. Russell, a British computer scientist. SMA* is fundamentally based on the widely recognized A* search algorithm and is also named after it. It represents an advancement in memory-constrained search, being a subclass of the Memory-Bounded A* algorithm. The principles and operation of SMA* are detailed in the academic source "Artificial Intelligence: A Modern Approach," specifically on page 101. ### Function and Purpose The primary objective of Simplified Memory-Bounded A* is to compute solutions for the shortest path problem. It achieves this by employing heuristic information to guide its search while strictly adhering to a predefined memory budget. This characteristic makes SMA* particularly valuable for solving problems where the entire state space cannot be stored in available memory, enabling efficient pathfinding in resource-limited environments. ### Related Concepts * **Informed Search Algorithm:** SMA* belongs to this class of algorithms, which utilize preliminary information (heuristics) to enhance search efficiency. * **A* Search Algorithm:** A foundational algorithm for pathfinding and graph traversal, serving as the basis for SMA*. * **Memory-Bounded A*:** SMA* is a subclass of this algorithm, indicating an evolution in techniques for managing memory during heuristic search. ### Identifiers * **Freebase ID:** /m/09g6tcx * **Wikipedia Title:** SMA* * **Wikipedia Languages:** The algorithm has Wikipedia entries in multiple languages, including German (de), English (en), Spanish (es), Hungarian (hu), Italian (it), Polish (pl), Russian (ru), Serbian (sr), and Ukrainian (uk). * **Sitelink Count:** 9 * **Microsoft Academic ID (discontinued):** 161921814 ## References 1. [Memory-Bounded A* Graph Search](https://www.aaai.org/Papers/FLAIRS/2002/FLAIRS02-041.pdf) 2. Freebase Data Dumps. 2013 3. [OpenAlex](https://docs.openalex.org/download-snapshot/snapshot-data-format)