Comparision of the Kinodynamic and Topological Path Searching

[ZhangBihui0311]

@ZbyLGsc Thank you for this great work~ I would like to know the different applicability (or the different trajectory style) between these two Path Searching methods, based on your flight tests. What i can see is that there are a lot of circular obstacles in the Topological simulation but not in the Kinodynamic one. Also, will there be a third method in the future~~?

[ZbyLGsc]

@ZhangBihui0311: This is a rather good question. In short: kinodynamic path searching finds promising solutions in both local and global planning. Topological path searching leads to stronger guarantee of feasibility and optimality, but is limited to local replanning problem.

The advantage of kinodynamic method is that in practice it finds promising paths, even in large maps where the start and end points are distant. However, since it searches in the discrete control space, the solution may not be satisfactory enough. In high-speed navigation in unknown environments, we desire local replanning that can always generate high-quality trajectories. Topological path searching is designed for this purpose, and it outperforms kinodynamic search. However, it may not scale well for global planning, since the number of distinctive topological classes grows rapidly with the number of obstacles.

The circular obstacles are introduced to better illustrate the capability of the topological method, since in 2.5D map there will not be many distinctive topological classes.

[ZbyLGsc]

There will be some extensions, but not another kind of path searching. We will add a perception-aware planning module into the current planner.

[ZhangBihui0311]

Thank you !!! @ZbyLGsc