With the widespread application of robots in aerospace, medicine, automation, and other fields, their motion safety is essential for the well-being of humans and the accomplishment of vital socially beneficial programs. Conventional robot hardware and software designs mainly rely on experiential knowledge and manual testing to ensure safety, but this fails to cover all possible testing paths and adds risks. Alternatively, formal, mathematically rigorous verifications can provide predictable and reliable guarantees of robot motion safety. To demonstrate the feasibility of this approach, we formalize the mathematical coordinate transformation of a robot’s rigid-body kinematics using the Coq Proof Assistant to verify the correctness of its theoretical design. First, based on record-type matrix formalization, we define and verify a robot’s spatial geometry by constructing formal expressions of the matrix’ Frobenius norm, trace, and inner product. Second, we divide rotary motion into revolution and rotation construct and provide their formal definitions. Next, we formally verify the rotational matrices of angle conventions (e.g., roll–pitch–yaw and Euler), and we complete the formal verification of the Rodriguez formula to formally verify the correctness of the motion theory in specific rotating kinematics problems. The formal work of this paper has a variety of essential applications and provides a generalizable kinematics analysis framework for robot control system verification. Moreover, it paves the way for automatic programming capabilities.
29 April 2024 in Journal of Logical and Algebraic Methods in Programming
Matrix inversion algorithms are ubiquitous in engineering, computer science, and other disciplines. While formal verification exists for individual inversion methods, a comprehensive verification alongside directly executable algorithms within a theorem prover is lacking for two key methods: inversion via the adjoint matrix (InvAM) and inversion via Gaussian elimination (InvGE). This paper addresses this gap by offering constructive implementations and rigorous formal verifications of both InvAM and InvGE within the Coq proof assistant, thus enabling reliable and ready-to-use computation of matrix inverses directly in the Coq environment. To facilitate the verification process, we introduce FinMatrix, a formal model for matrices. This model defines a vector as a function from a finite set to a type of elements and encapsulates a matrix as a vector of vectors. We formalize a comprehensive set of operations and mathematical properties pertinent to vectors and matrices. Leveraging this foundation, we formalize determinant theory and the Gaussian elimination algorithm, essential components of the matrix inversion process. We then proceed to formalize the aforementioned matrix inversion algorithms, InvAM and InvGE. To demonstrate the practicality of our formal verification, we addressed a system of linear equations within Coq using three distinct methods: Cramer’s rule, and inversion via InvAM or InvGE. We also illustrated the process for determining the inverse of a symbolic matrix with partial automation. Furthermore, we extracted OCaml code from Coq and performed preliminary performance tests. Our formalized algorithms set a benchmark for verifying additional matrix inversion methods and lay the groundwork for formalizing more advanced matrix theories.
As the scale and complexity of chips continue to increase, chip design becomes increasingly challenging. Designers typically need multiple iterations to achieve satisfactory results, but the substantial time required for each modification exacerbates the time pressure in the chip design process. Incremental methods are an effective technique to shorten the development iteration time. Therefore, this paper proposes a module-based incremental layout technique utilizing the hierarchical structure of the unflattened netlist. We have developed an incremental EDA tool for mid-version evaluation, covering the process from RTL to placement DEF. This tool enables faster synthesis and layout, assisting designers in assessing the feasibility of the current RTL design, thereby accelerating the estimation of the PPA (Power, Performance, and Area) during version iterations. It aids in making better choices for RTL design and logic synthesis, consequently shortening the chip development iteration time.