Verification and testing of mobile robot navigation algorithms: A case study in SPARK

Navigation algorithms are fundamental for mobile robots. While the correctness of the algorithms is important, it is equally important that they do not fail because of bugs in their implementation. Yet, even widely-used robot navigation code lacks proofs of correctness or credible coverage reports from testing. Robot software developers usually point towards the cost of manual verification or lack of automated tools that would handle their code. We demonstrate that the choice of programming language is essential both for finding bugs in the code and for proving their absence. Our re-implementation of three robot navigation algorithms in SPARK revealed bugs that for years have not been detected in their original code in C/C++. For one of the implementations we demonstrate that it is free from run-time errors. Our code and results are available online to encourage uptake by the robot software developers community.