Comparison of Interval Constraint Propagation Algorithms for Vehicle Localization

I. K. Kueviakoe, A. Lambert, P. Tarroux

LIMSI, CNRS, 91400 Orsay, France; ENS, 45 rue d'ULM, 75230 Paris, France.
LIMSI, CNRS, 91400 Orsay, France; Univ. Paris Sud, IEF, 91400 Orsay, France;.
LIVIC, IFSTTAR, 14 route de la minière, 78000 Versailles,France.

DOI: 10.4236/jsea.2012.512B030                

Abstract

Interval constraint propagation (ICP) algorithms allow to solve problems described as constraint satisfaction problems (CSP). ICP has been successfully applied to vehicle localization in the last few years. Once the localization problem has been stated, a large class of ICP solvers can be used. This paper compares a few ICP algorithms, using the same experimental data, in order to rank their performances in terms of accuracy and computing time.

Keywords

Interval Analysis, Constraint Propagation, Data Fusion, Vehicle Positioning, GPS

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	M. Clowes, “On seeing things,” Artificial intelligence, vol. 2,no. 1, pp. 79–116, 1971.
[2]	D. Waltz, “Understanding line drawings of scenes with shadows,” Psychology of Computer Vision, McGraw-Hill,New York, 1975.
[3]	A. Mackworth, “Consistency in networks of relations,” Artificial intelligence, vol. 8, no. 1, pp. 99–118, 1977.
[4]	H. Gallaire, “Logic programming: Further develop-ments,” in IEEE Symposium on Logic Programming, pp. 88–99, 1985.
[5]	J. Jaffar and J. Lassez, “Constraint logic programming,” in ACM SIGACT-SIGPLAN symposium on Principles of programming languages, pp. 111–119, 1987.
[6]	P. Van Hentenryck, Y. Deville, and C. Teng, “A generic arc-consistency algorithm and its specializations,” Artificial Intelligence, vol. 57, no. 2, pp. 291–321, 1992.
[7]	C. Bessiere, “Arc-consistency and arc-consistency again,” Ar-tificial intelligence, vol. 65, no. 1, pp. 179–190, 1994.
[8]	Z. Yuanlin and R. Yap, “Arc consis-tency on n-ary monotonic and linear constraints,” International Conference on Principles and Practice of Constraint Programming, pp. 470–483, 2000.
[9]	R. Dechter and J. Pearl, “Tree clustering for constraint networks,” Artificial Intelligence, vol. 38, no. 3, pp. 353–366, 1989.
[10]	F. Rossi, C. Petrie, and V. Dhar, “On the equivalence of con-straint satisfaction problems,” in European Confe-rence on Artificial Intelligence, pp. 550–556, 1990.
[11]	R. Mohr, G. Masini, et al., “Good old discrete relaxation,” in European Conference on Artificial Intelligence, pp. 651–656, 1988.
[12]	J. Cleary, “Logical arithmetic,” Future computing systems, vol. 2, no. 2, pp. 125–149, 1987.
[13]	E. Davis, “Constraint propagation with interval la-bels,” Artificial intelligence, vol. 32, no. 3, pp. 281–331, 1987.
[14]	E. Hyvonen, “Constraint rea-soning based on interval arithmetic,” in Internation-al Joint Conference on Artificial Intelligence, pp. 1193–1198, 1989.
[15]	F. Benhamou and W. Older, “Applying interval arithmetic to real, integer, and boolean constraints,” The Journal of Logic Pro-gramming, vol. 32, no. 1, pp. 1–24, 1997.
[16]	F. Benhamou, F. Goualard, L. Granvilliers, and J. Pu-get, “Revising hull and box consistency,” in Int. Conf. on Logic Programming, Citeseer, 1999.
[17]	F. Benhamon, D. McAllester, and P. Van Hentenryck, “Clp (intervals) revisited,” tech. rep., Citeseer, 1994.
[18]	L. Granvilliers, “Towards cooperative interval narrowing,” Frontiers of Com-bining Systems, pp. 18–31, 2000.
[19]	O. Lhomme, “Consistency techniques for numeric csps,” in In-ternational Joint Conference on Artificial Intelli-gence, pp. 232–232,1993.
[20]	A. Gning and P. Bonnifait, “Guaranteed dynamic localization using constraints propagation techniques on real inter-vals,” in IEEE International Conference on Robot-ics and Automation, pp. 1499–1504, 2004.
[21]	B. Vincke, A. Lambert, D. Gruyer, A. Elouardi, and E. Seignez,“Static and dynamic fusion for outdoor ve-hicle localization,” in International Conference on Control Automation Robotics & Vision, pp. 437–442, 2010.
[22]	B. Vincke and A. Lambert, “Enhanced constraints propagation for guaranteed localization predictive step,” in IEEE/RSJ IROS, Workshop on Planning, Perception and Navigation for Intelligent Vehicles, pp. 30–36, 2009.
[23]	L. Jaulin, “Localization of an underwater robot using interval constraint propagation,” International Conference on Principles and Practice of Constraint Programming, pp. 244–255, 2006.
[24]	D. L. Waltz, “Generating semantic descriptions from drawings of scenes with shadows,” PhD thesis, AI Lab, MIT, 1972.
[25]	D. Gruyer, A. Lambert, M. Perrollaz, and D. Gingras, “Experimental comparison of bayesian vehicle positioning methods based on multi-sensor data fusion,” International Journal of Vehicle Autonomous Systems, vol. 10, no. 3-4, 2012.
[26]	G. Chabert and L. Jaulin, “Hull consis-tency under monotonicity,” International Confe-rence on Principles and Practice of Constraint Pro-gramming, pp. 188–195, 2009.
[27]	R. Moore, In-terval analysis. Prentice-Hall Englewood Cliffs, NJ, 1966.
[28]	V. Kreinovich, A. Lakeyev, J. Rohn, and P. Kahl, Computational complexity and feasi-bility of data processing and interval computations. Kluwer Academic Publishers Netherlands, 1998.
[29]	L. Granvilliers and F. Benhamou, “Al-gorithm 852: Realpaver: an interval solver using constraint satisfaction techniques,” ACM Transac-tions on Mathematical Software, vol. 32, no. 1, pp. 138–156, 2006.
[30]	A. Lambert, D. Gruyer, B. Vincke, and E. Seignez, “Consistent outdoor vehicle localization by bounded-error state estimation,” in IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 1211–1216, 2009. Best Paper Award Finalist.