Розмір шрифту: 

Whenever a robotic mobile platform is being created, it often comes not only to how it should be built but more importantly how it will behave in a task-space? So, to address this issue many algorithms were developed and in different circumstances they show different performance. This is due to the nature of movement (space of feasible motions) of such mobile platform – cars, 6R-manipulators, “mecanum” wheels etc.

However, one of the most universal and robust algorithms is PRM (Probabilistic Road Map) with A* search. The idea behind it is about random sampling points in the task space with subsequent verification of collision-free edges between these points. Such points generally referred to as “nodes” and straight lines connecting them (with no object intersection) – “edges”.
After initialization one wants to know the most optimal path between node a and node b. The “most optimal” path in authors work was specified with respect to distance – the best is the shortest, however it can be easily modified to sustain following criteria: the most energy efficient, path with certain velocity constraints to the robot`s end-effector etc. This task is addressed to the graph search methods which are plentiful and can exhibit different behavior in different challenges. The A* search was used by the author to find the shortest way within a graph, created by PRM.

The author made modifications to the standard PRM algorithm in a way of incorporating a tolerance value to the computation. A tolerance value is a distance, which user want to designate when end-effector should go in a close proximity to some obstacle along the path.

More also, author did slight modification due to computational efficiency. This issue was addressed by the number of interconnected nodes. Of course, one wants all nodes to be connected with the others (omitting those edges, which intersect the obstacles) in order to find an optimal solution (when number of interconnected nodes goes to infinity we are guaranteed to find the shortest path possible). Bearing in mind that sometimes we do not need such level of discretization and want to solve this problem as fast as possible, author has implemented a k-nearest nodes feature. It allows to reduce overall quantity of edges and significantly boost computation speed with respect to k. When someone wants to use this, he must understand the trade-off between quality and speed.

PRM algorithm; A* search, graph search