Saurav Kambil

Saurav Kambil

M.S. in Mechanical Engineering @ Carnegie Mellon University

Catching a Moving Target: My Venture into Dynamic Path Planning

Intricacies of Dynamic Path Planning

The essence of my project was to develop a planner in C++ that enables a robot to catch a moving target within a grid-based environment, reflecting real-life scenarios where timing and precision are crucial.

Problem Setup

The simulation environment was a complex grid with various obstacles, where both the robot and the target had discrete, predictable movement patterns. The task was to calculate a path in minimal time, ensuring the robot could intercept the moving target despite the constraints imposed by the environment.

The Planner

  • Backward Dijkstra’s Implementation: I utilized a backward Dijkstra’s algorithm to compute a heuristic that informed the A* search, enhancing the planner’s foresight.
  • C++ for Performance: The code was executed in C++, chosen for its execution speed and low-level memory management capabilities, critical for real-time applications.
  • Memory Management: Employing dynamic allocation, I ensured efficient memory usage, crucial for maintaining performance during the planner’s runtime.

In summary, the heuristic calculation provides estimates of cell costs, the A* search finds an optimal path, and the search strategy evaluates and selects promising goals for the robot to reach. These components work together to efficiently guide the robot through the grid-based environment while considering obstacles and time constraints.

Performance and Results

The planner was rigorously tested, showing that it could catch the target in a variety of grid configurations. Performance times ranged from a swift 126 seconds in simpler scenarios to more complex ones requiring up to 4672 seconds, demonstrating the planner’s adaptability.

Conclusions and Future Work

This project not only honed my skills in algorithmic design and C++ but also laid the groundwork for future exploration into more unpredictable and non-grid-based environments, potentially using machine learning to predict target movements.

My full report details the entire process and can be found here.