{"id":109,"date":"2026-02-19T01:08:43","date_gmt":"2026-02-19T01:08:43","guid":{"rendered":"https:\/\/mrsdprojects.ri.cmu.edu\/2026teame\/?page_id=109"},"modified":"2026-03-03T23:27:17","modified_gmt":"2026-03-03T23:27:17","slug":"f1tenth","status":"publish","type":"page","link":"https:\/\/mrsdprojects.ri.cmu.edu\/2026teame\/f1tenth\/","title":{"rendered":"F1TENTH"},"content":{"rendered":"\n
\n
Mapping<\/a><\/div>\n\n\n\n
Path Planning Algorithm<\/a><\/div>\n\n\n\n
Pure Pursuit<\/a><\/div>\n\n\n\n
User Interface<\/a><\/div>\n<\/div>\n\n\n\n
\n\n\n\n
\"f1tenth\"<\/figure>\n\n\n\n

Mapping<\/h4>\n\n\n\n

Implement a collision-free map converter that takes the built occupancy grid map from slam_toolbox as input. It generates an occupancy grid cost map to avoid possible obstacle collision in the mission planning process. It also labels the map grid outside the drivable area for the user interface so that waypoints are added correctly in the interface.<\/p>\n\n\n\n

\"\"
Figure: Correct dataflow shown in rqt_graph<\/figcaption><\/figure>\n\n\n\n
\"\"<\/figure>\n\n\n\n
\"\"
Figure: Map after Map Editing Tool<\/figcaption><\/figure>\n\n\n\n
\"\"
Map inflation results: robot_radius:0.2m, inflation_radius: 0.5m<\/figcaption><\/figure>\n\n\n\n
\n\n\n\n

Path Planning Algorithm<\/h2>\n\n\n\n

Map Inflator<\/strong><\/p>\n\n\n\n

Motivation:<\/strong><\/p>\n\n\n\n

Instead of relying on Nav2 as done previously in the map_converter module, we aimed to implement a custom map inflation method. This approach removes the need to launch multiple redundant Nav2 nodes and allows tighter integration with our custom planning pipeline.<\/p>\n\n\n\n

Methodology:<\/strong><\/p>\n\n\n\n

This work introduces a map_inflator ROS 2 node that inflates obstacles in an OccupancyGrid to improve navigation safety. The node expands occupied cells to create a buffer zone that accounts for the robot\u2019s physical footprint, ensuring the global planner maintains safe clearance from obstacles and walls.<\/p>\n\n\n\n

Key Features<\/strong><\/p>\n\n\n\n

Obstacle Inflation: Transforms a standard occupancy grid into a “cost map” where obstacles are thickened based on a configurable radius in meters.<\/p>\n\n\n\n

Configurable Safety Buffer: Uses the inflation_radius_m parameter to automatically calculate the required number of grid cells based on the map’s resolution.<\/p>\n\n\n\n

Customizable Thresholds: Allows users to define what constitutes an “occupied” cell and toggle whether unknown territory (v < 0) should be treated as a lethal obstacle.<\/p>\n\n\n\n

Topic<\/th>Type<\/th>Description<\/th><\/tr>
\/map<\/td>nav_msgs\/msg\/OccupancyGrid<\/td>Input: The raw static map from a map server or SLAM node.<\/td><\/tr>
\/cost_map<\/td>nav_msgs\/msg\/OccupancyGrid<\/td>Output: Current robot state from Localization (Particle Filter).<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
\"\"
Figure: Map in Rviz2 before Inflation<\/figcaption><\/figure>\n\n\n\n
\"\"
Figure: Map in Rviz2 after Inflation<\/figcaption><\/figure>\n\n\n\n

Path Planning<\/strong>:<\/p>\n\n\n\n

Motivation<\/strong>:<\/p>\n\n\n\n

<\/p>\n\n\n\n

Methodology:<\/strong><\/p>\n\n\n\n

<\/p>\n\n\n\n

Key Features:<\/strong><\/p>\n\n\n\n

Topic<\/th>Type<\/th>Description<\/th><\/tr>
\/map<\/td>nav_msgs\/msg\/OccupancyGrid<\/td>Input: The raw static map from a map server or SLAM node.<\/td><\/tr>
\/cost_map<\/td>nav_msgs\/msg\/OccupancyGrid<\/td>Output: Current robot state from Localization (Particle Filter).<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

Smoothing<\/strong><\/p>\n\n\n\n

<\/p>\n\n\n\n

Motivation:<\/strong><\/p>\n\n\n\n

<\/p>\n\n\n\n

Methodology:<\/strong><\/p>\n\n\n\n

<\/p>\n\n\n\n

Key Features:<\/strong><\/p>\n\n\n\n

Topic<\/th>Type<\/th>Description<\/th><\/tr>
\/map<\/td>nav_msgs\/msg\/OccupancyGrid<\/td>Input: The raw static map from a map server or SLAM node.<\/td><\/tr>
\/cost_map<\/td>nav_msgs\/msg\/OccupancyGrid<\/td>Output: Current robot state from Localization (Particle Filter).<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
    \n
  • Replaced the initial brute-force search (O(n!)) which was computationally<\/li>\n\n\n\n
  • prohibitive for n > 10.<\/li>\n\n\n\n
  • o Implemented a bitmasking approach to optimize the storage of the DP table,<\/li>\n\n\n\n
  • reducing time complexity to O(n^2 2^n).<\/li>\n\n\n\n
  • o Result: Capable of finding the mathematically optimal tour for small-to-medium<\/li>\n\n\n\n
  • waypoint sets.<\/li>\n<\/ul>\n\n\n\n

    Held-Karp Algorithm (Dynamic Programming)<\/strong><\/p>\n\n\n\n

    Nearest Neighbor (Greedy Heuristic):<\/strong><\/p>\n\n\n\n

      \n
    • o Implemented as a fallback for high-density waypoint scenarios (n > 20).<\/li>\n\n\n\n
    • o Utilizes Dijkstra\u2019s algorithm for cost estimation between nodes.<\/li>\n\n\n\n
    • o Result: Provides rapid solutions with minimal memory overhead, ensuring<\/li>\n\n\n\n
    • system responsiveness when optimality is secondary to speed.<\/li>\n<\/ul>\n\n\n\n

      Implemented one-to-all Dijkstra from the start to compute true grid-based travel costs to every target waypoint. And ensures costs reflect feasible paths around static obstacles, rather than relying on Euclidean distance.
      \u25cf Built a TSP solver for waypoint ordering, which use Nearest neighbor as the first stage as an initial greedy tour, then apply 2-opt (swap edges) refinement to reduce crossings and lower total cost iteratively
      \u25cf After determining the waypoint visiting order, used Hybrid A* to generate the
      kinematically feasible path connecting the ordered waypoints.
      \u25cf Packaged the Python implementation into a ROS2 package: path_planning<\/p>\n\n\n\n

      \"\"
      Figure: Hybrid A* output path for traversing 30 waypoints in a grid map of 200×200<\/figcaption><\/figure>\n\n\n\n
      \"\"
      Figure: TSP without smoothing (left), Dijkstra (middle), Dijkstra + NN (right)<\/figcaption><\/figure>\n\n\n\n

      Local Planning (Pure Pursuit)<\/h2>\n\n\n\n

      Implemented a pure-pursuit local planning module that takes the planned path and current vehicle state as input, computes a steering command, and publishes it to the vehicle control module. This enables the robot to follow smooth trajectories generated by the planning unit.<\/p>\n\n\n\n

      Pure Pursuit Algorithm:<\/p>\n\n\n\n

      \u03ba<\/mi>=<\/mo>2<\/mn><\/mspace>sin<\/mi>\u2061<\/mo><\/mrow>(<\/mo>\u03b1<\/mi>\/<\/mi>L<\/mi>)<\/mo><\/mrow>\\kappa = 2 \\sin(\\alpha \/ L)\n<\/annotation><\/semantics><\/math><\/div>\n\n\n\n

      Bicycle Model Integration:<\/p>\n\n\n\n

      \u03b4<\/mi>=<\/mo>arctan<\/mi>\u2061<\/mo><\/mrow>(<\/mo>L<\/mi>\/<\/mi>\u03ba<\/mi>)<\/mo><\/mrow>\\delta = \\arctan(L \/ \\kappa)<\/annotation><\/semantics><\/math><\/div>\n\n\n\n
      Topic<\/th>Type<\/th>Description<\/th><\/tr>
      \/planning\/path<\/code><\/td>nav_msgs\/Path<\/td>Input: Sequence of waypoints from the Planning unit.<\/td><\/tr>
      \/pf\/pose\/odom<\/code><\/td>nav_msgs\/Odometry<\/td>Input: Current robot state from Localization (Particle Filter).<\/td><\/tr>
      \/drive<\/code><\/td>ackermann_msgs\/AckermannDriveStamped<\/td>Output: Target steering angle and velocity for the vehicle.<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
      \"\"
      Figure: Visualization of Standalone Pure Pursuit Test<\/figcaption><\/figure>\n\n\n\n