Package edu.wpi.first.math.path

Class TravelingSalesman

java.lang.Object

edu.wpi.first.math.path.TravelingSalesman

public class TravelingSalesman
extends Object

Given a list of poses, this class finds the shortest possible route that visits each pose exactly once and returns to the origin pose.

See Also:

https://en.wikipedia.org/wiki/Travelling_salesman_problem

Constructor Summary

Constructors

Constructor	Description
TravelingSalesman()	Constructs a traveling salesman problem solver with a cost function defined as the 2D distance between poses.
TravelingSalesman(ToDoubleBiFunction<Pose2d,Pose2d> cost)	Constructs a traveling salesman problem solver with a user-provided cost function.

Method Summary

Modifier and Type	Method	Description
<Poses extends Num> Pose2d[]	solve(Pose2d[] poses, int iterations)	Finds the path through every pose that minimizes the cost.

Methods inherited from class java.lang.Object

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

Constructor Details

TravelingSalesman

public TravelingSalesman()

Constructs a traveling salesman problem solver with a cost function defined as the 2D distance between poses.

TravelingSalesman

public TravelingSalesman(ToDoubleBiFunction<Pose2d,Pose2d> cost)

Constructs a traveling salesman problem solver with a user-provided cost function.

Parameters:

cost - Function that returns the cost between two poses. The sum of the costs for every pair of poses is minimized.

Method Details

solve

public <Poses extends Num> Pose2d[] solve(Pose2d[] poses, int iterations)

Finds the path through every pose that minimizes the cost. The first pose in the returned array is the first pose that was passed in.

Type Parameters:

Poses - A Num defining the length of the path and the number of poses.

Parameters:

poses - An array of Pose2ds the path must pass through.

iterations - The number of times the solver attempts to find a better random neighbor.

Returns:

The optimized path as an array of Pose2ds.