New Algorithm Redefines Autonomous Movement

Researchers from Caltech developed an algorithm for autonomous robots to assist with planning and decision-making. This system helps robots determine the best course of action while navigating the real world. The team described the Spectral Expansion Tree Search (SETS) method in Science Robotics.

Using machine learning and a unique algorithm to determine optimal moves within a set grid, Google DeepMind's AlphaZero program taught itself the games of chess, shogi, and go in 2018.

Our algorithm actually strategizes and then explores all the possible and important motions and chooses the best one through dynamic simulation, like playing many simulated games involving moving robots. The breakthrough innovation here is that we have derived a very efficient way of finding that optimal safe motion that typical optimization-based methods would never find.

Soon-Jo Chung, Bren Professor, Control and Dynamical Systems, California Institute of Technology

Soon-Jo Chung is also a Senior Research Scientist at JPL, which Caltech manages for NASA.

Many robots can move freely in any direction. For example, consider a humanoid robot designed to assist an older person around the house. As it comes across obstacles or unforeseen circumstances while performing its duties, such a robot should be able to move in various ways and, in essence, in any direction within the space. However, the challenges, obstacles, and movements these robots face will differ greatly from those of self-driving cars.

So, how can a single algorithm guide different robotic systems to choose the most effective course of action for navigating their specific environments?

You do not want a designer to have to handcraft these motions and say, 'This is the discrete set of moves the robot should be able to do. ' To overcome this, we came up with SETS.

John Lathrop, Graduate Student and Study Co-Lead Author, California Institute of Technology

SETS employs linear algebra and control theory to find natural motions that maximize a robotic platform's capabilities in a real-world environment.

The core concept is based on a Monte Carlo Tree Search (MCTS), a decision-making algorithm also used by Google's AlphaZero. In this context, "tree search" refers to navigating a branching structure that represents data relationships, while "Monte Carlo" indicates a random sampling approach.

In such a tree, the root branches out to child nodes, which are connected by edges. Potential moves are represented as new nodes in the MCTS, and the tree expands as more random samples of possible trajectories are tested.

After evaluating the potential outcomes of different moves, the algorithm selects the node with the best result based on a point valuation.

However, as Lathrop notes, the number of possible trajectories in the tree grows exponentially when this branching structure is applied to continuous dynamical systems, such as robots navigating through the real world.

“For some problems, trying to simulate every single possibility and then figure out which one is best would take years, maybe hundreds of years,” Lathrop said.

SETS uses a trade-off between exploration and exploitation to get around this.

Lathrop said, “We want to try simulating trajectories that we have not investigated before that is exploration. And we want to continue looking down paths that have previously yielded high rewards, that is, exploitation. By balancing the exploration and the exploitation, the algorithm is able to quickly converge on the optimal solution among all possible trajectories.”

For instance, a robot does not need to look into any of the other nodes on that branch of the tree if it begins by calculating a few potential actions that it believes would cause it to collide with a wall.

This exploration/exploitation tradeoff and search over the robot's natural motions enables our robots to think, move, and adapt to new information in real-time.

Benjamin Rivière, Postdoctoral Scholar Research Associate and Study Co-Lead Author, California Institute of Technology

SETS can complete a tree search in roughly a tenth of a second. During that time, it can simulate thousands to tens of thousands of potential paths, choose the best one, and then take action. As a result of the loop's continuous execution, the robotic system can make numerous decisions every second.

The SETS algorithm's ability to work on practically any robotic platform is one of its main advantages. Individual programming of the features and capabilities is not necessary. The algorithm's successful application in three distinct experimental settings is demonstrated by Chung and his colleagues in the new research, which is extremely uncommon in robotics studies.

In the first experiment, a quadrotor drone navigated an airfield with unpredictable air currents known as thermals, while observing four white balls and avoiding four orange ones. This experiment occurred at the Center for Autonomous Systems and Technologies (CAST) at Caltech.

In the second, the algorithm assisted a human driver operating a tracked ground vehicle on a narrow, winding track, helping to avoid collisions with the side rails. Finally, SETS was used to guide two tethered spacecraft in capturing and rerouting a third object, which could have been an asteroid, another spacecraft, or a different object.

The SETS algorithm is currently being applied by a team of Caltech researchers and students to an Indianapolis automobile that will compete in the Indy Autonomous Challenge on January 9 at the Consumer Electronics Show (CES) in Las Vegas.

The study was funded by the Defense Advanced Research Projects Agency's Learning Introspective Control (LINC) program, the Aerospace Corporation, and Supernal, and partially supported by the National Science Foundation Graduate Research Fellowship Program.

SETS was applied in three different robotic systems in experimental settings, including a drone, a tracked ground vehicle, and tethered spacecraft. Video Credit: California Institute of Technology

Journal Reference:

Rivière, B., et al. (2024) Monte Carlo tree search with spectral expansion for planning with dynamical systems. Science Robotics. doi.org/10.1126/scirobotics.ado1010.