TPS-A*: Path Planning for Any-Shape Vehicles with Certified Collision Checking in Trajectory Parameter Space
TPS-A*: Path Planning for Any-Shape Vehicles with Certified Collision Checking in Trajectory Parameter Space
This research introduces TPS-A*, a path planning algorithm designed for ground vehicles of any shape, utilizing certified collision checking within trajectory parameter space. The method precomputes a grid per footprint to ensure collision-free paths and bounded suboptimality independent of footprint complexity. Evaluated on 300 cluttered worlds, the planner solves queries in a median of three milliseconds on an AMD Ryzen 7 2700X, matching hybrid A* performance while avoiding obstacles and being nearly sixty times faster than other collision-free state-lattice planners. The system successfully handles non-convex footprints like forks, performs automated parking, navigates narrow doorways, and has been demonstrated driving a real robot across a university campus among people.
Source: arXiv Robotics — research abstracts · Read original article ↗
Loading article text…
What the source reports
Publisher-reported claims, with original evidence. These results have not been independently verified by RoboSignal.
Reported numbers
median execution time
3
View original evidence
edian of three milliseconds on an AMD Ryzen 7 2700X, on par with hybrid A*, 45\% of whose paths overlap obstacles, and nearly sixty times faster than a state-lattice planner, the only other collision-free one; with position goals, eighty-nine times faster than hybrid A*. It matches hybrid A* in automated parking and on narrow doorways, docks a non-convex fork footprint that no convex model admits, and drove a real ro
Open source S5execution time comparison ratio
60
View original evidence
edian of three milliseconds on an AMD Ryzen 7 2700X, on par with hybrid A*, 45\% of whose paths overlap obstacles, and nearly sixty times faster than a state-lattice planner, the only other collision-free one; with position goals, eighty-nine times faster than hybrid A*. It matches hybrid A* in automated parking and on narrow doorways, docks a non-convex fork footprint that no convex model admits, and drove a real ro
Open source S5execution time comparison ratio
89
View original evidence
edian of three milliseconds on an AMD Ryzen 7 2700X, on par with hybrid A*, 45\% of whose paths overlap obstacles, and nearly sixty times faster than a state-lattice planner, the only other collision-free one; with position goals, eighty-nine times faster than hybrid A*. It matches hybrid A* in automated parking and on narrow doorways, docks a non-convex fork footprint that no convex model admits, and drove a real ro
Open source S5
- paper: not_reported
- code: not_reported
- weights: not_reported
- dataset: not_reported
Source excerpts and review record
Automatically extracted; no manual editorial approval recorded.
bot across a university campus among people.
Open source S6
edian of three milliseconds on an AMD Ryzen 7 2700X, on par with hybrid A*, 45\% of whose paths overlap obstacles, and nearly sixty times faster than a state-lattice planner, the only other collision-free one; with position goals, eighty-nine times faster than hybrid A*. It matches hybrid A* in automated parking and on narrow doorways, docks a non-convex fork footprint that no convex model admits, and drove a real ro
Open source S5
tees: collision-free paths and bounded suboptimality relative to its lattice abstraction. Goals with or without heading are reached exactly by Reeds-Shepp shots certified as trajectories of the same generators. An exact independent test finds no collision in its paths. On 300 cluttered worlds, with the true footprint and the same goal pose for all planners, it solves every query with a collision-free goal pose in a m
Open source S4
Source：arXiv Robotics — research abstracts · arxiv.org