CS6963: Algorithmic Foundations of Robotics, 2025 Fall, University of Utah
- Name: Seongil Heo
- UID: u1527760
- Date: November 25th, 2025
1. Include the A* shortest path figure on map2.txt between (252, 115) and (350, 350), with 600 vertices and a connection radius of 100.
Answer
2. Holding the number of vertices constant at 600, vary the connection radius when computing the shortest path on map2.txt. For each experiment, report the radius, path length, and planning time. Explain any variation. (You may find a table useful for summarizing your findings.)
Answer
Below radius 61, the planner fails to find a solution on map2.txt. Figure 2 shows the path length and planning time for radius 61–100. As the connection radius increases, the roadmap becomes more densely connected, but the path length decreases only at specific thresholds where new, shorter shortcuts become available, resulting in a stepwise reduction in path length. In contrast, a larger radius forces each vertex to attempt connections with more neighbors, leading to more collision checks and higher graph construction costs, which causes the planning time to increase roughly linearly. Consequently, planning time increases while path length decreases, exhibiting an inverse relationship.
Table 1 and Figure 3 shows the results including the case where the connection radius is 200. When the radius increased from 100 to 200, the path length improved by approximately 0.000231, while the planning time continued to grow linearly and increased by more than a factor of four.
(61, 70, 80, 90, 100, 200)
| Connection Radius | Path Length | Planning Time |
|---|---|---|
| 61 | 363.068 | 0.512 |
| 70 | 362.973 | 0.697 |
| 80 | 362.908 | 0.931 |
| 90 | 362.887 | 1.194 |
| 100 | 362.887 | 1.515 |
| 200 | 362.887 | 6.602 |
Table: Path Length & Planning Time vs. Connection Radius 61, 70, 80, 90, 100, and 200 on map2.txt (600 vertices)
3. Holding the connection radius constant at 100, vary the number of vertices when computing the shortest path on map2.txt. For each experiment, report the number of vertices, path length, and planning time. Explain any variation. (You may find a table useful for summarizing your findings.)
Answer
Below the number of vertices 541, the planner fails to find a solution on map2.txt. Figure 4 shows the path length and planning time for the number of vertices 541–600. Increasing the number of vertices does not affect the resulting path length, which stays close to 362.887. This indicates that the roadmap already contains all the connections needed to recover the optimal route, so additional samples do not provide any further benefit. However, the planning time continues to increase as more vertices are added, growing. This increase occurs because each new vertex introduces extra connection attempts, collision checks, and a larger graph for the planner to process, leading to steadily higher computational cost.
Table 2 and Figure 5 shows the results including the case where the number of vertices is 1200. When the number of vertices increased from 600 to 1200, the path length improved by approximately 6.554, while the planning time continued to grow linearly and increased by more than a factor of four.
| # Vertices | Path Length | Planning Time |
|---|---|---|
| 541 | 362.887 | 1.288 |
| 550 | 362.887 | 1.252 |
| 560 | 362.887 | 1.333 |
| 570 | 362.887 | 1.356 |
| 580 | 362.887 | 1.400 |
| 590 | 362.887 | 1.467 |
| 600 | 362.887 | 1.500 |
| 1200 | 356.333 | 6.432 |
Table: Path Length & Planning Time vs. Number of vertices on map2.txt (100 radius)
4. Use the previous experiments to choose a number of vertices and connection radius for map2.txt. Compute the shortest path with A* and Lazy A*. Report the path length, planning time, and edges evaluated. Explain any variation.
Answer
In Figure 4, the planning time is lowest when the number of vertices is 543, while the path length remains unchanged. With the number of vertices fixed at 543, the planner again fails to find a solution when the connection radius is below 61. Figure 6 shows the resulting path length and planning time when the radius is varied from 61 to 100 under this vertex setting.
Between radius 76 and 77, the path length and planning time curves intersect. At this point, the path length drops significantly while the planning time changes only slightly. Based on this trade-off, the optimal parameter choice is vertices = 543 and radius = 77.
Figure 7 shows the results of running A* and Lazy A* with a connection radius of 77 and 543 vertices. Visually, the difference between the two paths is difficult to distinguish.
| Lazy | # Vertices | Edges | Path length | Planning Time | Edges evaluated |
|---|---|---|---|---|---|
| False | 543 | 10639 | 362.908 | 0.699 | 11605 |
| True | 543 | 11539 | 362.908 | 0.076 | 320 |
Table 3 compares A* and Lazy A* on the same condition (543 vertices, radius 77). Both methods produce the same path length of 362.908, but Lazy A* is much faster. A* checks 11605 edges and takes 0.699 seconds, while Lazy A* checks only 320 edges and finishes in 0.076 seconds. This shows that Lazy A* greatly reduces collision checking cost without affecting the final path.
5. Compare the time spent on planning and shortcutting on map1.txt. Describe qualitatively how the paths differ.
Answer
Settings
- Lazy: True
- Vertices: 25
- Edges: 51
Results
- Running A*
- Path length: 12.960450156532826
- Planning time: 0.0017800331115722656
- Edges evaluated: 14
- Shortcutting A* path
- Shortcut length: 12.591492106547538
- Shortcut time: 0.0026865005493164062
The path without shortcutting follows the original edges selected by Lazy A*, so small unnecessary turns imposed by the graph structure remain, resulting in a more jagged trajectory. In contrast, the path with shortcutting removes as many intermediate waypoints as possible, producing a more direct and straight trajectory. Although both paths reach the same start and goal, the shortcut path is shorter and more efficient because it eliminates unnecessary detours.
6. Holding the number of vertices and connection radius constant at 40 and 4 respectively, vary the curvature at 3, 4.5, 9, and 15 when computing the shortest path on map1.txt. Include plots of the computed paths for each curvature. Describe qualitatively how the paths differ, and quantitatively compare the path lengths.
Answer
| Curvature | # Vertices | Edges | Path length | Planning Time (s) | Edges evaluated |
|---|---|---|---|---|---|
| 3 | 40 | 332 | 16.087 | 0.041 | 38 |
| 4.5 | 40 | 381 | 14.773 | 0.047 | 40 |
| 9 | 40 | 418 | 13.606 | 0.049 | 35 |
| 15 | 40 | 431 | 13.206 | 0.047 | 33 |
Table: Computed Lazy A* with 40 vertices, a connection radius of 4, and curvature values of 3, 4.5, 9, and 15.
Figure 9 and Table 4 show how the shortest path on map1.txt changes as the curvature is varied while keeping the number of vertices 40 and the connection radius 4 fixed.
Qualitatively, when the curvature is 3, the robot cannot turn sharply, resulting in the longest path, producing an unnecessary loop near the bottom. At 4.5, the robot gains a bit more turning capability, which removes the loop, but the path still makes a wide detour around the obstacle. When the curvature is increased to 9, the robot can execute much sharper turns, allowing it to pass closer to the obstacle boundaries and shortening the path. At 15, the path becomes the most direct, although the improvement over curvature 9 is small, indicating that most of the benefit is already achieved at curvature 9.
Quantitatively, lower curvature lead to longer paths, while higher curvature limits produce shorter and more efficient tra- jectories, with the path length decreasing from 16.087 to 13.206. The planning time remains nearly constant approximately 0.04 across all curvature values, while the path length decreases monotonically as the curvature increases. This demonstrates that increasing the robot’s maneuverability enables more direct paths without increasing computational cost.
7. The minimum and maximum steering angles used by MPC are -0.34 and 0.34 radians respectively. Knowing that the distance between the axles is 0.33 meters, what is the maximum curvature for the MuSHR car? (Hint: think about the kinematic car model.)
Answer
Base figure source:
https://courses.cs.washington.edu/courses/cse478/20wi/site/resources/lec5_motion_model.pdf
(lec5_motion_model.pdf, page 25)
Figure 10 illustrates the kinematic car model, where the distance between the axles
From the bicycle model geometry:
Thus,
The maximum curvature occurs when the steering angle reaches its maximum magnitude,
Therefore, the maximum curvature of the MuSHR car is approximately
8. Include an RViz screenshot of the MuSHR car tracking a path in maze_0, as well as the parameters you used to construct the roadmap.
Answer
motion_params
- vel_std: 0.05
- delta_std: 0.07
- x_std: 0.01
- y_std: 0.01
- theta_std: 0.03
sensor_params
- hit_std: 2.5
- z_hit: 0.8
- z_short: 0.01
- z_max: 0.01
- z_rand: 0.25
- K: 8
- T: 10
- Vertices: 1100
- Radius: 7
- Curvature: 0.9
9. Include an RViz screenshot of the MuSHR car tracking a path in cse2_2, as well as the parameters you used to construct the roadmap.
Answer
motion_params
- vel_std: 0.05
- delta_std: 0.07
- x_std: 0.01
- y_std: 0.01
- theta_std: 0.03
sensor_params
- hit_std: 5
- z_hit: 0.8
- z_short: 0.01
- z_max: 0.01
- z_rand: 0.25
- K: 8
- T: 10
- Vertices: 2000
- Radius: 7
- Curvature: 0.9
10. If you retuned either the particle filter or MPC, describe why you thought it was necessary and how you chose the new parameters.
Answer
For maze_0, the original particle filter and MPC settings were left unchanged. In contrast, for cse2_2, localization was unstable, so the sensor parameter hit_std was increased to 5. By making the sensor model less sensitive, the particle filter became more stable and operated more reliably.
Although the maximum curvature was calculated as 1.07 in Question 7, in practice this value produced turns that were too sharp for the vehicle to follow reliably. Therefore, the curvature was reduced to 0.9 so that the planned path would better match the vehicle’s actual trajectory. The radius was set to 7 because both environments use the same vehicle, and this value provided feasible paths within reasonable computation time. When using a smaller radius often caused the planner to fail, especially in long or complex paths. The number of vertices was chosen based on the map, balancing path quality with computational cost.