Introducing Project Cane

I just added "Project Cane" [1] into Google code. The goal of that project is to implement and explore different local navigation methods and bet them against each other.

I also hope to gather a good selection of realistic test cases in the process. Something that I have seen to cause problems before and something that turns out while testing new code. Eventually the result of this project will end up as a module for Detour.

The code is quick and dirty. If you want to reuse the code in your project I encourage to reimplement it. If you have something to contribute, say, port of existing local navigation method, some test cases, your favorite steering method, let me know and I'll give you access.


The current implementation includes the TOI sampling based method I have been blogging about recently. It works in many cases pretty well, but produces ugly results under certain cases and with certain parameters.

One of the biggest drawback is the sampling. For example try out the example chicken_corridor.txt with fewer samples (say, 32) and it gets rather ugly. It seems to be crucial to get the tiny features right, in order to make the local navigation robust in constrained areas.

Another thing that is causing weird behavior is that the method makes the assumption that moving at constant speed is a good thing. While it makes sense (and some papers refer to that assumption too), in some cases it just creates movement which is not what I expect.

I'll be adding my HRVO implementation as soon as I get it to work with segments too.

_

In general, I'm not quite satisfied with any method I have tried so far. Interestingly, many of then can be tuned so that they will solve the specific tests cases nicely. And usually the tuning has to do with how to handle tiny details in velocity handling.

In certain cases it is beneficial to filter out higher frequency details to create steady and flicker free velocity selection, but sometimes the right solution can only be found by looking at the fine details (such as the case mentioned above).

Usually my attention in this kind of cases turns into some sort of hierarchical methods. Translating that to the above problem, I could be possible to downsample the sampled TOIs and use that to select a rough sector where the velocity will be selected from and then use the more accurate samples to refine the selection. Velocity selection is really hard problem. No wonder that most of the studies eventually resort to search (i.e. see: VFH, VFH+, VFH*).

After a steady progress of research, I feel that I'm back to square one again, maybe a bit wiser this time around.

___

[1] Yes, I'm fan of Md. House and local navigation is like poking around with a cane anyways.