frc::TravelingSalesman Class Reference

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

#include <frc/path/TravelingSalesman.h>

Public Member Functions
constexpr	TravelingSalesman ()=default
	Constructs a traveling salesman problem solver with a cost function defined as the 2D distance between poses.
	TravelingSalesman (std::function< double(Pose2d, Pose2d)> cost)
	Constructs a traveling salesman problem solver with a user-provided cost function.
template<size_t Poses>
wpi::array< Pose2d, Poses >	Solve (const wpi::array< Pose2d, Poses > &poses, int iterations)
	Finds the path through every pose that minimizes the cost.
std::vector< Pose2d >	Solve (std::span< const Pose2d > poses, int iterations)
	Finds the path through every pose that minimizes the cost.

Detailed Description

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 & Destructor Documentation

TravelingSalesman() [1/2]

frc::TravelingSalesman::TravelingSalesman ( )

constexprdefault

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

TravelingSalesman() [2/2]

frc::TravelingSalesman::TravelingSalesman ( std::function< double(Pose2d, Pose2d)> cost )

inlineexplicit

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.

Member Function Documentation

Solve() [1/2]

template<size_t Poses>

wpi::array< Pose2d, Poses > frc::TravelingSalesman::Solve ( const wpi::array< Pose2d, Poses > & poses, int iterations )

inline

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.

This overload supports a statically-sized list of poses.

Template Parameters

Poses

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.

Solve() [2/2]

std::vector< Pose2d > frc::TravelingSalesman::Solve ( std::span< const Pose2d > poses, int iterations )

inline

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.

This overload supports a dynamically-sized list of poses for Python to use.

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.

---

The documentation for this class was generated from the following file:

• frc/path/TravelingSalesman.h