Verified Planning for Uncrewed Ground Vehicles in Dynamic Environments

Principal Investigators

• Kevin Leahy (PI), Worchester Polytechnic Institute
• Vladimir Vantsevich, Lee Moradi (co-PI), WPI

Students

• Taylor Bergeron, Rohan Walia, Philip Smith, WPI

Government

• Philip Frederick, Jon Smereka, U.S. Army GVSC

Industry

• Alyssa Scheske, Applied Intuition

Project #1.A125 began end-2025.

Signal Temporal Logic (STL) has been used for mission planning for robots in a variety of settings. One promising avenue is for autonomous driving, in which STL has been used to encode the rules of the road. However, this work does not meet the requirements of military operations with a UGV for two reasons. First, the UGV is likely to travel on much different terrain than autonomous cars developed for civil transportation. The UGV will travel on unpaved, variable terrain, as opposed to paved roads designed for driving. Accounting for the traversability constraints in such unstructured environments is critical. Second, the most common approach to planning using STL is using mixed-integer linear programming (MILP). MILPs are a combinatorial optimization problem that are known to be NP-hard. Therefore, running them at operational speed for replanning is not reliable. Indeed our recent work shows that replanning can take just as long as initial plan generation when using a MILP.

The goal of this project is to develop a method for rapidly planning and replanning for an autonomous vehicle (or team of autonomous vehicles) in a dynamic, unstructured environment, in order to satisfy high-level constraints, such as mission objectives, and link them with low-level trajectory constraints, such as traversability requirements.

The research objectives of this project are to link the low-level trajectory planning problem with the high level mission planning problem in order to overcome dynamic changes that inevitably occur during mission execution. Linking these two levels requires a planning formalism that can capture meaningful constraints across both levels. Although tools for planning under such a formalism exist, there are two key questions that must be addressed to deploy such a planner in this context.

RQ1: Can an autonomous agent make verifiable planning decisions at operational speeds? If a system is going to be deployed in real-world missions, its decisions need to be computationally tractable for the size, weight, and power (SWaP) constraints of the autonomous system. While UGVs are less SWaP-constrained than small UAS, they cannot utilize as much computational power and time as grid- or cloud-based optimizers often leverage. Therefore, we seek a new method for casting these decision problems that is amenable to solving on low-SWaP hardware at high speeds.

RQ2: Can the decision process incorporate dynamic updates to the environment and the mission? In addition to being fast to compute, solutions need to easily incorporate dynamic information at run time, as operating conditions change. While purely symbolic methods maintain a graph object that can be incrementally updated, adding incremental updates to an optimization problem can require an entirely new solution process. Thus, a solution method that can be incrementally updated is critical.

#1.A125