planner.avclPlan.search

Class TSPSearchPlanner

java.lang.Object

planner.avclPlan.search.SearchTrackPlanner

planner.avclPlan.search.TrackedSearchPlanner

planner.avclPlan.search.TSPSearchPlanner

All Implemented Interfaces:

Runnable

Direct Known Subclasses:

AnnealedTSPSearchPlanner

public class TSPSearchPlanner
extends TrackedSearchPlanner
implements Runnable

Class that will use iterative improvement to a traveling salesman problem solution to compute a series of waypoints that will search a geographic area with a prescribed probability of detection

Author:

dtdavis

Field Summary

Fields

Modifier and Type	Field and Description
protected static double	COS60
protected double[][]	searchSequence
protected static double	SIN60
static double	SIXTY_DEGREES
static double	THIRTY_DEGREES

Fields inherited from class planner.avclPlan.search.TrackedSearchPlanner

pd, sweepWidth, trackSpacing

Fields inherited from class planner.avclPlan.search.SearchTrackPlanner

plan, searchArea, startPoint

Constructor Summary

Constructors

Constructor and Description
TSPSearchPlanner(GeoArea searchArea, double S, double PD, double[] startPosit) Creates a new instance of TSPSearchPlanner
TSPSearchPlanner(GeoArea searchArea, double S, double PD, double[] startPosit, boolean pointFocus) Creates a new instance of TSPSearchPlanner

Method Summary

Methods

Modifier and Type	Method and Description
protected List<double[]>	computeVisitPoints() Computes a set of points that blanket the search area.
double	distance() Computes the total distance covered by the path
protected SearchPlan	generatePlan() Converts the sequenced array of transit points into a plan
protected void	incrementallyImprove() Uses pairwise comparison of array elements to incrementally improve a proposed traveling salesman problem solution.
double	partialDistance(int endPt) Computes the distance from the start to a specified point using the path
double	partialDistance(int startPt, int endPt) Computes the distance from a specified start point to a specified end point on the path
double	remainingDistance(int startPt) Computes the distance remaining from the specified point to the end of the path
void	run() Implements the Runnable interface

Methods inherited from class planner.avclPlan.search.TrackedSearchPlanner

setRequiredPD, setSweepWidth, setTrackSpacing

Methods inherited from class planner.avclPlan.search.SearchTrackPlanner

getPlan, getRunTime, setRunTime

Methods inherited from class java.lang.Object

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

Field Detail

THIRTY_DEGREES

public static final double THIRTY_DEGREES

See Also:

Constant Field Values

SIXTY_DEGREES

public static final double SIXTY_DEGREES

See Also:

Constant Field Values

SIN60

protected static final double SIN60

COS60

protected static final double COS60

searchSequence

protected double[][] searchSequence

Constructor Detail

TSPSearchPlanner

public TSPSearchPlanner(GeoArea searchArea,
                double S,
                double PD,
                double[] startPosit,
                boolean pointFocus)

Creates a new instance of TSPSearchPlanner

Parameters:

searchArea - geographic area that is to be searched

S -

PD -

startPosit - double[2] defining the vehicle's position at the beginning of the search

pointFocus - set to true if the vehicle is to start the search at the region's center

TSPSearchPlanner

public TSPSearchPlanner(GeoArea searchArea,
                double S,
                double PD,
                double[] startPosit)

Creates a new instance of TSPSearchPlanner

Parameters:

searchArea - geographic area that is to be searched

S -

PD -

startPosit - double[2] defining the vehicle's position at the beginning of the search

Method Detail

generatePlan

protected SearchPlan generatePlan()

Converts the sequenced array of transit points into a plan

Returns:

SearchPlan

computeVisitPoints

protected final List<double[]> computeVisitPoints()

Computes a set of points that blanket the search area. Ultimately, the search will consist of visiting each of these points in the most efficient sequence.

Returns:

ArrayList of double[2] points that define a set of (x, y) coordinates that blanket the area to be searched with sufficient granularity to achieve the required PD

partialDistance

public double partialDistance(int endPt)

Computes the distance from the start to a specified point using the path

Parameters:

endPt - of the last point in the partial transit

Returns:

the path distance from the start to the designated path point

partialDistance

public double partialDistance(int startPt,
                     int endPt)

Computes the distance from a specified start point to a specified end point on the path

Parameters:

startPt - index of the first point in the partial transit

endPt - index of the last point in the partial transit

Returns:

the path distance from the start to the designated path point

remainingDistance

public double remainingDistance(int startPt)

Computes the distance remaining from the specified point to the end of the path

Parameters:

startPt - of the last point in the partial transit

Returns:

the path distance from the start to the designated path point

distance

public double distance()

Computes the total distance covered by the path

Returns:

total distance covered by the path

incrementallyImprove

protected void incrementallyImprove()

Uses pairwise comparison of array elements to incrementally improve a proposed traveling salesman problem solution. The algorithm continues until no pairwise swap will improve the solution.

run

public void run()

Implements the Runnable interface

Specified by:

run in interface Runnable

Specified by:

run in class TrackedSearchPlanner