TL;DR
This paper introduces a novel model checker for ConGolog, a high-level robot control language that handles concurrency, prioritization, and interrupts. The key innovation is a technique that leverages XSB tabling and the $\mu$-calculus to verify complex, non-terminating programs within a finite time, addressing a significant challenge in formal verification.
What Problem Does This Paper Address?
Verifying the correctness of robot control programs is crucial for ensuring safety and reliability. ConGolog, a sophisticated programming language designed for robot control, introduces complexities like concurrent processes, prioritized execution, and handling of external events (exogenous actions). These features, combined with the inherent non-determinism and potential for non-termination in such programs, make manual verification extremely difficult, if not impossible. The core challenge is to develop an automatic method that can prove properties of these complex, potentially infinite-running programs in a practical, finite amount of time.
Methods
The authors propose a model checker that applies techniques from formal verification, specifically drawing inspiration from branching-time temporal logics and the $\mu$-calculus. To handle non-termination and non-determinism, they employ greatest and least fixed-point constructions, similar to those used in the propositional $\mu$-calculus. A significant aspect of their approach is the use of XSB's tabling mechanism. This allows them to manage the infinite computational tree generated by ConGolog programs. Their key insight is that it's sufficient to verify properties on a finite fragment of this tree, exploiting repetition patterns in system and program states. They also model the environment by creating a special program that non-deterministically chooses and executes exogenous actions.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Bridging the Gap: The paper tackles the difficult problem of verifying non-terminating programs in finite time, a critical hurdle for real-world applications like robotics.
- Exploiting Repetition: The core idea is that infinite computations in ConGolog programs exhibit repeating patterns in states. By detecting these repetitions, the model checker can avoid infinite loops and converge to a verification result.
- XSB Tabling as a Solution: The authors cleverly leverage the tabling feature of the XSB logic programming system. This allows them to store and reuse intermediate results, effectively pruning the search space and enabling termination for verification.
- Formalizing Properties: The use of the $\mu$-calculus provides a powerful way to formally express complex properties, such as fairness (e.g., ensuring no requests are ignored indefinitely), which are essential for robot behavior.
Key Results
The paper describes a model checker that is in progress. While specific quantitative results are not presented, the authors demonstrate the approach with examples like an elevator controller. They show how their model checker can distinguish between a program that might lead to starvation (ignoring requests) and one that guarantees all requests are eventually served. The primary qualitative result is the successful application of XSB tabling and $\mu$-calculus techniques to enable finite-time verification of non-terminating ConGolog programs.
Limitations and Future Work
The authors acknowledge that their model checker is currently restricted to non-terminating programs. They also note occasional unexpected and contradictory results, which they suspect might be related to known bugs in the XSB system. Future work includes a deeper understanding of XSB to resolve these issues, proving the correctness of their implementation, and extending the model checker to handle a finite number of fluents (properties of the world that change with actions), which is a current restriction.
Summary updated