This is a Rust library implementing the Polyanya any-angle pathfinding algorithm on navigation meshes. It provides a core `Mesh` struct that supports 2D and 3D pathfinding with multiple overlapping layers, agent radius, and path simplification. The library includes several input formats: custom `.mesh` files (v2/v3), Recast JSON navigation meshes, triangulated meshes from outer edges and obstacles (via CDT), and trimesh files. It features an optimized A* search with chained expansions, geometric predicates for cone clipping and vertex snapping, and precomputed BVH for efficient point location. The repository contains extensive benchmarks, fuzz tests, and example binaries (including a scenario runner and traced profiling examples). It is structured as a reusable library with optional features like async, serde, stats, tracing, and Recast import. The code demonstrates strong engineering practices with careful handling of floating-point edge cases and performance-critical sections using `SmallVec` and `unsafe` indexing.
A ROS-based C++ implementation of the Hybrid A* path planning algorithm for nonholonomic autonomous vehicles, originally developed as part of a master's thesis at KTH. The system takes a binary occupancy grid (from LIDAR) and start/goal poses, then plans a smooth, drivable path using a combination of continuous-space A* with state discretization in heading, constrained (Dubins/Reeds-Shepp) and unconstrained (2D A*) heuristics, and a final gradient-descent smoother that accounts for obstacle clearance, curvature, and smoothness. It also optionally uses a Voronoi diagram to guide the path away from obstacles. The architecture is modular: a central Planner class manages ROS callbacks and orchestrates the search (Algorithm), collision detection (precomputed lookup tables for vehicle footprint), path tracing, and visualization via RViz. The code is well-documented and has been widely cited in autonomous driving research. While it is tightly coupled to ROS 1 (Noetic) and relies on OMPL for Reeds-Shepp heuristics, the core algorithmic components (lookup-based collision checking, Dubins path, gradient smoother) are self-contained and could be extracted for other projects.
PythonRobotics is a large collection of robotics algorithms implemented in Python, designed primarily for educational purposes and as a companion to a textbook. It covers a wide range of robotics domains including localization (EKF, particle filter, histogram filter), mapping (grid maps, NDT, clustering), SLAM (EKF SLAM, FastSLAM, GraphSLAM), path planning (A*, Dijkstra, RRT variants, PRM, DWA, Frenet, etc.), path tracking (Stanley, LQR, MPC, pure pursuit), arm navigation (inverse kinematics, RRT for arms), aerial navigation (drone trajectory, rocket landing), bipedal walking, inverted pendulum control, and mission planning (state machines, behavior trees). Each algorithm is implemented as a standalone script with a main() function that runs a simulation and visualizes results using matplotlib. The code is not packaged as a library and is not intended for production use; it is a learning resource with clear, readable implementations that reference academic papers. The repository includes extensive documentation in Sphinx RST format, CI/CD pipelines, and a test suite that runs each demo without animation.
This repository implements FAR Planner (Fast, Attemptable Route Planner using Dynamic Visibility Update), a robotic navigation system designed for subterranean environments. It builds and dynamically updates a visibility graph from LiDAR point cloud data to enable fast replanning in static and dynamic environments. The system uses a modular ROS architecture with separate components for contour detection, graph management, path planning, terrain handling, and sensor processing. Key features include dual-threaded operation (graph update and path search), RViz visualization, teleoperation capabilities, and integration with custom ROS message types for graph communication. The code was field-tested by the CMU-OSU Team in the DARPA Subterranean Challenge, where it won the 'Most Sectors Explored Award'.