HeuristicSearch - nnrg/opennero GitHub Wiki

Often, we know something about which general direction to search a graph. Such an intuition is called a heuristic, and a search algorithm can find the shortest path faster than it can in the case of brute force search.

The most prominent heuristic search method is the A* Search Algorithm (see section 3.5.2 of AIMA). A* is a way to sift through a graph or a tree in order to find the shortest path through the goal. When given an appropriate heuristic the algorithm will try to expand the most promising branches of the graph first. It is routinely used for pathfinding in games, and has many extensions and modifications for dealing with various applications.

Click to play video.

1. Start OpenNERO
2. Select the Search Experiment
3. Click on the Single Agent A* agent and run to completion
4. Click on the Teleporting A* agent and run to completion
5. Click on the Front A* agent and run to completion

In OpenNERO, there are three different visualizations of this algorithm in the MazeMod. All of them start at one corner of the maze and try to find the goal (red cube) at the opposite corner.

To start this visualization, start OpenNERO and click on the Maze button. After the maze loads, click on the Single Agent A* button.

This visualization shows what would happen if the agent was a physical robot that has to move in order to get to and expand the next node in the graph. As the agent runs around the maze, it marks the cells with three different kinds of markers:

• BLUE - expanded node
• YELLOW - next node to expand
• GREEN - generated node (that may be expanded later)

To start this visualization, start OpenNERO and click on the Maze button. After the maze loads, click on the Teleporting A* button.

In this case, the robot can teleport from its current state to the yellow node, i.e. the one that needs to be expanded next. Since A* does not actually visit the states between them, this is a more accurate way to visualize the steps that the algorithm takes. The blue, yellow, and green markers have the same meaning as in single-agent A*.

To start this visualization, start OpenNERO and click on the Maze button. After the maze loads, click on the Front A* button.

The green nodes constitute the search frontier in A*, and the search proceeds simply by expanding those nodes in the frontier that seem most promising, without actually having to run or teleport control to them. This idea is visualized by 'cloning' copies of the search agent and leaving them waiting at the green nodes. The blue, yellow, and green markers have the same meaning as in single-agent A*.

The A* agent is implemented in mods/Maze/agent.py. The three variants are:

• AStarSearchAgent
• TeleportingAStarSearchAgent
• FrontAStarSearchAgent

See SystemOverview for general information on how OpenNERO agents work.

The world of search doesn't end here! For example, for A*, there are a many variants that have been adapted to particular types of search problems. Among some of the most interesting are:

• D* for cases when the cost function can change while the agent is searching for a route (this search strategy is the basis for prototype systems tested on Mars rovers Opportunity and Spirit and the navigation system of the winning entry in the DARPA Urban Challenge).
• IDA* - iterative deepening A* - for large graphs where memory is a limiting factor

We encourage you to implement one of these other variants as a programming assignment.