A futuristic multi-level parking structure with cars parked in rows. The image features digital overlays and holographic lines indicating advanced automated navigation, connectivity, and smart parking systems guiding vehicles to available spots.

Volley Transforms AGV Path Planning

In the world of robotics and automation, one good rule is to never stand still. At Volley, our Autonomous Guided Vehicles (AGVs) live this maxim every day, and they’re about to get even better at it. We’re making big changes to our scheduling software that will make our garages work better and faster. This post dives into the significant changes we’ve made, why they matter, and what the future holds for our AVGs and garages.

Our AGVs rely on a centralized path planning system to understand where they are, where they need to go, and how to get there. The initial version of our path planning system, V1, was groundbreaking for its time – incredibly, that was only a few years ago. V1 utilized a sequential motion planning approach, which means that all parking tasks were lined up in a specific order. While this method worked, and taught us a lot, it had some challenges:

  1. Sequential Motion Planning: V1 required all tasks to be perfectly planned from the start. If an AGV was already in motion, re-routing it was impossible. This lack of flexibility led to delays, especially when we modeled unexpectedly higher numbers of cars coming into or out of a garage.
  2. Fixed Tray Planning: The system’s approach to handling the trays that the cars park on was rigid. AGVs could only perform fixed maneuvers, limiting their ability to handle more complex or dynamic scenarios, including differently sized cars. 
  3. Inefficient Planning: AGV tasks were always treated sequentially, with no ability for the robots to look ahead. This could result in inefficiencies, like an AGV going to a charger, but only staying there for a few seconds. 
  4. Geometric Reasoning: V1 had limited geometric reasoning, treating all payloads with the same bounding box and collision avoidance logic, meaning the garage wasn’t as space efficient as it could be.
  5. Language and Integration Issues: Some parts of V1 were written in C#, while more recent system components used C++, ROS, and Python. This disparity necessitated maintaining additional adapter code, complicating development and integration.

These limitations not only affected the efficiency of the AGVs but also posed significant challenges as the system scaled across multiple garages.

V2: Rise of The Autobots

We recently flipped the switch on V2, our eagerly awaited software update. While the initial release of V2 retains some sequential planning elements, it introduces several pivotal changes and sets the stage for even more significant enhancements.

  1. Conflict-Based Search (CBS) in Motion Planning: V2 employs a Conflict-Based Search algorithm, a robust method designed to handle a wider range of scenarios and provide more flexible solutions. Eventually, CBS promises to allow for mid-stage replanning, enabling AGVs to adapt dynamically to changes in a garage’s schedule.
  2. Enhanced Tray Planning: The new system introduces a more sophisticated tray planning logic capable of handling more difficult grid layouts for cars. While initial releases will still rely on some sequential planning, this sets the groundwork for more intelligent AGV assignments and simultaneous maneuvers. 
  3. Improved Geometric Reasoning: V2 brings a considerable upgrade in geometric reasoning. It now accounts for payload sizes, tray placements, and edge awareness. This comprehensive approach to geometric reasoning will prevent collisions and unnecessary delays, making the system more robust and adaptable to different layouts.
  4. Consistent Architecture: Maintenance, upgrades, and security are much easier with the entire system now written in the same set of languages.This change not only reduces the overhead of maintaining adapter code but also optimizes system latency and runtime, paving the way for more advanced capabilities in the future.


The Parking Lot Ahead: Full Implementation and Beyond

While the initial release of V2 is a significant step forward, the full vision for V2 includes even more advanced features that promise to revolutionize Volley’s AGV path planning even further.

  1. Full CBS Implementation: Completing the CBS algorithm will allow for the simultaneous planning of all AGVs, solving any MAPF instance. 
  2. Advanced Tray Planning: Future updates will integrate more sophisticated tray planning maneuvers. This will enhance the system’s ability to manage space and handle complex tray configurations seamlessly.
  3. Dynamic Job Planning: Upcoming enhancements will introduce replanning logic and job reordering capabilities. AGVs will be able to cancel and reassign tasks dynamically, improving overall system responsiveness. 
  4. Optimized Geometric Reasoning: Further improvements will reduce initialization times and enhance testing and development efficiency.

The transition from V1 to V2 marks a pivotal moment for Volley’s AGV path planning software. By addressing the limitations of sequential planning and introducing more advanced algorithms and logic, V2 sets the stage for a more flexible, efficient, and robust system. Whether it’s in automated parking garages or other industrial applications, advancements like these promise to bring us closer to a world where machines can navigate complex environments with ease and precision.