×

Solving non-linear constraint satisfaction problems involving time-dependent functions. (Solving non-linear constraint satisfaction problems involving time-dependant functions.) (English) Zbl 1302.65122

Summary: We consider the resolution of non-linear constraint satisfaction problems where the variables of the systems are trajectories (functions from \(\mathbb R\) to \(\mathbb R^n\)). We introduce the notion of tubes as intervals of functions, for which the lower and upper bounds are trajectories with respect to the inclusion. We then define basic operators and prove propositions verified by tubes. We show the possibility to build contractors on tubes and propagate constraints to solve problems involving time-dependant functions as the unknown variables. We show that the approach is particularly powerful when inter-temporal equations (e.g. delays) are involved. Finally, in order to illustrate the principle and efficiency of the approach, several test cases are provided.

MSC:

65G40 General methods in interval analysis
65G30 Interval and finite arithmetic
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Moore R.E.: Methods and Applications of Interval Analysis. SIAM, Philadelphia (1979) · Zbl 0417.65022
[2] Jaulin L., Kieffer M., Didrit O., Walter E.: Applied Interval Analysis. Springer, Berlin (2001) · Zbl 1023.65037
[3] Thrun S., Bugard W., Fox D.: Probabilistic Robotics. MIT Press, Cambridge (2005) · Zbl 1081.68703
[4] Jaulin L.: Range-only SLAM with occupancy maps; a set-membership approach. IEEE Trans. Robot. 27(5), 1004-1010 (2011)
[5] Bars, F.L., Bertholom, A., Sliwka, J., Jaulin, L.: Interval slam for underwater robots; a new experiment. In: NOLCOS 2010, Italy (2010)
[6] Drocourt, C., Delahoche, L., Brassart, B.M.E., Clerentin, A.: Incremental construction of the robot’s environmental map using interval analysis. In: Global Optimization and Constraint Satisfaction: Second International Workshop, COCOS 2003, vol. 3478, pp. 127-141 (2005) · Zbl 1076.68596
[7] Bethencourt, A., Jaulin, L.: 3d reconstruction using interval analysis on the kinect device coupled with an imu. Int. J. Adv. Robot. Syst. 10 (2013). http://www.intechopen.com/books/international_journal_of_advanced_robotic_systems/3d-reconstruction-using-interval-methods-on-the-kinect-device-coupled-with-an-imu · Zbl 1114.93060
[8] Delanoue, N., Jaulin, L., Cottenceau, B.: Using interval arithmetic to prove that a set is path-connected. Theor. Comput. Sci. Special issue: Real Numbers and Computers 351(1), 119-128 (2006) · Zbl 1087.68068
[9] Aubin J., Frankowska H.: Set-Valued Analysis. Birkhäuser, Boston (1990) · Zbl 0713.49021
[10] Abdallah F., Gning A., Bonnifait P.: Box particle filtering for nonlinear state estimation using interval analysis. Automatica 44(3), 807-815 (2008) · Zbl 1283.93262
[11] Chabert G., Jaulin L.: Contractor programming. Artif. Intell. 173, 1079-1100 (2009) · Zbl 1191.68628
[12] Drevelle, V., Bonnifait, P.: High integrity GNSS location zone characterization using interval analysis. In: ION GNSS (2009) · Zbl 1348.93082
[13] Berz M., Makino K.: Verified integration of odes and flows using differential algebraic methods on high-order Taylor models. Reliab. Comput. 4(3), 361-369 (1998) · Zbl 0976.65061
[14] Davey, B.A., Priestley, H.A.: Introduction to Lattices and Order. Cambridge University Press, London (2002). ISBN: 0521784514 · Zbl 1002.06001
[15] Gollamudi, S., Nagaraj, S., Kapoor, S., Huang, Y.-F.: Set-membership state estimation with optimal bounding ellipsoids. In: International Symposium on Information Theory and its Applications (1996) · Zbl 1026.93015
[16] Kurzhanski A., Valyi I.: Ellipsoidal Calculus for Estimation and Control. Birkhäuser, Boston (1997) · Zbl 0865.93001
[17] Milanese, M., Norton, J., Piet-Lahanier, H., Walter, E.(eds.) : Bounding Approaches to System Identification. Plenum Press, New York (1996) · Zbl 0845.00024
[18] Aubry C., Desmare R., Jaulin L.: Loop detection of mobile robots using interval analysis. Automatica 49(2), 463-470 (2013) · Zbl 1259.93078
[19] Araya, I., Neveu, B., Trombettoni, G.: Exploiting common subexpressions in numerical CSPs. In: Proceedings of Constraint Programming, CP. LNCS, vol. 5202, pp. 342-357 (2008)
[20] Ceberio, M., Granvilliers, L.: Solving nonlinear systems by constraint inversion and interval arithmetic. In: Artificial Intelligence and Symbolic Computation, vol. 1930. LNCS, vol. 5202, pp. 127-141 (2001) · Zbl 1042.68127
[21] Chernousko F.L.: State Estimation for Dynamic Systems. CRC Press, Boca Raton (1994) · Zbl 0830.93032
[22] Schweppe F.C.: Recursive state estimation: unknown but bounded errors and system inputs. IEEE Trans. Autom. Control 13(1), 22-28 (1968)
[23] Jaulin L.: Nonlinear bounded-error state estimation of continuous-time systems. Automatica 38, 1079-1082 (2002) · Zbl 1026.93015
[24] Bravo J., Alamo T., Camacho E.: Robust mpc of constrained discrete-time nonlinear systems based on approximated reachable sets. Automatica 42, 1745-1751 (2006) · Zbl 1114.93060
[25] Combastel, C.: A state bounding observer for uncertain non-linear continuous-time systems based on zonotopes. In: CDC-ECC’05 (2005)
[26] Cross, E.A., Mitchell, I.M.: Level set methods for computing reachable sets of systems with differential algebraic equation dynamics. In: American Control Conference, 2008, pp. 2260-2265. IEEE (2008)
[27] Althoff, M., Krogh, B.H.: Reachability analysis of nonlinear differential-algebraic systems. Autom. Control IEEE Trans. 59(2), 371-383 (2014). doi:10.1109/TAC.2013.2285751 · Zbl 1360.93082
[28] Nedialkov, N.: Interval tools for odes and daes. In: 12th GAMM-IMACS International Symposium on Scientific Computing, Computer Arithmetic and Validated Numerics, 2006, SCAN 2006, pp. 4-4 (2006)
[29] Bouissou, O., Chapoutot, A., Djoudi A.: Enclosing temporal evolution of dynamical systems using numerical methods, In: 5th NASA Formal Methods Symposium, NFM 2013. NASA Ames Research Center, Moffett Field, CA, USA (2013)
[30] Bethencourt A., Jaulin L.: Cooperative localization of underwater robots with unsynchronized clocks. Paladyn J. Behav. Robot. 4(4), 233-244 (2013)
[31] Bethencourt, A.: Interval analysis for swarm localization. Application to underwater robotics. PhD dissertation, Universite de Breatgne Occidental, Brest, France (2014)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.