planner.avclPlan.search

Class BestFirstSearchWorldState

java.lang.Object

planner.aStarPlan.WorldState

planner.avclPlan.search.SearchWorldState

planner.avclPlan.search.BestFirstSearchWorldState

public class BestFirstSearchWorldState
extends SearchWorldState

Represents the state of the world at various stages of a search. Conditions consist of "visited" conditions where the search is complete when all of the locations have been visited. The estimate of remaining cost is the track spacing times the number of unvisited locations. Incurred cost so far is the distance traveled on all of the legs so far plus the track spacing times the number of legs (this biases the searh towards patterns with fewer long legs rather than numerous short legs)

Version:

$Revision: 1.3 $

Author:

dtdavis

Contact: Don Brutzman (web.nps.navy.mil/~brutzman) brutzman@nps.navy.mil

Field Summary

Fields inherited from class planner.avclPlan.search.SearchWorldState

buffer, FORTY_FIVE_DEGREES, HEADINGS, NINETY_DEGREES, ONE_FIFTY_DEGREES, ONE_THIRTY_FIVE_DEGREES, ONE_TWENTY_DEGREES, pointFocus, searchArea, searchPoints, SIXTY_DEGREES, THIRTY_DEGREES, THREE_FIFTEEN_DEGREES, THREE_HUNDRED_DEGREES, THREE_THIRTY_DEGREES, trackLengthMultiple, trackSpacing, TWO_FORTY_DEGREES, TWO_SEVENTY_DEGREES, TWO_TEN_DEGREES, TWO_TWENTY_FIVE_DEGREES, vehiclePosition, vehiclePsi

Constructor Summary

Constructors

Modifier	Constructor and Description
protected	BestFirstSearchWorldState() Creates a new instance of BestFirstSearchWorldState
protected	BestFirstSearchWorldState(List<double[]> searchPoints, GeoArea searchArea, double spacing, double[] position) Creates a new instance of BestFirstSearchWorldState
protected	BestFirstSearchWorldState(List<double[]> searchPoints, GeoArea searchArea, double spacing, double[] position, boolean pointFocus) Creates a new instance of BestFirstSearchWorldState
protected	BestFirstSearchWorldState(List<double[]> searchPoints, GeoArea searchArea, List<double[]> complete, double spacing, double[] position) Creates a new instance of BestFirstSearchWorldState
protected	BestFirstSearchWorldState(List<double[]> searchPoints, GeoArea searchArea, List<double[]> complete, double spacing, double[] position, boolean pointFocus) Creates a new instance of BestFirstSearchWorldState

Method Summary

Modifier and Type	Method and Description
WorldState	computeStepEffect(PlanStep step) Computes the effect of a plan step on the world state conditions
List<SearchPlanStep>	possibleSteps() Returns an ArrayList containing all steps that are possible from the current state
double	worldStateDistance(WorldState candidate) Compares this state with another to measure how different they are in order to provide an estimate of how much effort will be required to go from this state to the candidate state.

Methods inherited from class planner.avclPlan.search.SearchWorldState

addVisited, computePsi, generateConditions, visited

Methods inherited from class planner.aStarPlan.WorldState

addCondition, addCondition, getCondition, hasCondition, match, numberOfConditions, toString

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

BestFirstSearchWorldState

protected BestFirstSearchWorldState()

Creates a new instance of BestFirstSearchWorldState

BestFirstSearchWorldState

protected BestFirstSearchWorldState(List<double[]> searchPoints,
                                    GeoArea searchArea,
                                    List<double[]> complete,
                                    double spacing,
                                    double[] position)

Creates a new instance of BestFirstSearchWorldState

Parameters:

searchPoints - List of points that are to be visited during the search

searchArea - Geographic area that the planner is to devise a search pattern for

complete - List of points that have been visited to date

spacing - track spacing to be used during the search

position - double[2] containing the current (x, y) position of the vehicle

BestFirstSearchWorldState

protected BestFirstSearchWorldState(List<double[]> searchPoints,
                                    GeoArea searchArea,
                                    double spacing,
                                    double[] position)

Creates a new instance of BestFirstSearchWorldState

Parameters:

searchPoints - List of points that are to be visited during the search

searchArea - Geographic area that the planner is to devise a search pattern for

spacing - track spacing to be used during the search

position - double[2] containing the current (x, y) position of the vehicle

BestFirstSearchWorldState

protected BestFirstSearchWorldState(List<double[]> searchPoints,
                                    GeoArea searchArea,
                                    List<double[]> complete,
                                    double spacing,
                                    double[] position,
                                    boolean pointFocus)

Creates a new instance of BestFirstSearchWorldState

Parameters:

searchPoints - List of points that are to be visited during the search

searchArea - Geographic area that the planner is to devise a search pattern for

complete - List of points that have been visited to date

spacing - track spacing to be used during the search

position - double[2] containing the current (x, y) position of the vehicle

pointFocus -

BestFirstSearchWorldState

protected BestFirstSearchWorldState(List<double[]> searchPoints,
                                    GeoArea searchArea,
                                    double spacing,
                                    double[] position,
                                    boolean pointFocus)

Creates a new instance of BestFirstSearchWorldState

Parameters:

searchPoints - List of points that are to be visited during the search

searchArea - Geographic area that the planner is to devise a search pattern for

spacing - track spacing to be used during the search

position - double[2] containing the current (x, y) position of the vehicle

pointFocus -

Method Detail

computeStepEffect

public WorldState computeStepEffect(PlanStep step)

Computes the effect of a plan step on the world state conditions

Overrides:

computeStepEffect in class SearchWorldState

Parameters:

step - PlanStep object.

Returns:

the effect of a plan step on the world state conditions.

worldStateDistance

public double worldStateDistance(WorldState candidate)

Compares this state with another to measure how different they are in order to provide an estimate of how much effort will be required to go from this state to the candidate state. This particular metric is based on the number of conditions present in the candidate that are not present in the current state and returns the number * trackSpacing * 10. This heavily biases the A* search towards covering the points in as few steps as possible, as opposed to the shortest distance covered.

Overrides:

worldStateDistance in class SearchWorldState

Parameters:

candidate - WorldState object.

Returns:

the value of double of comparison this state with another.

possibleSteps

public List<SearchPlanStep> possibleSteps()

Returns an ArrayList containing all steps that are possible from the current state

Overrides:

possibleSteps in class SearchWorldState

Returns:

an ArrayList containing all steps.