public class

ADStarForward

extends Algorithm<A, S, N extends Node<A, S, N>>
java.lang.Object
   ↳ es.usc.citius.hipster.algorithm.Algorithm<A, S, N extends es.usc.citius.hipster.model.Node<A, S, N>>
     ↳ es.usc.citius.hipster.algorithm.ADStarForward<A, S, C extends java.lang.Comparable<C>, N extends es.usc.citius.hipster.model.ADStarNode<A, S, C, N>>

Class Overview

Iterative implementation of the forward Anytime Dynamic A* (AD*-f) search algorithm.

AD* is an anytime, dynamic search algorithm. It is able to obtain suboptimal-bounded solutions, tuning the quality of the solution based on the available search time (this is done by adjusting the heuristic inflation parameter, epsilon). This algorithm is executed iteratively improving the quality of the solution and reusing previous search efforts. The algorithm also takes into account the changes produced over the graph arc costs to incrementally repair the previous solution. AD* provides anytime results and an efficient way to solve dynamic search problems.

This is the forward implementation of AD*, the algorithm starts exploring the state space from the beginning state and trying to reach a goal state (or multiple ones).

Reference:
Maxim Likhachev, David Ferguson, Geoffrey Gordon, Anthony (Tony) Stentz, and Sebastian Thrun, "Anytime Dynamic A*: An Anytime, Replanning Algorithm" Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS), June, 2005.

Summary

Nested Classes
class ADStarForward.Iterator Internal iterator that implements all the logic of the A* search  
Fields
protected S begin
protected ADStarNodeExpander<A, S, C extends Comparable<C>, N extends ADStarNode<A, S, C, N>> expander
protected Collection<S> goals
Public Constructors
ADStarForward(S begin, S goal, ADStarNodeExpander<A, S, C, N> expander)
Create an instance of the algorithm with a begin, a goal and a component to expand new nodes from the current one.
ADStarForward(S begin, Collection<S> goals, ADStarNodeExpander<A, S, C, N> expander)
Create an instance of the algorithm with a begin, multiple goals and a component to expand new nodes from the current one.
Public Methods
Iterator iterator()
[Expand]
Inherited Methods
From class es.usc.citius.hipster.algorithm.Algorithm
From class java.lang.Object
From interface java.lang.Iterable

Fields

protected S begin

protected ADStarNodeExpander<A, S, C extends Comparable<C>, N extends ADStarNode<A, S, C, N>> expander

protected Collection<S> goals

Public Constructors

public ADStarForward (S begin, S goal, ADStarNodeExpander<A, S, C, N> expander)

Create an instance of the algorithm with a begin, a goal and a component to expand new nodes from the current one.

Parameters
begin begin state
goal goal state
expander component which generates new nodes from the current

public ADStarForward (S begin, Collection<S> goals, ADStarNodeExpander<A, S, C, N> expander)

Create an instance of the algorithm with a begin, multiple goals and a component to expand new nodes from the current one.

Parameters
begin begin state
goals collection of goal states
expander component which generates new nodes from the current

Public Methods

public Iterator iterator ()