The PETLON Algorithm to Plan Efficiently for Task-Level-Optimal Navigation

Shih-Yun Lo, Shiqi Zhang, Peter StoneJAIR 2020 · DOI

The integration of high-level reasoning and low-level movement has long been a "holy grail" in robotics. PETLON (Planning Efficiently for Task-Level-Optimal Navigation) is a framework that bridges this gap by integrating task and motion planning to guarantee the lowest-cost solution for robot navigation. By using a "lazy" evaluation strategy, PETLON finds the mathematically optimal sequence of actions for complex tasks without the computational burden of calculating every possible path in advance.

The Challenge of Task-Level Navigation

Imagine a robot tasked with preparing for a camping trip: it needs to fetch a cooler, then a hot dog from the fridge, then a newspaper, and finally deliver them to a storage room.

A robot navigating a complex task involving multiple waypoints like a cooler, fridge, and newsstand.

Traditionally, this problem is split into two distinct layers:

  1. Task Planning: Decides the order of operations (e.g., "get cooler before hot dog") using symbolic logic.
  2. Motion Planning: Finds the actual geometric path between points.

The core issue is that task planners usually estimate movement costs using simple straight-line distances. In cluttered environments, these estimates are often inaccurate. To achieve true optimality, the robot needs actual motion costs. However, calculating the exact path between every possible pair of objects in a large building is an $O(N^2)$ problem that scales poorly as the number of rooms and items increases.

The PETLON Methodology

PETLON treats motion planning as an expensive resource to be used sparingly. It employs three cost functions to guide its search:

  • Heuristic ($h$): An optimistic "guess," such as Euclidean distance.
  • Evaluated ($\hat{C}$): The actual cost returned by a real motion planner (e.g., PRM*).
  • Maintained ($Cost$): A running tally that starts as a heuristic and is updated with real data as the algorithm iterates.
The PETLON approach evaluates only a subset of potential motion paths (red) rather than all possible connections (gray).

The algorithm operates in a loop where the Task Planner finds the best plan based on current costs, and the Motion Planner evaluates only the actions within that specific plan. If the "best" plan's actions have all been evaluated and it remains the optimal choice, the robot executes it. This "lazy" approach avoids thousands of unnecessary calculations by deferring expensive motion planning until a task is actually recommended by high-level logic.

Key Results and Scalability

The researchers evaluated PETLON in high-fidelity simulations and on a physical RMP 110 mobile robot. The results demonstrated massive efficiency gains:

  • Efficiency: In a large-scale test case, a brute-force approach required 2,850 motion evaluations, while PETLON found the same optimal plan with fewer than 26 evaluations.
  • Speed: In standard domains, PETLON reduced total planning time from over 30 seconds to under 20 seconds while maintaining 100% task-level optimality.
  • Quality: While simple heuristic baselines produced paths of 50 meters, PETLON consistently identified the optimal 37-meter path.

Conclusion and Future Directions

PETLON proves that "admissibility"—using heuristics that never overestimate the true cost—allows a robot to safely ignore suboptimal plans even under perfect conditions. While currently focused on static maps and fixed state-to-coordinate mappings, future work aims to incorporate dynamic obstacles and adapt the framework for complex manipulation tasks, such as robotic shelf organization.

Summary updated

BibTeX
@article{lo2020petlon,
  author = {Shih-Yun Lo and Shiqi Zhang and Peter Stone},
  title = {{The PETLON Algorithm to Plan Efficiently for Task-Level-Optimal Navigation}},
  journal = {J. Artif. Intell. Res.},
  year = {2020},
  doi = {10.1613/jair.1.12181},
}
Figure