Simulated annealing in WPILib

truher · December 5, 2023, 5:25pm

wpimath/src/main/java/edu/wpi/first/math/optimization/SimulatedAnnealing.java

woah, cool.

calcmogul · December 5, 2023, 6:50pm

For those confused by the lack of context, WPILib 2024 will ship a simulated annealing optimization problem solver and a traveling salesman problem solver.

Solving optimization problems involves tweaking input variables to try to minimize some cost function. Simulated annealing is good for solving optimization problems with many local minima and a very large search space (it’s a heuristic solver rather than an exact solver like, say, SQP or interior-point method). Simulated annealing is a popular choice for solving the traveling salesman problem, a problem where you’re trying to find the shortest ordered list of destinations. The class in WPILib supports a list of Pose2ds.

Ashray.g · December 5, 2023, 6:52pm

Oh did someone port my java to c++ a year later

dan · December 5, 2023, 6:53pm

What are some possible usages for these solvers?

calcmogul · December 5, 2023, 6:53pm

Yea, I cleaned it up and got it merged.

calcmogul · December 5, 2023, 6:53pm

See my edited post.

Ashray.g · December 5, 2023, 6:55pm

eg

github.com

wpilibsuite/allwpilib/blob/14c3ade155080ee7d4ae1467e3e0c54e4b561337/wpimath/src/test/java/edu/wpi/first/math/path/TravelingSalesmanTest.java#L15


      
          package edu.wpi.first.math.path;
          
          import static org.junit.jupiter.api.Assertions.assertEquals;
          import static org.junit.jupiter.api.Assertions.assertTrue;
          
          import edu.wpi.first.math.geometry.Pose2d;
          import edu.wpi.first.math.geometry.Rotation2d;
          import edu.wpi.first.util.CircularBuffer;
          import org.junit.jupiter.api.Test;
          
          class TravelingSalesmanTest {
            /**
             * Returns true if the cycles represented by the two lists match.
             *
             * @param expected The expected cycle.
             * @param actual The actual cycle.
             */
            private boolean isMatchingCycle(Pose2d[] expected, Pose2d[] actual) {
              assertEquals(expected.length, actual.length);
          
              // Find first element in actual that matches expected

Oblarg · December 5, 2023, 7:27pm

Cool to see this made it in!

dan · December 5, 2023, 7:34pm

Can you provide an example for FRC usage for this?

AndrewMcb · December 5, 2023, 7:45pm

A classic example would be finding the optimal path through a field with objects to avoid when given a starting and ending point. Some discussion on the topic in an FRC context can be found in other threads like this: Finding Optimal Path Through Game Objects

SLAB-Mr.Thomas · December 5, 2023, 10:07pm

Many years ago I used my simulated annealing program (basically from Scientific America, IIRC) for computer generated pairings for a large Secret Santa gift exchange. Had rules, for example, exchange with kids within X years of age of each other and adults-to-adults, no exchanges within the same family (different last name), etc.

Joe_Ross · December 6, 2023, 3:34am

scheduling FRC matches

Oblarg · December 6, 2023, 3:31pm

For those interested in the history of this feature - it was originally a personal project on the FRC discord, which we then suggested upstreaming. It took a couple years, but was never forgotten, and here it is now!

Remember that you, too, can provide major feature additions to WPILib - all you need to do is open a PR and talk about it with the other contributors. I strongly recommend that anyone graduating from FRC who wants to stay involved consider doing so through this kind of contribution - it’s good resume fodder, too.

system · December 5, 2024, 3:31pm

This topic was automatically closed 365 days after the last reply. New replies are no longer allowed.