Abstract
Interval Analysis is a mathematical tool that could be used to solve Constraint Satisfaction Problem. It guarantees solutions, and deals with uncertainties. However, Interval Analysis suffers from an overestimation of the solutions, i.e. the pessimism. In this paper, we initiate a new method to reduce the pessimism based on the convex hull properties of BSplines and the Kronecker product. To assess our method, we compute the feasible workspace of a 2D manipulator taking into account joint limits, stability and reachability constraints: a classical Constraint Satisfaction Problem in robotics.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Tay, N.N.W., Saputra, A.A., Botzheim, J., Kubota, N.: Service robot planning via solving constraint satisfaction problem. ROBOMECH J. 3(1), 17 (2016)
Lozano-Pérez, T., Kaelbling, L.P.: A constraint-based method for solving sequential manipulation planning problems. In: 2014 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 3684–3691, September 2014
Fromherz, M.P., Hogg, T., Shang, Y., Jackson, W.B.: Modular robot control and continuous constraint satisfaction. In: Proceedings of IJCAI-01 Workshop on Modelling and Solving Problems with Constraints, pp. 47–56 (2001)
Lengagne, S., Ramdani, N., Fraisse, P.: Planning and fast replanning safe motions for humanoid robots. IEEE Trans. Robot. 27(6), 1095–1106 (2011)
Jaulin, L., Kieffer, M., Didrit, O., Walter, E.: Applied Interval Analysis with Examples in Parameter and State Estimation, Robust Control and Robotics. Springer, London (2001)
Lengagne, S., Vaillant, J., Yoshida, E., Kheddar, A.: Generation of whole-body optimal dynamic multi-contact motions. Int. J. Robot. Res. 17 (2013)
Merlet, J.-P.: Interval analysis and reliability in robotics. Int. J. Reliab. Saf. 3(1–3), 104–130 (2009)
Yokoo, M., Hirayama, K.: Algorithms for distributed constraint satisfaction: a review. Auton. Agents Multi-Agent Syst. 3(2), 185–207 (2000)
Gelle, E., Faltings, B.: Solving mixed and conditional constraint satisfaction problems. Constraints 8(2), 107–141 (2003)
Sunaga, T.: Theory of interval algebra and its application to numerical analysis. RAAG Mem. Ggujutsu Bunken Fukuy-kai 2, 547–564 (1958)
Moore, R.E., Bierbaum, F.: Methods and Applications of Interval Analysis (SIAM Studies in Applied and Numerical Mathematics (Siam Studies in Applied Mathematics). Siam Studies in Applied Mathematics, vol. 2. Soc for Industrial & Applied Math, Philadelphia (1979)
Neumaier, A.: Interval Methods for Systems of Equations. Cambridge University Press, Cambridge (1990)
Pérez-Galván, C., Bogle, I.D.L.: Global optimisation for dynamic systems using interval analysis. Comput. Chem. Eng. 107, 343–356 (2017)
Jiang, C., Han, X., Guan, F., Li, Y.: An uncertain structural optimization method based on nonlinear interval number programming and interval analysis method. Eng. Struct. 29(11), 3168–3177 (2007)
Ma, H., Xu, S., Liang, Y.: Global optimization of fuel consumption in J2 rendezvous using interval analysis. Adv. Space Res. 59(6), 1577–1598 (2017)
Merlet, J.P.: Interval Analysis and Robotics, pp. 147–156. Springer, Heidelberg (2011)
Jaulin, L.: Interval analysis and robotics. In: SCAN 2012, Russia, Novosibirsk (2012)
Rohou, S., Jaulin, L., Mihaylova, L., Le Bars, F., Veres, S.M.: Guaranteed computation of robot trajectories. Robot. Auton. Syst. 93, 76–84 (2017)
Desrochers, B., Jaulin, L.: Minkowski operations of sets with application to robot localization. In: SNR 2017, Uppsala (2017)
Benoît, D., Luc, J.: Computing a guaranteed approximation of the zone explored by a robot. IEEE Trans. Autom. Control 62(1), 425–430 (2017)
Le Bars, F., Bertholom, A., Sliwka, J., Jaulin, L.: Interval SLAM for underwater robots; a new experiment. In: NOLCOS 2010, France, p. XX, September 2010
Wu, J.: Uncertainty analysis and optimization by using the orthogonal polynomials, Ph.D. dissertation (2015)
Netz, L.: Using horner schemes to improve the efficiency and precision of interval constraint propagation (2015)
Schäcke, K.: On the kronecker product (2013)
Loan, C.F.: The ubiquitous kronecker product. J. Comput. Appl. Math. 123(1), 85–100 (2000). Numerical Analysis 2000. Vol. III: Linear Algebra
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Kalawoun, R., Lengagne, S., Bouchon, F., Mezouar, Y. (2019). BSplines Properties with Interval Analysis for Constraint Satisfaction Problem: Application in Robotics. In: Strand, M., Dillmann, R., Menegatti, E., Ghidoni, S. (eds) Intelligent Autonomous Systems 15. IAS 2018. Advances in Intelligent Systems and Computing, vol 867. Springer, Cham. https://doi.org/10.1007/978-3-030-01370-7_39
Download citation
DOI: https://doi.org/10.1007/978-3-030-01370-7_39
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-01369-1
Online ISBN: 978-3-030-01370-7
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)