Difference between Single-Query and Multiple Query Algorithms?

Question

I am spending a lot of time in understanding these two concepts, because in several papers that I read, they define them differently, and I do not know exactly what is the meaning of the two different queries.

I understand, from what I read, that single query algorithm, like RRT, they only compute a single path between an starting point and a goal point, and anything else.

However, multiple query algorithms, like PRM, you construct a roadmap, and once you have it, you can query it for multiples paths, I mean, you can select two points (init and goal), and then if you change your opinion you can change these two points with others.

But I do not know if this approach is correct. I would love that someone can explain me in layman terms.

Answer 1

I think what you said in your question is correct so far.

Single and multi query planning refers to the number of planning tasks you are about to execute. That means, the number of different paths you want to plan, given an unchanging environment.

PRM constructs a graph-structure (roadmap) of the free configuration space. Instead of exploring the c space every time you plan a path like RRT does, PRM is able to use the generated roadmap multiple times as long as the environment it is based on does not change.

Answer 2

To understand this concept, you can compare two famous algorithms, Probabilistic Roadmap (PRM) and RRT.

RRT is a single query algorithm. In other words, it can evaluate a single path when two points are selected, i.e., the path between start and goal point. RRT forms a tree-like structure that branches out in all directions sampling and connecting the points(waypoints).

On the other hand, PRM is more like a planner than a typical algorithm. It forms a graph-like structure that spreads but doesn't branch-like RRT. It can be used to find multiple paths/queries from start to goal. The biggest advantage of using PRM is that it retains the graph structure and reuses it every time you select two points. Although RRT guarantees a feasible path but at the expense of optimality.

Hope this helps.

Answer 3

Modern pathplanning algorithm like PRM and RRT allow to find a trajectory on a given map which avoids obstacles. Especially under realtime condition in computer games the techniques are providing an efficient path from start to goal. Apart from pathplanning itself, graph-based planning can be used as a meta-algorithm for motion planning in general.

RRT is faster than PRM because the number of calculated edges are lower. RRT was designed with minimalism in mind, which means that graph extension is seen as costly and should be avoided under all circumstances. In contrast, PRM invests more resources in building a complete graph which includes more nodes and more edges.

For the solver ontop of an existing graph, the PRM algorithm is more comfortable to query, because the number of possible paths is higher. Additional constraints can be matched more easily, while RRT has the problem that the shortest path looks in most cases a bit strange. The spline isn't the shortest one but goes a bit uncommon through the map. That is the reason, why RRT needs a postprocessing step to smooth the path.