- Rating
- 2
- Confidence
- 3
- Informativeness
- 1
- Presentation
- 3
- Soundness
- 1
Read review
Paper summary
The authors study the problem of coverage path planning for a robot in a navigation setting with a set of charging locations under energy constraints. The authors propose a framework around standard PPO to enforce this constraint in a way that is robust to estimation errors for underlying cost/energy predictors.
Critical strengths
The authors are also commended for a well written and clear draft that studies a very clearly defined problem and reports reasonable results. I like the crisp problem.
Critical weaknesses
That said, there are some questions that may limit the impact and significance of the findings. Primarily, while the improvement over naive PPO seems clear, it is less clear why something like "Exact-mask PPO" or alternative (heuristic or algorithmic) approaches may not suffice or even be more desirable to enforce strict adherence to safety instead of improved empirical adherence.
I am open to bumping up the score if there is satisfactory expository or empirical clarification around the presented question. The strength of the paper is that the problem is very crisp. Covering the bases to strengthen the significance argument will improve the draft.
Questions for authors
Specific comments/questions follow.
Consider related work [1] or similar literature that studies algorithmic or optimization-based views of this category of problem. In the gridworld simplification the authors impose on Procthor, can such methods work? What are the challenges of applying approximate combinatorial/MILP solvers and optimizers to known maps? I.e., beyond improving PPO, the authors should consider discussing and motivating the key challenges in the problem that necessitate the policy and then motivate the benefits of the safety constraint improvements to the learned policy.
Exact-PPO is presented as undesirable because of needing an oracle. For a given map, this oracle should be precomputation. How expensive is this? This relates also to unclear details about the dimensions of the maps (grids). Details about Exact-mask PPO are missing -- is the oracle/masking needed during training or deployment?
Consider also alternative simple/heuristic safety filters that operate strictly locally. Use any black box policy for the primary task -- coverage. This may be the PPO the authors train. From a state you can estimate/compute R*(s). Explicit computation for a single state should be a single start multi goal search on a grid if the map is known. The policy \pi proposes an action/next state s'. You can compute/estimate d_g(s,s') and R*(s'). If the current charge E_t < d_g(s,s') + R*(s'), go to nearest charger by incurring cost R*(s). This forces the black box policy to remain feasible, albeit potentially inefficient and also not complete. Will such a heuristic strategy suffice? What are challenges in such strategies? Are they computational or is some information not known?
Empirical evidence will be strongest but clear exposition or clarification about challenges and limitations in the studied setting may be helpful.
While recovery is active, the controller selects an available charging target with the largest predicted reserve. -> why will the charging target not be available?
What is the dimension of the grids the authors evaluate? Examples of the maps and settings should be included as well to help the reader.
The assumption that traversing a cell is not covering it may be too restrictive in many scenarios.
[1] Sharma, Gokarna, Ayan Dutta, and Jong-Hoon Kim. "Optimal online coverage path planning with energy constraints." In Proceedings of the 18th international conference on autonomous agents and multiagent systems, pp. 1189-1197. 2019.
2 comments
I thank the authors for their careful response.
I will repeat my original comment that the problem is very crisp. Its simplicity merits a clear discussion about the aspects that make it interesting.
Going by the numbering in the author response 1-6.
I will group 1, 3 together. The focus on "using estimated return costs" is weakened by the observation in 3 that "exact, precomputed costs" are applicable. The mitigating argument is that "Coverage can still stall". While this does sound somewhat intuitive, this needs some evidence and clear motivation. For example, a probabilistic policy that has support over enough of the action space should return a different action eventually. I think the point to "learn feasibility from experience when interacting constraints make exact checks difficult" may prove interesting but the presented domain does not appear to have this characteristic.
The authors mention "recharging may keep the robot within its energy budget but leave too little time to meet a deadline." Nitpick: I do not agree with this point. Given the standard optimization formulation, charging can be modeled as a constraint. So if the robot charges, it should not, for example, always charge fully. The time spent to charge should be recovered from the optimization for the primary task. This constrained optimization problem should have an optima. If the optimal budget allocation to charging and coverage fails to meet a time deadline this means that that deadline is infeasible given the specification of the optimization. For example, if all coverage locations are farther away than a safe return range.
The response point 4 are handcrafted assumptions within the studied setting. In future drafts, these should be accompanied by some practical motivation.
Overall, a fair set of discussions and comparisons with classical, algorithmic, optimization-based methods, or filters on black box policies will benefit the communication of both the methodological and practical design choices behind designing robotic systems that need to solve navigation-based tasks with charging budget constraints. At this point, I think this may require a fresh resubmission that takes into account all reviewers' comments.
Thank you for these questions and for the recommendation paper. We will cite their work on online energy-constrained coverage and explain how it relates to our known-map benchmark.
The planning problem is to choose the order of service targets and divide them into charging tours that each fit within the battery budget. Shortest-path search gives the cost of traveling between targets. Choosing the order of visits and deciding where to recharge remain joint routing decisions. Our TSP-Split baseline demonstrates that classical planning is effective in this setting. It completed every evaluated mission without a violation. Our contribution is to examine what happens when a coverage policy makes decisions using estimated return costs under a hard energy constraint. In Table 2, the false-feasible rate was 2.1% among admitted candidates and 4.6% among PPO’s proposals. This distinction matters because feasibility estimates are used on the targets the policy actually favors. RAC-PPO combines checks on the proposed target with a recovery mode that stays active until recharging. The known-map benchmark gives us exact costs against which to measure the estimation errors and study how they interact with those decisions.
2.Exact-PPO is presented as undesirable because of needing an oracle. For a given map, this oracle should be precomputation. How expensive is this? Details about Exact-mask PPO are missing -- is the oracle/masking needed during training or deployment?
Thank you for pointing out that exact return costs can be precomputed. For each static map, charger layout, and motion model, a single multi-source Dijkstra search initialized at all chargers computes the minimum return cost from every traversable cell. With a binary heap, the search takes O((|V| + |E|) log |V|) time, and subsequent decisions can retrieve these costs from a lookup table. The manuscript does not report measured preprocessing times. For RAC-PPO, we use exact return costs to fit the return-cost estimator. During evaluation, candidate admission, proposal checking, and recovery all use the estimator’s predictions. We compute exact reserves after action selection solely to assess constraint violations. The Exact-mask PPO baseline uses precomputed exact return costs to exclude infeasible targets during evaluation. The submitted manuscript does not specify whether this baseline also used the exact mask during training. We will clarify the evaluation-time use of exact costs for both methods in the revised manuscript.
We agree that, on our known grid, the proposed filter preserves return feasibility if the robot starts in a return-feasible state and uses exact, precomputed costs. Coverage can still stall if the policy repeatedly proposes an infeasible target after recharging. RAC-PPO uses a fixed reserve check with a learned return-cost estimate. The known grid lets us measure how estimation errors affect target selection and recovery. Our longer-term goal is to learn feasibility from experience when interacting constraints make exact checks difficult. For example, recharging may keep the robot within its energy budget but leave too little time to meet a deadline.
While coverage is incomplete, the robot’s current charger is excluded from the candidate set. In a single-charger map, this can leave the set empty. Recovery selects the eligible charger with the largest predicted reserve. If none is eligible, it selects the candidate minimizing outbound cost plus predicted return cost. RAC-PPO achieved 93.92% mission success, with violations in 6.08% of episodes overall and 18.23% at the tightest budget. We will clarify the fallback in Algorithm 1.
What is the dimension of the grids the authors evaluate? The floorplans are discretized into 0.5 m × 0.5 m cells, and we use a robot radius of 0.2 m when determining traversability. The manuscript gives the cell resolution but omits the grid dimensions and the distribution of traversable-cell counts. We will report these statistics and include representative maps showing the charger placements and motion settings. Future evaluations will consider a broader range of map sizes.
The assumption that traversing a cell is not covering it may be too restrictive in many scenarios.
We agree that pass-through coverage is appropriate for many applications. Our benchmark marks a cell as covered when the robot reaches it as a selected target, as in tasks that require a measurement at a designated location. We will clarify this assumption and discuss its implications for route choice and travel distance.