We consider the problem of computing the smallest contact forces, with point-contact friction model, that can hold an object in equilibrium against a known external applied force and torque. It is known that the force optimization problem (FOP) can be formulated as a semidefinite programming problem (SDP) or a second-order cone problem (SOCP), and thus, can be solved using several standard algorithms for these problem classes. In this paper, we describe a custom interior-point algorithm for solving the FOP that exploits the specific structure of the problem, and is much faster than these standard methods. Our method has a complexity that is linear in the number of contact forces, whereas methods based on generic SDP or SOCP algorithms have complexity that is cubic in the number of forces. Our method is also much faster for smaller problems. We derive a compact dual problem for the FOP, which allows us to rapidly compute lower bounds on the minimum contact force and certify the infeasibility of a FOP. We use this dual problem to terminate our optimization method with a guaranteed accuracy. Finally, we consider the problem of solving a family of FOPs that are related. This occurs, for example, in determining whether force closure occurs, in analyzing the worst case contact force required over a set of external forces and torques, and in the problem of choosing contact points on an object so as to minimize the required contact force. Using dual bounds, and a warm-start version of our FOP method, we show how such families of FOPs can be solved very efficiently.

We describe a technique for reconstructing probable occluded surfaces from 3D range images. The technique exploits the fact that many objects possess shape symmetries that can be recognized even from partial 3D views. Our approach identifies probable symmetries and uses them to attend the partial 3D shape model into the occluded space. To accommodate objects consisting of multiple parts, we describe a technique for segmenting objects into parts characterized by different symmetries. Results are provided for a real-world database of 3D range images of common objects, acquired through an active stereo rig

As an adlunct to mechamcal program verification, it is desirable to partmlly mechamze mductwe assertion synthesis.It is generally beheved that mechanical synthesis must be confined to simple assertions or simple extensions to programmer supphed assertions since the general problem of synthesis reqmres deep insight into the program's operation This paper confirms and quantifies this behef A class {R} of programs Is described for which the inductive assertions can be produced directly Then, by extending this class, a new class is obtained for which assertion synthesis reqmres at least nondetermlnlSUC polynomial t~me In fact a specific subset is shown to be NP-complete This yields two results, First, since nondetermimstlc polynomial ume ~s strongly conlectured to require determlmstlc exponenual time, it appears that the general problem of asserUon synthesis Is at least exponentml.Second, the extension from the class {R} is thus shown to be a cause of this time complexity The result is a better understanding of the difficulty of assertion synthesis and its cause KEY WORDS AND PHRASES synthesizing inducuve asseruons, program venficaUon, prowng programs correct, loop lnvarlants, mduct~on ca CATEGOrieS 3 64, 4 19, 4 22, 5.21, 5 24, 5,25 1 IntroducttonIn recent years there'has been considerable work in mechanical program verification, principally using the method of inductive assertions [8].As the explicit specification of inductive assertions by the programmer ts a tedious and error-prone task, much attention has been given to the subproblem of synthesizing, completing, and debugging inductive assertions [1-3, 5-7, 9, 10, 13, 14, 17-19].It seems plausible that practical success will come of this work in the following sense: A mechanical verification system will ultimately be able to accept a program with obvious or relatively unimportant assertions omitted, fill in the details, and verify the program.This raises the question as to whether assertion synthesis is inherently confined to filling in details or whether, on the contrary, it is possible to synthesize assertions by a uniform procedure.In stating this question it is necessary to exercise care since (a) verifying the synthesized assertions requires theorem proving which, for all but the simplest domains, is not uniformly decidable, and (b) assertion synthesis can always be carried out by generating all well-formed formulas as trial assertions.In view of these two caveats, a better phrasing of the question is: Suppose some program with a complete set of inducttve assertions can be verified or rejected in some time N. What can be said concerning the vertfication or reiectton time if the inducuve assertlons are omitted?The principal result of this paper is showing that at least nondeterministic polynomial time is required in the worst case.Since it is strongly conlectured that nondeterministic polynomial time requires deterministic exponential time [12], tt is very likely that assertion synthesis can add exponential ttme to verification.The second result of this paper is a characterization of the circumstances which make assertion synthesis difficult To this end, we exhibit a class {R} of programs for which correct assertions can be obtained directly from the input/output specifications Then, by violating one of the rules Copyrxght

Most current approaches to mechanical program verification transform a program and its specifications into first-order formulas and try to prove these formulas valid. Since the first-order predicate calculus is not decidable, such approaches are inherently limited. This paper proposes an alternative approach to program verification: correctness proofs are constructively established by proof justifications written in an algorithmic notation. These proof justifications are written as part of the program, along with the executable code and correctness specifications. A notation is presented in which code, specifications, and justifications are interwoven. For example, if a program contains a specification 3x P(x), the program also contains a justification that exhibits the particulat value of x that makes P true. Analogously, justifications may be used to state how universally quantified formulas are to be instantiated when they are used as hypotheses. Programs so justifiled may be verified by proving quantifier-free formulas. Additional classes of justifications serve related ends. Formally, justifications reduce correctness to a decidable theory. Informally, justifications establish the connection between the executable code and correctness specifications, documenting the reasoning on which the correctness is based.

Program development often proceeds by transforming simple, clear programs into complex, involuted, but more efficient ones. This paper examines ways this process can be rendered more systematic. We show how analysis of program performance, partial evaluation of functions, and abstraction of recursive function definitions from recurring subgoals can be combined to yield many global transformations in a methodical fashion. Examples are drawn from compiler optimization, list processing, very high level languages, and APL execution.

It is shown that specifications of program performance can be formally verified. Formal verification techniques, in particular, the method of inductive assertions, can be adapted to show that a program's maximum or mean execution time is correctly described by specifications supplied with the program. To formally establish the mean execution time, branching probabilities are expressed using inductive assertions which involve probability distributions. Verification conditions are formed and proved which establish that if the input distribution is correctly described by the input specifications, then the inductive assertions correctly describe the probability distributions of the data during execution. Once the inductive assertions are shown to be correct, branching probabilities are obtained and mean computation time is computed.

This paper is concerned with proving properties of programs which use data structures. The goal is to be able to prove that all instances of a class (e.g. as defined in Simula) satisfy some property. A method of proof which achieves this goal, generator induction , is studied and compared to other proof rules and methods: inductive assertions, recursion induction, computation induction, and, in some detail, structural induction. The paper concludes by using generator induction to prove a characteristic property of an implementation of hashtables.

Newer programming languages for artificial intelligence extend the class of available control regimes beyond simple hierarchical control. In so doing, a key issue is using a model that clearly exhibits the relation between modules, processes, access environments, and control environments. This paper presents a model which is applicable to diverse languages and presents a set of control primitives which provide a concise basis on which one can define almost all known regimes of control.

Program development often proceeds by transforming simple, clear programs into complex, involuted, but more efficient ones. This paper examines ways this process can be rendered more systematic. We show how analysis of program performance, partial evaluation of functions, and abstraction of recursive function definitions from recurring subgoals can be combined to yield many global transformations in a methodical fashion. Examples are drawn from compiler optimization, list processing, very high-evel languages, and APL execution.

Describes a prototype system Vista which provides assistance in synthesizing correct inductive assertions. Given only the source program, it is able to generate a useful class of assertions automatically. For a larger class, it is able to extend partial inductive assertions supplied by the programmer to form complete assertions from which it proves program correctness. Its synthesis methods include: symbolic evaluation in a weak interpretation, combining output assertions with loop exit information to obtain trail loop assertions, and extracting information from proofs which fail in order to determine how assertions should be strengthened.

To carry out significant program optimization, it is necessary to know what properties hold at each program unit. Frequently the properties of interest form a partially ordered set with a minimum condition (i.e., well-founded). When this occurs, it is possible to directly compute the properties that can be attached to program units and, optionally, to expand the program text to obtain a strong assignment of properties. Techniques are presented for property computation in iterative and recursive programs. Application to a variety of property sets is discussed.

Most programming languages allow the use of free variables in procedures. The mechanism for connecting such free variables with their intended meanings has significant impact on the convenience of the language for the programmer and the efficiency of the resulting programs. The EL1 programming language in the ECL programming system provides a closure mechanism which allows the programmer considerable control over the binding of free variables and serves as an aid to efficient implementation. In this paper, the closure mechanism for EL1 is explained, its rationale presented, and various applications displayed.

A technique for compactifying garbage collection is presented. The method is applicable to very general classes of nodes, works even when pointers point into the middle of nodes, and preserves arbitrarily complex re-entrant pointer structures.

An algorithm for tracing during garbage collection of list structure is presented. It requires only one bit for each level of doubly branching structure traced. Compared to existing trace algorithms, it generally requires less storage-often, substantially less.

Complexity classes of formal languages defined by time- and tape-bounded Turing acceptors are studied with the aim of showing sufficient conditions for these classes to be AFLs and to be principal AFLs.