Interval analysis for certified numerical solution of problems in robotics

Merlet, J. P.

International Journal of Applied Mathematics and Computer Science, Tome 19 (2009) no. 3, pp. 399-412

Résumé

Interval analysis is a relatively new mathematical tool that allows one to deal with problems that may have to be solved numerically with a computer. Examples of such problems are system solving and global optimization, but numerous other problems may be addressed as well. This approach has the following general advantages: (a) it allows to find solutions of a problem only within some finite domain which make sense as soon as the unknowns in the problem are physical parameters; (b) numerical computer round-off errors are taken into account so that the solutions are guaranteed; (c) it allows one to take into account the uncertainties that are inherent to a physical system. Properties (a) and (c) are of special interest in robotics problems, in which many of the variables are parameters that are measured (i.e., known only up to some bounded errors) while the modeling of the robot is based on parameters that are submitted to uncertainties (e.g., because of manufacturing tolerances). Taking into account these uncertainties is essential for many robotics applications such as medical or space robotics for which safety is a crucial issue. A further inherent property of interval analysis that is of interest for robotics problems is that this approach allows one to deal with the uncertainties that are unavoidable in robotics. Although the basic principles of interval analysis are easy to understand and to implement, this approach will be efficient only if the right heuristics are used and if the problem at hand is formulated appropriately. In this paper we will emphasize various robotics problems that have been solved with interval analysis, many of which are currently beyond the reach of other mathematical approaches.

Détail

Keywords: interval analysis, uncertainties, robotics
Mots-clés : analiza interwałowa, niepewność, robotyka

Bibliographie

[1] Ashokaraj, I., Tsourdos, A., Silson, P. and White, B. A. (2004). Sensor based robot localisation and navigation: Using interval analysis and extended Kalman filter, Proceedings of the 5th Asian Control Conference, Melbourne, Australia.

[2] Carreras, C. and Walker, I. (2001). Interval methods for faulttree analysis in robotics, IEEE Transactions on Reliability 50(1): 3-11.

[3] Chablat, D., Wenger, P. and Merlet, J.-P. (2004). A comparative study between two three-dof parallel kinematic machines using kinetostatic criteria and interval analysis, Proceedings of the 11th IFToMM World Congress on the Theory of Machines and Mechanisms, Tianjin, China, pp. 1209-1213.

[4] Chablat, D., Wenger, P. and Merlet, J.-P. (2002). Workspace analysis of the Orthoglide using interval analysis, Advances in Robot Kinematics, Caldes de Malavalla, Spain, pp. 397-406.

[5] Clerentin, A., Delahoche, L., Brassart, E. and Izri, S. (2003). Imprecision and uncertainty quantification for the problem of mobile robot localization, Proceedings of the Performance Metrics for Intelligent Systems Workshop, Gaithersburg, MD, USA.

[6] Daney, D., Andreff, N., Chabert, G. and Papegay, Y. (2006). Interval method for calibration of parallel robots: A visionbased experimentation, Mechanism and Machine Theory 41(8): 929-944.

[7] Das, I. and Dennis, J. (1997). A closer look at drawbacks of minimizing weighted sums of objectives for Pareto set generation in multicriteria optimization problem, Structural Optimization 14: 63-69.

[8] Didrit, O. (1997). Analyse par intervalles pour l'automatique; Résolution globale et garantie de problèmes non linéaires en robotique et en commande robuste, Ph.D. thesis, Université Paris XI Orsay, Paris.

[9] Dietmaier, P. (1998). The Stewart-Gough platform of general geometry can have 40 real postures, Advances in Robot Kinematics, Strobl, Austria, pp. 7-16.

[10] Drocourt, C., Delahoche, L., Brassart, E., Marhic, B. and Clerentin, A. (2003). Incremental construction of the robot's environmental map using interval analysis, Proceedings of the 2nd International Workshop on Global Constrained Optimization and Constraint Satisfaction (COCOS'03), Lausanne, Switzerland.

[11] Fang, H. and Merlet, J.-P. (2005). Multi-criteria optimal design of parallel manipulators based on interval analysis, Mechanism and Machine Theory 40(2): 151-171.

[12] Gough, V. and Whitehall, S. (1962). Universal tire test machine, Proceedings of the 9th International Technical Congress F.I.S.I.T.A., London, UK, Vol. 117, pp. 117-135.

[13] Hansen, E. (2004). Global Optimization Using Interval Analysis, Marcel Dekker, New York, NY.

[14] Hubert, J. and Merlet, J.-P. (2008). Singularity analysis through static analysis, Advances in Robot Kinematics, Batz/mer, France, pp. 13-20.

[15] Innocenti, C. (2001). Forward kinematics in polynomial form of the general Stewart platform, ASME Journal of Mechanical Design 123(2): 254-260.

[16] Jaulin, L., Kieffer, M., Didrit, O. and Walter, E. (2001). Applied Interval Analysis, Springer-Verlag, Heidelberg.

[17] Kearfott, R. and Manuel, N. I. (1990). INTBIS, a portable interval Newton/Bisection package, ACM Transactions on Mathematical Software 16(2): 152-157.

[18] Kieffer, M., Jaulin, L., Walter, E. and Meizel, D. (2000). Robust autonomous robot localization using interval analysis, Reliable Computing 6(3): 337-362.

[19] Kreinovich, V. (2000). Optimal finite characterization of linear problems with inexact data, Technical Report CS-00-37, University of Texas at El Paso, TX.

[20] Kreinovich, V., Lakeyev, A., Rohn, J. and Kahl, P. (1998). Computational Complexity and Feasibility of Data Processing and Interval Computations, Kluwer, Dordrecht.

[21] Lebbah, Y., Michel, C., Rueher, M., Merlet, J.-P. and Daney, D. (2004). Combining local consistencies with a new global filtering algorithm on linear relaxations, SIAM Journal of Numerical Analysis, 42(2076).

[22] Merlet, J.-P. (2004). Solving the forward kinematics of a Goughtype parallel manipulator with interval analysis, International Journal of Robotics Research 23(3): 221-236.

[23] Merlet, J.-P. (2000). ALIAS: An interval analysis based library for solving and analyzing system of equations, SEA, Toulouse, France.

[24] Merlet, J.-P. (1989). Singular configurations of parallel manipulators and Grassmann geometry, International Journal of Robotics Research 8(5): 45-56.

[25] Merlet, J.-P. and Donelan, P. (2006). On the regularity of the inverse jacobian of parallel robot, Advances in Robot Kinematics, Ljubljana, Slovenia, pp. 41-48.

[26] Moore, R. (1979). Methods and Applications of Interval Analysis, SIAM Studies in Applied Mathematics, SIAM, Philadelphia, PA.

[27] Neumaier, A. (1990). Interval Methods for Systems of Equations, Cambridge University Press, Cambridge.

[28] Neumaier, A. (2001). Introduction to Numerical Analysis, Cambridge University Press, Cambridge.

[29] Piazzi, A. and Visioli, A. (2000). Global minimum-jerk trajectory planning of robot manipulators, Transactions on Industrial Electronics 47(1): 140-149.

[30] Rao, R., Asaithambi, A. and Agrawal, S. (1998). Inverse kinematic solution of robot manipulators using interval analysis, Journal of Mechanical Design 120(1): 147-150.

[31] Redon, S. et al. (2004). Fast continuous collision detection for articulated models, Proceedings of the 9th ACM Symposium on Solid Modeling and Applications, Genoa, Italy, pp. 145-156.

[32] Rex, G. and Rohn, J. (1998). Sufficient conditions for regularity and singularity of interval matrices, SIAM Journal on Matrix Analysis and Applications 20(2): 437-445.

[33] Ronga, F. and Vust, T. (1992). Stewart platforms without computer?, Proceedings of the Conference on Real Analytic and Algebraic Geometry, Trento, Italy, pp. 197-212.

[34] Rouillier, F. (1995). Real roots counting for some robotics problems, in B. R. J-P. Merlet (Ed.), Computational Kinematics, Kluwer, Dordrecht, pp. 73-82.

[35] Seignez, E., Kieffer, M., Lambert, A., Walter, E. and Maurin, T. (2005). Experimental vehicle localization by boundederror state estimation using interval analysis, IEEE/RJS IROS, Edmonton, Canada.

[36] Tapia, R. (1971). The Kantorovitch theorem for Newton's method, American Mathematic Monthly 78(1.ea): 389-392.

[37] Wampler, C. (1996). Forward displacement analysis of general six-in-parallel SPS (Stewart) platform manipulators using soma coordinates, Mechanism and Machine Theory 31(3): 331-337.

[38] Wu, W. and Rao, S. (2004). Interval approach for the modeling of tolerances and clearances in mechanism analysis, Journal of Mechanical Design 126(4): 581-592.