Learning Coverage Paths in Unknown Environments with Reinforcement Learning

We thank the reviewer for their valuable feedback on how to improve the comparison with other methods, and we appreciate the positive feedback. We reply to the concerns below.

The baselines may not be challenging enough, a TSP-baseline should be included. We agree that a TSP-baseline would further increase the quality of the comparison. However, we believe that the methods under comparison provide sufficient insights about the performance of our method, as they span a wide range of approaches.

Unclear how the baselines are implemented. We used the implementations from their code repositories. We will provide links to these in the appendix to make it more clear.

The RL-based baseline (Hu et al., 2020) targets a multi-agent setting, it is not clear if this is a fair comparison. As Hu et al. predict control signals using RL (although not end-to-end) we consider it the closest related method to our work, and thus we wanted to compare with it. Based on Voronoi partitioning, it can also be used for multi-agent exploration. However, for a fair comparison, we limited it to one agent as this is the focus of our paper. As Hu et al. predict the control signals based on the relative goal position from a previous stage in their framework, a simpler network architecture is sufficient, compared to predicting them based on the full map observation.

Some baselines are originally proposed in multi-agent settings. Apart from Hu et al. and the potential field-based method (Yu et al., 2021), all other methods were originally proposed in a single-agent setting. Xu et al. (2022) later extended them to the multi-agent case. We believe that the absence of the multi-agent component in Yu et al. does not trivialize their method nor hinder single-agent performance, as they showcase their method also in single-agent exploration. This method still serves as a useful comparison in the single-agent case, as this is a common approach for single-robot path planning.

Total variation contribution is slightly overclaimed, it is simply the perimeter. The key is that TV can be computed locally and continuously, enabling e.g. variational image enhancement, infilling, and segmentation methods (a body of several hundred papers). The insight that these properties also enable its application in continuous RL is, to the best of our knowledge, novel.

What is the collision frequency? For exploration, it varied between once every 100-1000 seconds, which is roughly once every 50-500 meters. For lawn mowing, it varied between once every 150-250 seconds, which is roughly once every 30-50 meters. However, the vast majority of collisions were near-parallel, and we didn’t see any head on collisions. The practical implications are very different between these cases. We will add this analysis to the appendix.

Thank you. Just a note, TSP solvers typically allow you to specify a distance matrix between every pair of points, so ideally you would try to quantify if this makes a difference from Euclidean distance (on a grid you can get the known shortest paths between any two points with the A* or Bellman Ford algorithm). If Concorde is somehow not a good fit, LKH-3 is another commonly used TSP solver and can be downloaded from http://webhotel4.ruc.dk/~keld/research/LKH-3/. And also I don't necessarily expect the proposed RL method to perform better, but knowing the tradeoff between solution quality and planning time of a TSP solver would significantly help characterize the proposed method.

The negative holes is a fair point, and I agree that "perimeter" is a crude term for cases like this, but I think there should be a better term for the total boundary which gives more insight on a global level than TV, which is a local operation that you apply globally.

We thank the reviewer for their feedback, and provide replies to the concerns below.

The research has limited novelty, with a modest contribution. May we kindly ask the reviewer to be more specific, e.g. by giving a reference that would limit the novelty? As far as we know, previous work has not applied RL to learn continuous control signals end-to-end in CPP. In our interpretation, the strengths outlined by reviewers aapF and 5fHE tend to suggest that they agree. Learning control signals end-to-end in this way comes with unique challenges, which we address in the paper.

Most machine learning and classical planning methods can handle the investigated problem. We agree that many classical and learning-based methods tackle a similar problem. However, none approach it end-to-end with RL as mentioned above. Compared to classical methods and multi-stage frameworks, this approach does not put any constraints on the path space, and allows the model to adapt to specific quirks in the agent dynamics in order to find a more efficient path.

In terms of multi-scale approaches, prior studies have delved into this issue. This is true. We are not suggesting that it is a new concept, but rather, that it is a necessary part in our solution to the challenge of applying RL to large-scale CPP. We will clarify this part in the paper.

How might the research tackle sim-to-real transfer? Good question. As mentioned early on page 4, we believe that our approach can be used with an off-the-shelf SLAM method, removing the need for known pose. In this setting, the agent can learn and adapt to the noise characteristics during training. That our approach works well on noise-free data / data with simulated noise is a necessary condition for future real-world applications. The evaluation of our method on physical robot systems with realistic, noisy sensing will be subject of a future manuscript.

How does the agent architecture differ from architectures in methods like TRPO? The architectures used in TRPO are either feed-forward fully connected networks, similar to our MLP baseline, or convolutional networks for image observations, similar to the map feature branch in our CNN baseline. They are different in regards to our multimodal feature extractor and SGCNN architecture.

We thank the reviewer for their valuable feedback on how to improve the quality of our paper. We address the first two points. Additional answers will follow shortly.

The proposed method does not include any environment dynamics. The ability to adapt to non-modeled environment dynamics was mainly used as a motivation for choosing an RL-based approach. Indeed, [1] shows that in grid environments, RL can be robust to dynamic environments and outperform classical methods. We missed to include this reference and will update the paper accordingly. Due to the findings in [1], we focused on the question whether an RL-based approach can learn patterns to choose locations that are promising in terms of new information in a continuous setting at all, before moving to dynamic environments.

[1] Saha et al. “Online area covering robot in unknown dynamic environments”, ICARA, 2021.

Some methods are not discussed at all. There are many works on CPP that share a connection to our work. However, to include all of them would not fit within 9 pages. We had to make a selection and choose the most related ones. We did not include Caley et al. (2019) as it tackles a slightly different problem, robot search (i.e. find the exit) instead of covering the area completely. Shrestha et al. (2019) presents and interesting approach for the same task and we thank the reviewer for this reference, we will include it in the related work.

Here follows additional replies.

The noise in the built maps are not fully realistic. As mentioned early on page 4, we believe that our approach can be used with an off-the-shelf SLAM method, removing the need for known pose. In this setting, the agent can learn and adapt to the noise characteristics during training. That our approach works well on noise-free data / data with simulated noise is a necessary condition for future real-world applications. The evaluation of our method on physical robot systems with realistic, noisy sensing will be subject of a future manuscript.

It would be good to build the maps considering the noise using a realistic robot simulator, e.g. in ROS. We agree that this would be highly interesting, although ROS is not necessarily fully realistic as it does not have a full notion of continuous time. Evaluations on real robots would be preferable to any simulation.

Why use different methods to compare omnidirectional/non-omnidirectional exploration? We simply compared the methods on the task setup described in their respective code implementations. We will provide links to the code repositories used in the appendix.

The standard deviation should be included, e.g. in Table 1. We will do our best to do multiple runs for the standard deviation, although we can not promise that they will finish during the discussion period.

It would be good to include coverage over time in the omnidirectional case in the appendix. Good suggestion. Although, the T90 and T99 metrics used in Explore-Bench convey information part of such a plot.

How does a multi-scale map compare to a single map with high enough w and h? In large environments, using a single map is not feasible as the computational cost is O(n^2). For example, with our current setup with 4 maps that span an area of size 76.8x76.8 m2, the training step time is 40 ms. With a single map spanning only 19.2x19.2 m2 using the same pixel resolution as the finest scale, the training step time is 2500 ms. This would increase the total training time by roughly two orders of magnitude. Thus, a multi-scale map is actually necessary for large-scale environments. We will clarify this part in the paper.

Could an adaptive scale be included? As you mention, the training needs to be done with specific scales. We believe the most practical way is to simply train with sufficiently many scales to cover the maximum size for a particular use case. If the model is deployed in a small area, the larger scales would not contain any frontier points in the far distance, but the agent can still cover the area by utilizing the smaller scales. Increasing the represented area by adding more scales is fairly cheap, as the computational cost is O(log(n)). We will add such a discussion to the appendix.

The impact of normalizing the distance measurements should be discussed. Good point. With this normalization, the training is tied to a specific sensor range. However, the map representation is more flexible, and does in theory also contain the information of the raw lidar data. So excluding the sensor feature extractor in Figure 4 would in theory generalize to any sensor setup. We will add this discussion to the appendix.

It is good to provide an intuition on how to set the parameters. Good point. We will describe the parameters in more detail and provide an intuition on how to set them in the appendix.

We thank the reviewer for their valuable suggestions on improving the clarity, motivation and analysis. We are also encouraged by the positive feedback. We address the concerns below.

What is the reason for choosing SAC over other RL methods? In our understanding, SAC is the standard method for continuous RL, and has been used successfully in robot navigation [1]. It also has high sample efficiency, which is important for future real-world experiments.

[1] de Jesus et al. "Soft Actor-Critic for Navigation of Mobile Robots", Journal of Intelligent and Robotic Systems, 2021.

What is the motivation for the MLP baseline? The purpose of the MLP baseline is to evaluate the effect of the inductive biases in the CNN/SGCNN architectures. Note that the MLP architecture even has more parameters, 3.2M compared to 0.8M for the CNNs, due to the initial fully connected layer. This tells us that the inductive biases are indeed necessary.

Figure 4 is missing the frontier maps. Yes, we realized, we will update the figure accordingly.

It is unclear what x3 and x4 mean in Figure 4. We can see that, we will update the caption explaining that they refer to the number of conv and fully connected layers.

Perfect observations and noise-free pose might limit practical utility. As mentioned early on page 4, we believe that our approach can be used with an off-the-shelf SLAM method, removing the need for known pose. In this setting, the agent can learn and adapt to the noise characteristics during training. That our approach works well on noise-free data / data with simulated noise (see below) is a necessary condition for future real-world applications. The evaluation of our method on physical robot systems with realistic, noisy sensing will be subject of a future manuscript.

The scale of the noise isn’t completely clear. We measured the average position error for the SLAM method used in the CPP methods under comparison, and applied a similar noise to our method to get a fair comparison.

Experiments on high-fidelity simulators. We agree that this would be highly interesting, although evaluations on real robots are preferable to any simulation.

What is the inference time? The model inference time is 5 ms on a laptop (i5-520M CPU, no GPU), and 2 ms on a high-performance cluster node (6226R CPU, T4 GPU). As our network is fairly lightweight it can run in real time. The time for updating the maps and constructing the multi-scale map representation etc. is 57/9 ms for exploration/mowing on the laptop, and 19/3 ms for exploration/mowing on the cluster node. All map updates are performed locally, resulting in high scalability. We will add this analysis to the appendix.

What is the collision frequency? For exploration, it varied between once every 100-1000 seconds, which is roughly once every 50-500 meters. For lawn mowing, it varied between once every 150-250 seconds, which is roughly once every 30-50 meters. However, the vast majority of collisions were near-parallel, and we didn’t see any head on collisions. The practical implications are very different between these cases. We will add this analysis to the appendix.

The word “environment dynamics” is confusing, it should be “agent dynamics”. By “environment dynamics” we meant to convey aspects that do not only depend on the properties of the agent, such as wheel slip or moving obstacles.

In the POMDP definition, the probability of transitioning to s_t should only depend on the previous state and action. This is true, the state should not depend on all previous states and actions leading up to the new state (which we do not violate), we will update this.

Did you experiment with other reward formulations? Yes, we did. We tried a positive goal reward for reaching the goal coverage, and a negative truncation reward, but these gave no effect. We will include them in the appendix.

How does the performance scale to much larger environments? More maps or higher resolution is required, right? Yes, more maps or higher resolution would be needed for much larger environments. More maps would be most feasible, as the computational cost is O(log(n)). For example, our current setup with 4 maps spans an area of size 76.8x76.8 m2 with 4096 pixels. Increasing the number of maps to 6 would increase the computational cost by 50% while spanning more than 1x1 km2 in 6144 pixels.