Interval constraint solving for camera control and motion planning

ABSTRACT

Many problems in robust control and motion planning can be reduced to either finding a sound approximation of the solution space determined by a set of nonlinear inequalities, or to the "guaranteed tuning problem" as defined by Jaulin and Walter, which amounts to finding a value for some tuning parameter such that a set of inequalities be verified for all the possible values of some perturbation vector. A classical approach to solving these problems, which satisfies the strong soundness requirement, involves some quantifier elimination procedure such as Collins' Cylindrical Algebraic Decomposition symbolic method. Sound numerical methods using interval arithmetic and local consistency enforcement to prune the search space are presented in this article as much faster alternatives for both soundly solving systems of nonlinear inequalities, and addressing the guaranteed tuning problem whenever the perturbation vector has dimension 1. The use of these methods in camera control is investigated, and experiments with the prototype of a declarative modeler to express camera motion using a cinematic language are reported and commented upon.

REFERENCES

• 1: Abdallah, C., Dorato, P., Yang, W., Liska, R., and Steinberg, S. 1996. Applications of quantifier elimination theory to control theory. In Proceedings of the 4th IEEE Mediterranean Symposium on Control and Automation (Malene, Crete, Greece). 340--345.
• 2: Abrams, S. and Allen, P. K. 1997. Computing camera viewpoints in an active robot work-cell. IBM Res. rep. RC 20987. IBM Research Division, Yorktown Heights, NY.
• 3: Alefeld, G. and Herzberger, J. 1983. Introduction to Interval Computations. Academic Press Inc., New York, NY.
• 4: Arijon, D. 1976. Grammar of the Film Language. Hastings House Publishers, New York, NY.
• 5: Armengol, J., Travé-Massuyès, L., Vehí, J., and Sáinz, M. A. 1998. Modal interval analysis for error-bounded semiqualitative simulation. In 1r Congrés Català d'Intelligència Artificial. 223--231.
• 6: Frédéric Benhamou, Interval Constraint Logic Programming, Selected Papers from Constraint Programming: Basics and Trends, p.1-21, May 16-20, 1994
• 7: Frédéric Benhamou, Heterogeneous Constraint Solving, Proceedings of the 5th International Conference on Algebraic and Logic Programming, p.62-76, September 25-27, 1996
• 8: Frédéric Benhamou , Frédéric Goualard , Laurent Granvilliers , Jean-François Puget, Revising hull and box consistency, Proceedings of the 1999 international conference on Logic programming, p.230-244, November 1999, Las Cruces, New Mexico, United States
• 9: F. Benhamou , D. McAllester , P. van Hentenryck, CLP(intervals) revisited, Proceedings of the 1994 International Symposium on Logic programming, p.124-138, November 1994, Symposia, Melbourne
• 10: Benhamou, F. and Older, W. J. 1997. Applying interval arithmetic to real, integer and Boolean constraints. J. Logic Programm. 32, 1, 1--24.
• 11: IEEE Computer Graphics and Applications, Where Am I? What Am I Looking At?, IEEE Computer Graphics and Applications, v.8 n.4, p.76-81, July 1988 [doi>10.1109/38.7751]
• 12: Marc Christie , Eric Languénou , Laurent Granvilliers, Modeling Camera Control with Constrained Hypertubes, Proceedings of the 8th International Conference on Principles and Practice of Constraint Programming, p.618-632, September 09-13, 2002
• 13: Hélène Collavizza , François Delobel , Michel Rueher, Extending Consistent Domains of Numeric CSP, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.406-413, July 31-August 06, 1999
• 14: George E. Collins, Hauptvortrag: Quantifier elimination for real closed fields by cylindrical algebraic decomposition, Proceedings of the 2nd GI Conference on Automata Theory and Formal Languages, p.134-183, May 20-23, 1975
• 15: Glorianna Davenport , Thomas Aguirre Smith , Natalio Pincever, Cinematic Primitives for Multimedia, IEEE Computer Graphics and Applications, v.11 n.4, p.67-74, July 1991 [doi>10.1109/38.126883]
• 16: Steven Mark Drucker, Intelligent camera control for graphical environments, Massachusetts Institute of Technology, Cambridge, MA, 1994
• 17: Steven M. Drucker , Tinsley A. Galyean , David Zeltzer, CINEMA: a system for procedural camera movements, Proceedings of the 1992 symposium on Interactive 3D graphics, p.67-70, June 1992, Cambridge, Massachusetts, United States [doi>10.1145/147156.147166]
• 18: Drucker, S. M. and Zeltzer, D. 1994. Intelligent camera control in a virtual environment. In Proceedings of Graphics Interface '94. Canadian Information Processing Society, Banff, Alta., Canada, 190--199.
• 19: Ebers, J. J. and Moll, J. L. 1954. Large-scale behaviour of junction transistors. IRE Procs. 42, 1761--1772.
• 20: Emiris, I. Z. and Mourrain, B. 1999. Computer algebra methods for studying and computing molecular conformations. Algorithmica 25, 2/3, 372--402.
• 21: R. T. Farouki , V. T. Rajan, On the numerical condition of polynomials in Berstein form, Computer Aided Geometric Design, v.4 n.3, p.191-216, Nov., 1987 [doi>10.1016/0167-8396(87)90012-4]
• 22: Gardeńes, E. and Trepat, A. 1980. Fundamentals of SIGLA, an interval computing system over the completed set of intervals. Comput. 24, 2--3, 161--179.
• 23: Gardeñes, E. H. and Mielgo, H. 1986. Modal intervals: Reasons and ground semantics. In Interval Mathematics. Lecture Notes in Computer Science, vol. 212. Springer-Verlag, Berlin, Germany.
• 24: Garloff, J. and Graf, B. 1999. Solving strict polynomial inequalities by Bernstein expansion. In The Use of Symbolic Methods in Control System Analysis and Design, N. Munro, Ed. The Institution of Electrical Engineers, London, England, 339--352.
• 25: Michael Gleicher , Andrew Witkin, Through-the-lens camera control, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.331-340, July 1992
• 26: Laurent Granvilliers , Frédéric Benhamou, Progress in the Solving of a Circuit Design Problem, Journal of Global Optimization, v.20 n.2, p.155-168, June 2001 [doi>10.1023/A:1011266226870]
• 27: Hansen, E. R. 1992. Global Optimization Using Interval Analysis. Pure and Applied Mathematics. Marcel Dekker Inc, New York, NY.
• 28: Djamila Haroud , Boi Faltings, Global Consistency for Continuous Constraints, Proceedings of the Second International Workshop on Principles and Practice of Constraint Programming, p.40-50, May 02-04, 1994
• 29: Hong, H. and Buchberger, B. 1991. Speeding-up quantifier elimination by Gröbner bases. Tech. Rep. 91-06. RISC-Linz, Johannes Kepler University, Linz, Austria.
• 30: IEEE. 1985. IEEE standard for binary floating-point arithmetic. Tech. rep. IEEE Std 754-1985. Institute of Electrical and Electronics Engineers, Piscataway, NJ. Reaffirmed 1990.
• 31: Jardillier, F. and Languénou, é. 1998. Screen-space constraints for camera movements: the virtual cameraman. In Eurographics'98 proceedings, N. Ferreira and M. Göbel, Eds. Vol. 17. Blackwell Publishers, Oxford, UK, 175--186.
• 32: Luc Jaulin , Eric Walter, Set inversion via interval analysis for nonlinear bounded-error estimation, Automatica (Journal of IFAC), v.29 n.4, p.1053-1064, July 1993 [doi>10.1016/0005-1098(93)90106-4]
• 33: Luc Jaulin , Éric Walter, Guaranteed tuning, with application to robust control and motion planning, Automatica (Journal of IFAC), v.32 n.9, p.1217-1221, Aug. 1996
• 34: Jirstrand, M. 1995. Cylindrical algebraic decomposition---an introduction. Tech. Rep. 1995-10-18, Department of Electrical Engineering, Linköping University, Linköping, Sweden.
• 35: Kaucher, E. W. 1980. Interval analysis in the extended interval space IR. Comput. (Supplementum) 2, 33--49.
• 36: Kutsia, T. and Schicho, J. 1999. Numerical solving of constraints of multivariate polynomial strict inequalities. Tech. rep. 99-31. RISC Institute, Johannes Kepler University, Linz, Austria.
• 37: Vincent Lefèvre , Jean-Michel Muller , Arnaud Tisserand, Toward Correctly Rounded Transcendentals, IEEE Transactions on Computers, v.47 n.11, p.1235-1243, November 1998 [doi>10.1109/12.736435]
• 38: Mackworth, A. K. 1977. Consistency in networks of relations. Art. Intell. 1, 8, 99--118.
• 39: Markov, S. 1995. On directed interval arithmetic and its applications. J. Univers. Comput. Sci. 1, 7, 514--526.
• 40: Keith Meintjes , Alexander P. Morgan, Chemical equilibrium systems as numerical test problems, ACM Transactions on Mathematical Software (TOMS), v.16 n.2, p.143-151, June 1990 [doi>10.1145/78928.78930]
• 41: Moore, R. E. 1966. Interval Analysis. Prentice-Hall, Englewood Cliffs, NJ.
• 42: Neumaier, A. 1990. Interval Methods for Systems of Equations. Encyclopedia of Mathematics and its Applications, vol. 37. Cambridge Unversity Press, Cambridge, U.K.
• 43: Older, W. J. and Vellino, A. 1990. Extending Prolog with constraint arithmetic on real intervals. In Proceedings of IEEE Canadian Conference on Electrical and Computer Engineering. IEEE Computer Society Press, New York, NY.
• 44: Petru Pau , Josef Schicho, Quantifier elimination for trigonometric polynomials by cylindrical trigonometric decomposition, Journal of Symbolic Computation, v.29 n.6, p.971-983, June 2000 [doi>10.1006/jsco.1999.0352]
• 45: Puget, J.-F. 1994. A C++ implementation of CLP. In Proceedings of the Singapore Conference on Intelligent Systems (SPICIS'94, Singapore).
• 46: Jean-François Puget , Pascal Van Hentenryck, A Constraint Satisfaction Approach to a Circuit Design Problem, Journal of Global Optimization, v.13 n.1, p.75-93, 1998 [doi>10.1023/A:1008236911603]
• 47: Rademacher, H. A. 1948. On the accumulation of errors in processes of integration on high-speed calculating machines. Annals Comput. Laor. Harvard Univ. 16, 176--185. Cited in Stoer and Bulirsch {1993}.
• 48: Sam, J. 1995. Constraint consistency techniques for continuous domains. Ph.D. dissertation. école polytechnique fédérale de Lausanne, Lausanne, Switzerland.
• 49: Shary, S. P. 1995. Algebraic solutions to interval linear equations and their applications. In Numerical Methods and Error Bounds, Proceedings of the IMACS-GAMM International Symposium on Numerical Methods and Error Bounds, G. Alefeld and J. Herzberger, Eds. Akademie Verlag, Oldenburg, Germany, 224--233.
• 50: Shary, S. P. 1999. Interval Gauss-Seidel method for generalized solution sets to interval linear systems. In MISC'99---Workshop on Applications of Interval Analysis to Systems and Control (Girona, Spain). 51--65.
• 51: Ken Shoemake, Animating rotation with quaternion curves, Proceedings of the 12th annual conference on Computer graphics and interactive techniques, p.245-254, July 1985
• 52: John M. Snyder, Interval analysis for computer graphics, Proceedings of the 19th annual conference on Computer graphics and interactive techniques, p.121-130, July 1992
• 53: Stoer, J. and Bulirsch, R. 1993. Introduction to Numerical Analysis, 2nd ed. in Texts in Applied Mathematics, vol. 12. Springer, Heidelberg, Germany.
• 54: Sunaga, T. 1958. Theory of an interval algebra and its application to numerical analysis. In Research Association of Applied Geometry Memoirs of the Unifying Study of Basic Problems in Engineering and Physical Sciences by Means of Geometry, K. Kondo, Ed. Vol. 2. Gakujutsu Bunken Fukyu-Kai, Japan, Chapter Miscellaneous Subjects II, 547--564.
• 55: Tarabanis, K. 1990. Automated sensor planning and modeling for robotic vision tasks. Tech. rep. CUCS-045-90. Columbia University, New York, NY.
• 56: Turing, A. M. 1948. Rounding-off errors in matrix processes. Quart. J. Mech. 1, 287--308. Cited in Wilkinson {1963}.
• 57: Pascal Van Hentenryck , David McAllester , Deepak Kapur, Solving Polynomial Systems Using a Branch and Prune Approach, SIAM Journal on Numerical Analysis, v.34 n.2, p.797-827, April. 1997 [doi>10.1137/S0036142995281504]
• 58: Van Hentenryck, P., Michel, L., and Deville, Y. 1997b. Numerica: A Modeling Language for Global Optimization. MIT Press, Cambridge, MA.
• 59: Waltz, D. L. 1975. Understanding line drawings of scenes with shadows. In The Psychology of Computer Vision, P. H. Winston, B. Horn, M. Minsky, and Y. Shirai, Eds. McGraw-Hill, New York, NY, Chap. 2, 19--91.
• 60: Ward, A. C., Lozano-Pérez, T., and Seering, W. P. 1989. Extending the constraint propagation of intervals. In Proceedings of IJCAI'89. 1453--1458.
• 61: James H. Wilkinson, Rounding Errors in Algebraic Processes, Dover Publications, Incorporated, 1994

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Constraints

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Interval arithmetic

  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.1 Multimedia Information Systems
          Subjects: Animations

General Terms:
Algorithms, Reliability, Theory

Keywords:
Camera control, inner approximation, interval constraint, universal quantifier