More Web Proxy on the site http://driver.im/

article

Interval constraint solving for camera control and motion planning

Authors:

Frédéric Benhamou,

Frédéric Goualard,

Éric Languénou,,

Marc ChristieAuthors Info & Claims

ACM Transactions on Computational Logic (TOCL), Volume 5, Issue 4

Pages 732 - 767

https://doi.org/10.1145/1024922.1024927

Published: 01 October 2004 Publication History

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]

Benhamou, F. 1995. Interval constraint logic programming. In Constraint Programming: Basics and Trends: 1994 Châtillon Spring School, Châtillon-sur-Seine, France, May 16--20, 1994, A. Podelski, Ed. Lecture Notes in Computer Science, vol. 910. Springer-Verlag, Berlin, Germany, 1--21.

[7]

Benhamou, F. 1996. Heterogeneous constraint solving. In Proceedings of the 5th International Conference on Algebraic and Logic Programming (ALP'96). Lecture Notes in Computer Science, vol. 1139. Springer-Verlag, Aachen, Germany, 62--76.

[8]

Benhamou, F., Goualard, F., Granvilliers, L., and Puget, J.-F. 1999. Revising hull and box consistency. In Proceedings of the 16th International Conference on Logic Programming (ICLP'99). MIT Press, Cambridge, MA. 230--244.

[9]

Benhamou, F., McAllester, D., and Van Hentenryck, P. 1994. CLP(Intervals) revisited. In Proceedings of the International Symposium on Logic Programming (ILPS'94). MIT Press, Cambridge, MA, 124--138.

[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]

Blinn, J. 1988. Where am I? What am I looking at? IEEE Comput. Graph. Appl. 8, 4 (July), 76--81.

[12]

Christie, M., Languénou, E., and Granvilliers, L. 2002. Modeling camera control with constrained hypertubes. In Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP'2002), P. V. Hentenryck, Ed. Lecture Notes in Computer Science, vol. 2470. Springer-Verlag, Berlin, Germany, 618--632.

[13]

Collavizza, H., Delobel, F., and Rueher, M. 1999. Extending consistent domains of numeric CSP. In Proceedings of the 16th IJCAI. (Stockholm, Sweden). Vol. 1. 406--411.

[14]

Collins, G. E. 1975. Quantifier elimination for real closed fields by cylindrical algebraic decomposition. In Proceedings of the 2nd GI Conference on Automata Theory and Formal Languages. Lecture Notes in Computer Science, vol. 33. Springer, Kaiserslauten, Germany, 134--183.

[15]

Davenport, G., Smith, T. A., and Pincever, N. 1991. Cinematic primitives for multimedia. IEEE Comput. Graph. Appl. 11, 4 (July), 67--74.

[16]

Drucker, S. M. 1994. Intelligent camera control for graphical environments. Ph.D. dessertation. Program in Media Arts and Sciences, School of Architecture and Planning, MIT, Cambridge, MA.

[17]

Drucker, S. M., Galyean, T. A., and Zeltzer, D. 1992. CINEMA: A system for procedural camera movements. In Proceedings of the 1992 Symposium on Interactive 3D Graphics, M. Levoy and E. E. Catmull, Eds. ACM Press, New York, NY, 67--70.

[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]

Farouki, R. T. and Rajan, V. T. 1987. On the numerical condition of polynomials in Bernstein form. Comput. Aided Geom. Des. 4, 191--216.

[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]

Gleicher, M. and Witkin, A. 1992. Through-the-lens camera control. In Comput. Graph. (SIGGRAPH '92 Proceedings, E. E. Catmull, Ed.). 26, 2, 331--340.

[26]

Granvilliers, L. and Benhamou, F. 2001. Progress in the solving of a circuit design problem. J. Global Opt. 20, 2, 155--168.

[27]

Hansen, E. R. 1992. Global Optimization Using Interval Analysis. Pure and Applied Mathematics. Marcel Dekker Inc, New York, NY.

[28]

Haroud, D. and Faltings, B. 1994. Global consistency for continuous constraints. Lecture Notes in Computer Science, vol. 874. Springer-Verlag, Berlin, Germany, 40--50.

[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]

Jaulin, L. and Walter, E. 1993. Set inversion via interval analysis for nonlinear bounded-error estimation. Automatica 29, 4, 1053--1064.

[33]

Jaulin, L. and Walter, E. 1996. Guaranteed tuning with application to robust control and motion planning. Automatica 32, 8, 1217--1221.

[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]

Lefèvre, V., Muller, J.-M., and Tisserand, A. 1998. Towards correctly rounded transcendeatals. IEEE Trans. Comput. 47, 11 (Nov.), 1235--1243.

[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]

Meintjes, K. and Morgan, A. P. 1990. Chemical equilibrium systems as numerical test problems. ACM Trans. Math. Softw. 16, 2 (June), 143--151.

[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]

Pau, P. and Schicho, J. 2000. Quantifier elimination for trigonometric polynomials by cylindrical trigonometric decomposition. J. Symbol. Computat. 29, 6 (June), 971--983.

[45]

Puget, J.-F. 1994. A C++ implementation of CLP. In Proceedings of the Singapore Conference on Intelligent Systems (SPICIS'94, Singapore).

[46]

Puget, J.-F. and Van Hentenryck, P. 1998. A constraint satisfaction approach to a circuit design problem. J. Global Opt. 13, 75--93.

[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]

Shoemake, K. 1985. Animation rotations with quaternion curves. Comput. Graph. Proceedings of SIGGRAPH'83, San Francisco, CA). 19, 3, 245--254.

[52]

Snyder, J. M. 1992. Interval analysis for computer graphics. In Computer Graphics (SIGGRAPH '92 Proceedings, E. E. Catmull, Ed.). 26, 2, 121--130.

[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]

Van Hentenryck, P., McAllester, D., and Kapur, D. 1997a. Solving polynomial systems using a branch and prune approach. SIAM J. Numer. Anal. 34, 2 (April), 797--827.

[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]

Wilkinson, J. H. 1963. Rounding Errors in Algebraic Processes. Prentice-Hall, New Jersey. Reprinted as Dover Publications (1994).

Cited By

Nuger EBenhabib B(2018)Multi-Camera Active-Vision for Markerless Shape Recovery of Unknown Deforming ObjectsJournal of Intelligent and Robotic Systems10.1007/s10846-018-0773-092:2(223-264)Online publication date: 1-Oct-2018
https://dl.acm.org/doi/10.1007/s10846-018-0773-0
Amamra AAmara YBenaissa RMerabti B(2016)Optimal camera path planning for 3D visualisation2016 SAI Computing Conference (SAI)10.1109/SAI.2016.7556011(388-393)Online publication date: Jul-2016
https://doi.org/10.1109/SAI.2016.7556011
Hu JWang YCheng AZhong Z(2015)Sensitivity Analysis in Quantified Interval Constraint Satisfaction ProblemsJournal of Mechanical Design10.1115/1.4029513137:4Online publication date: 1-Apr-2015
https://doi.org/10.1115/1.4029513
Show More Cited By

Index Terms

Interval constraint solving for camera control and motion planning

Recommendations

On H∞ control for linear systems with interval time-varying delay

This paper deals with the problem of delay-dependent robust H"~ control for linear time-delay systems with norm-bounded, and possibly time-varying, uncertainty. The time-delay is assumed to be a time-varying continuous function belonging to a given ...
Delay-range-dependent robust H∞ control for uncertain systems with interval time-varying delays

This paper deals with the problem of delay-range-dependent robust H"~ control for uncertain systems with time-varying delays and norm-bounded parameter uncertainties. The time delay is assumed to be a time-varying continuous function belonging to a ...
Constraint Solving for Proof Planning

Proof planning is an application of AI planning to theorem proving that employs plan operators that encapsulate mathematical proof techniques. Many proofs require the instantiation of variables; that is, mathematical objects with certain properties have ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Computational Logic

ACM Transactions on Computational Logic Volume 5, Issue 4

October 2004

191 pages

ISSN:1529-3785

EISSN:1557-945X

DOI:10.1145/1024922

Issue’s Table of Contents

Copyright © 2004 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 2004

Published in TOCL Volume 5, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

27
Total Citations
View Citations
631
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)1

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Nuger EBenhabib B(2018)Multi-Camera Active-Vision for Markerless Shape Recovery of Unknown Deforming ObjectsJournal of Intelligent and Robotic Systems10.1007/s10846-018-0773-092:2(223-264)Online publication date: 1-Oct-2018
https://dl.acm.org/doi/10.1007/s10846-018-0773-0
Amamra AAmara YBenaissa RMerabti B(2016)Optimal camera path planning for 3D visualisation2016 SAI Computing Conference (SAI)10.1109/SAI.2016.7556011(388-393)Online publication date: Jul-2016
https://doi.org/10.1109/SAI.2016.7556011
Hu JWang YCheng AZhong Z(2015)Sensitivity Analysis in Quantified Interval Constraint Satisfaction ProblemsJournal of Mechanical Design10.1115/1.4029513137:4Online publication date: 1-Apr-2015
https://doi.org/10.1115/1.4029513
(2015)BibliographyAbstract Domains in Constraint Programming10.1016/B978-1-78548-010-2.50013-1(143-158)Online publication date: 2015
https://doi.org/10.1016/B978-1-78548-010-2.50013-1
Korovina MKudinov O(2015)Index Sets as a Measure of Continuous Constraint ComplexityPerspectives of System Informatics10.1007/978-3-662-46823-4_17(201-215)Online publication date: 19-Apr-2015
https://doi.org/10.1007/978-3-662-46823-4_17
Hu JAminzadeh MWang Y(2013)Searching Feasible Design Space by Solving Quantified Constraint Satisfaction ProblemsJournal of Mechanical Design10.1115/1.4026027136:3(031002)Online publication date: 31-Dec-2013
https://doi.org/10.1115/1.4026027
Hsu WZhang YMa K(2013)A Multi-Criteria Approach to Camera Motion Design for Volume Data AnimationIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2013.12319:12(2792-2801)Online publication date: 1-Dec-2013
https://dl.acm.org/doi/10.1109/TVCG.2013.123
Belghith KKabanza FBellefeuille PHartman L(2012)Automated camera planning to film robot operationsArtificial Intelligence Review10.1007/s10462-011-9233-y37:4(313-330)Online publication date: 1-Apr-2012
https://dl.acm.org/doi/10.1007/s10462-011-9233-y
Yeh ILin CChien HLee T(2011)Efficient camera path planning algorithm for human motion overviewComputer Animation and Virtual Worlds10.1002/cav.39822:2-3(239-250)Online publication date: 1-Apr-2011
https://dl.acm.org/doi/10.1002/cav.398
Kim TJung SBaek GKim S(2010)Development of Motion Control Camera Design Based on Wires with Anti-sway MethodInternational Journal of Fuzzy Logic and Intelligent Systems10.5391/IJFIS.2010.10.1.02510:1(25-30)Online publication date: 31-Mar-2010
https://doi.org/10.5391/IJFIS.2010.10.1.025
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents