Interval analysis for certified numerical solution of problems in robotics

Jean-Pierre Merlet

International Journal of Applied Mathematics and Computer Science (2009)

  • Volume: 19, Issue: 3, page 399-412
  • ISSN: 1641-876X

Abstract

top
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.

How to cite

top

Jean-Pierre Merlet. "Interval analysis for certified numerical solution of problems in robotics." International Journal of Applied Mathematics and Computer Science 19.3 (2009): 399-412. <http://eudml.org/doc/207944>.

@article{Jean2009,
abstract = {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.},
author = {Jean-Pierre Merlet},
journal = {International Journal of Applied Mathematics and Computer Science},
keywords = {interval analysis; uncertainties; robotics},
language = {eng},
number = {3},
pages = {399-412},
title = {Interval analysis for certified numerical solution of problems in robotics},
url = {http://eudml.org/doc/207944},
volume = {19},
year = {2009},
}

TY - JOUR
AU - Jean-Pierre Merlet
TI - Interval analysis for certified numerical solution of problems in robotics
JO - International Journal of Applied Mathematics and Computer Science
PY - 2009
VL - 19
IS - 3
SP - 399
EP - 412
AB - 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.
LA - eng
KW - interval analysis; uncertainties; robotics
UR - http://eudml.org/doc/207944
ER -

References

top
  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. Zbl1123.70005
  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. Zbl0953.70006
  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. Zbl1103.90092
  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. Zbl1023.65037
  17. Kearfott, R. and Manuel, N. I. (1990). INTBIS, a portable interval Newton/Bisection package, ACM Transactions on Mathematical Software 16(2): 152-157. Zbl0900.65152
  18. Kieffer, M., Jaulin, L., Walter, E. and Meizel, D. (2000). Robust autonomous robot localization using interval analysis, Reliable Computing 6(3): 337-362. Zbl0978.70004
  19. Kreinovich, V. (2000). Optimal finite characterization of linear problems with inexact data, Technical Report CS-0037, University of Texas at El Paso, TX. Zbl1080.15002
  20. Kreinovich, V., Lakeyev, A., Rohn, J. and Kahl, P. (1998). Computational Complexity and Feasibility of Data Processing and Interval Computations, Kluwer, Dordrecht. Zbl0945.68077
  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. Zbl1323.70039
  26. Moore, R. (1979). Methods and Applications of Interval Analysis, SIAM Studies in Applied Mathematics, SIAM, Philadelphia, PA. Zbl0417.65022
  27. Neumaier, A. (1990). Interval Methods for Systems of Equations, Cambridge University Press, Cambridge. Zbl0715.65030
  28. Neumaier, A. (2001). Introduction to Numerical Analysis, Cambridge University Press, Cambridge. Zbl0980.65001
  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. Zbl0924.15003
  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. Zbl0827.70003
  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. Zbl0900.70069
  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. Zbl0215.27404
  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. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.