An Effective Algorithm for Finding Shortest Paths in Tubular Spaces

Round 1

Reviewer 1 Report

I think this is the natural approach to detecting the shortest path
betwen two points within a 3D curvy tube which can be represented as 
the disjoint union of discs oriented perpendicularly to a smooth central curve.
I only suggest  

(1) minor changes in the Introduction

(2) doing computational experiment 8 with a Spiral in Table 2 with
at least 4 twists. 

As for (1): I am convinced that the most appropriate paradigm for the
ESP (Euclidean shortest path) is stretching a non-elastic chord 
between to points within a tube even for the authors.
They do not mention this basic example from old classical mechanics,
though it seems that the proposed algorithm tries to imitate the
procedure of stretching in a simplified variational method.

If possible please mention the chord paradigm or
explain your reason shortly if you do not agree that this would be the 
proper basic example.
  

I find the remarks about the applications mentioned at the beginning 
of the Introduction are too ambitious. For instance a it would be
problematic (dangerous) for a flying drone to touch the surface.
Notice that we can pass to a narrower tube to overcome this difficulty,
but there are much more problems for driving a drone in realistic circumstance
which make questionable the hints for the view points of a purely 
geometrical optimization. 
[Indeed the analogous 2D problem of finding the best 
lap time in an advanced Formula 1 simulator applied to an existing circuit
is studied recently very intensively with AI (artificial intelligence) methods.
It is well-known that to follow the geometrically shortest path produces a
very non-competitive lap time.
If we regard drones, analogous problems appear with need of more governing parameters.]

I suggest that some more sincere and modest words should be payed 
to the limits of the applications with the purely geometric algorithm of the paper.
This will not compromise the value of the work
which I find very good with thoroughly elaborated examples.

As for (2): With more twists in the spiral, 
the differences between results with
various methods become very striking.
I can understand that this would require a bigger figure,
but the outcome is worth to see. 

 

Author Response

Please see the attachment.

Author Response File: Author Response.pdf

Reviewer 2 Report

The present paper studies the euclidean shortest path problem in tubular spaces. For instance, imagine a drone that wants to fly though a tunnel system and shall pick the shortest path. A new algorithm is presented that is based directly on visibility properties of the tubes. This is in contrast to standard techniques that layout a graph on the tube system and find a shortest path in it with, say, Dijkstra. In particular, this makes the algorithm reactive, i.e., the drone does not have to know the tube system in advance.

Strengths

1. The paper is generally well written and provides a complete introduction to the field.
2. The theoretical arguments seem mostly correct (see notes below).
3. Results are supported by experiments, which are scientifically sound and illustrated with helpful figures.

Weaknesses

1. Code and experimental data are not available, which makes it impossible to verify the experiments. Implementation details are missing (for instance, much can be done wrong in implementing Dijkstra efficiently, so it would be interesting to know which library was used).
2. The complete Section 3 is somewhat strange. As far as I understand it, the algorithm is: Transform your tube system into a mesh graph and run a “from the shelf” Dijkstra on it.
   • I don’t get why a Lemma by Dijkstra is cited or why Algorithm 1 is presented.
   • It is claimed that Dijkstra runs in O(|A|) time, which is generally not the case (it runs in O(|V|log|V|+|A|) at best). So if this is, for this particular application, any different, it has to be proven in a Lemma.
   • The authors state that this method “generally [produce] a zigzag line”. From the pictures in the experiments, I cannot see this (and I also don’t see why Dijkstra should produce these).
   • It is claimed that making the mesh finer results in significantly slower running times. This should be stated (and proven) more formally.
3. The “proposed method” is based on some Lemmas proven by the authors (which seem correct). However, the submission is lacking a Theorem that proves that the algorithm as a whole is correct. The run time is not analyzed either.
4. In my opinion, the authors exaggerate a little. It is correct that their method, in these experiments, is faster than Dijkstra and provided slightly better results. However, it is not like “Dijkstra produces a somewhat catastrophic route”. Concerning the running time, I assume much can be done by tuning the Dijkstra implementation. For instance, I am rather surprised that plain Dijkstra is used and not A* (which clearly can benefit from the geographic information in the tube system).

Conclusion

All in all I like the paper: the proposed solution seems reasonable and the experiments provide some evidence that it is compatible with known techniques. However, the authors have to improve their formal statements about the algorithms a bit and should highlight and discuss in more details the pros (and also cons) when the new algorithm is compared to other ones. The discussion in the evaluation of the experiments seems to exaggerate the results a bit – what is not necessary, as they are solid anyway (for instance, I think that the algorithm is reactive is more crucial than the slightly better performance).

Notes to the Authors

• l.86 It would be good if you would state concretely what “shorter, smoother, and faster” means in this context.
• I was wondering whether the Dijkstra approach has any guarantees on the quality of the path (with respect to the granularity of the mesh). Maybe it would be good to discuss this a little within the paper.
• l.94 “searching ESP” sounds wired.
• l.105 This seems to be a part of a sentence that nowhere starts.
• l.150 “We then” – when?
• l.154 hereafter “is” based
• l.199 newline after QED
• l.268 “the this” -> “this”
• l.207 “is belong to” -> “belongs to”
• l.299-303 A bit to much slang for my taste.
• l.323 A theoretical bound would be important nevertheless (your algorithm may only be fast on the instances you have generated).
• l.334-343 This seems like a motivation to use A* instead of Dijkstra.
• l.345 The location within the tube – should that not be a feature of Dijkstra? You could give nodes in the center of the tube more priority (by adapting the edge weights accordingly). Please clarify, why Dijkstra fails here and the proposed solution does not.
• l.372 “lava tubes on astronomical objects” sounds cool, but maybe also a little exaggerated?
• l.379 “is much better than Dijkstra” I cannot conclude that from the provided experiments.

Author Response

Please see the attachment.

Author Response File: Author Response.pdf

Reviewer 3 Report

The authors of this paper presented a novel algorithm for solving the ESP problem inside tubular spaces based on its geometric properties. Computational results were conducted on various types of tubular spaces. The authors showed that the achieved efficiency of the proposed algorithm is much better than Dijkstra’s one and it   provided smoother and more precise results with a faster calculation speed than one obtained by Dijkstra’s algorithm with the same grid. 

Simply, the proposed method has certain novelty and contribution. The paper presentation is also good. The evaluation experiments are comprehensive. I recommend to accept this paper with a proofreading, and also rechecking mathematical expressions, and notations. 

Author Response

Please see the attachment.

Author Response File: Author Response.pdf

Round 2

Reviewer 2 Report

The authors have modified the manuscript and reflected upon most of my concerns. In particular:

• The source code is now available at GitHub.
• Details about the runtime of the implemented version of Dijkstra were added.
• The exaggeration of the comparison was reduced (what is good, the algorithm is strong enough).

I am now in favor of accepting the paper after minor revision, but I think the following points should be discussed within the manuscript shortly (which should not be a problem, because the authors discussed it already in the provided cover letter):

1. The source code / GitHub link should be referenced within the paper.
2. The reasoning of choosing / not choosing A* should be discussed briefly (in particular, it is not obvious to me why geometric heuristics in a tubular space are not monotone, in which case A* would be optimal and accuracy would not be a problem).
3. Now that I see that you implementation of Dijkstra can be seen as BFS and runs in linear time, I am curious why it is so slow. I understand that the run time depends on the granularity of the mesh and, thus, the number of nodes in the network. But, from the experiments, the correlation does not become clear. I belief the following table would be a great extension to the paper (if it can easily be generated with the existing experimental setup): Take 2 or 3 of the surfaces from Table 2 (say 1 und 8) (these become the rows) and write for various granularities (the columns) of the mesh the total number of nodes in it, the time to compute the mesh, the time to run Dijkstra on it, and the obtained accuracy. (My guess is that for very low granularities this will be faster than the proposed method, but will become intractable quickly. I also assume that the bootleneck is actually the generation of the mesh and not the BFS, which would be an interesting observation for further research.)

Author Response

Please see the attachment

Author Response File: Author Response.pdf