This paper deals with reactive motion planning for a manipulator robot that is required to grasp objects on a conveyor belt. The system is composed of - a conveyor belt moving at constant speed, - a 7 degree-of-freedom manipulator robot - an object put on the conveyor belt, and - an RGBD sensor that detects and localizes the object on the conveyor belt. Upon detection of an object, the system plans a motion for the robot in order to grasp the object and starts executing the motion. During execution, the sensor provides a more accurate perception of the object position. The robot then needs to replan a new path starting downstream along the original path and going to the new goal state. In order to be able to plan motions in bounded time, the authors propose to precompute a data-structure containing a lot of paths, and to search this data-structure at execution-time. The main contributions of the paper are 1. the construction of the above mentioned data-structure, 2. a proof of bounded search time once the data-structure is computed. Finally, the approach is validated in simulation and on a real PR2 robot. The main idea of the paper can be summarized as follows. Given a number $n_{goal}$ of discretized goal states, and $n$ a number of possible starting states, precomputing a data-structure that provides for each pair (initial state, goal state) a path requires to store in memory $n.n_{goal}$ paths. The paper proposes to compute a set of paths that share the same starting part for many goal states, thus reducing the value of $n$. The idea is interesting and seems to be efficient, according to the experimental results and according to comparisons with other approaches. The implementation on a real robot makes the work clearly more valuable. However, the paper suffers a few shortcomings that are described below. 1. The authors do not provide any expression of the size of the data structure built with their method with respect to the number of goal states and number of discretized times along the motions. They provide such a expression for the brute force method: $O(n_{goal}^{l})$. They only give the value of 20MB in the evaluation section. Note moreover that the simple fact to store a set of paths in a roadmap (graph) makes the complexity decrease from $n^2$ where $n$ is the number of states, to $n.k$ where $k$ is the average number of neighbors of the nodes. For big roadmaps, $k$ is much smaller than $n$. 2. The proof provided in IV.E is short and simple. Basically searching a path in a precomputed roadmap is always bounded in time and therefore the title is somewhat misleading. 3. The continuity of the velocity is not guaranteed. This might be a problem for real industrial applications where the conveyor belt is much faster. Below are few minor comments. The motion primitives used are not clearly defined in the paper. Why not using linear interpolations ? Algorithm 1: there is a confusion between $G^{cov}$, $G^{uncov}$, $G^{'cov}$, and $G^{'uncov}$. Line 5 for instance, $G^{cov}$ should be replaced by $G^{uncov}$.

The paper addresses an interesting problem. However, the discussion of previous work is not complete and fair, as I'm pretty sure one can modify existing work on replanning using PRM/RRT to achieve the objectives stated in this paper, see also my point 1 below. 1) The main concern I have with this paper is that there is no discussion on the completeness of the algorithm. The proof of Lemma 1 (completeness) is omitted "due to lack of space"!!! Yet, it seems pretty clear that the algorithm is not complete. For example, in algorithm 4, if the iteration of line 20 (t <- t -\delta_t) is performed until t < t_curr, then the algorithm fails. This point is critical since there's no use having a constant-time planning algorithm if one has no guarantee of success rate. For example: another algorithm could return "Nil" all the time (thereby provably constant time) for a success rate of 0%. So it's always a matter of trade-off between planning time and success rate. Here, one would expect, at least, a proof that the proposed algorithm is complete given some bounds on t_curr, T_bound. 2) Since the task at hand is time-critical, the motions are expected to be very fast, saturating the velocity and acceleration bounds of the robot to minimize execution time. However, it seems that this paper does not take into account such bounds. For example, the state space considered does not include the current velocity. This is particularly important during "latching", as switching between different trajectories may easily violate velocity/acceleration bounds. 3) In general, I found that the paper was not very well written. The notations are not consistent. For example, there are \pi, \Pi, \Pi(s,t,g), \Pi_s, i->j... coexisting, which is very confusing. Key notions (e.g. how "latching" is done, proof of completeness,...) are skipped.