人工智能精品资源：(ebook-Artificial Intelligence) Gavanelli - Interactive Constraint Satisfaction Problems

DOTTORATO DI RICERCA IN INGEGNERIA DELL’INFORMAZIONE XIV CICLO Sede Amministrativa Universit`a degli Studi di MODENA e REGGIO EMILIA TESI PER IL CONSEGUIMENTO DEL TITOLO DI DOTTORE DI RICERCA Interactive Constraint Satisfaction Problems for Artificial Vision Relatore: Prof. Cesare Stefanelli Correlatore: Prof. Paola Mello CANDIDATO Marco Gavanelli ACKNOWLEDGMENTS I would like to thank all those people who made this thesis possible and an enjoyable experience for me. In particular, I wish to thank Rita Cucchiara, Evelina Lamma, Paola Mello, Massimo Piccardi, and Cesare Stefanelli for the continuous support in all phases of this work. I also wish to thank Carmen Gervet for valuable suggestions and help during my visit in IC-Parc. A special thank goes to Michela Milano, who has always encouraged me during my studies, guiding my work and helping whenever I was in need. ii ABSTRACT Interactive Constraint Satisfaction Problems for Artificial Vision Marco Gavanelli , Ph.D. Universit`a degli Studi di Ferrara Artificial Vision is an important field of Artificial Intelligence: the human brain is able to derive various types of information about the outer world from vision. However, the semantic interpretation of objects is a hard task for a computer. Constraints have been widely used for visual recognition, because they are able to describe very complex models and situations in a natural way [115, 86]∗. Constraint Logic Programming [67] is a new paradigm of declarative programming lan- guages that is able to deal declaratively and efficiently with problems described with con- straints. In this thesis, we addressed problems that stem from Artificial Vision with constraints. We developed a 3D visual search system able to detect an object described with constraints in an image. We provide constraint models for dealing with the problems in Artificial Vision. We generalize the applied techniques to other important fields of Artificial Intel- ligence, developing new tools of Constraint Satisfaction and Optimization in Constraint Logic Programming. In order to obtain efficiency, we propose a tight interaction between the Constraint Solver and the provider of visual features. We give a theoretical model, solving algorithm and a language extension. ∗ Bracketed references placed superior to the line of text refer to the bibliography. iii We model 3D objects with an object-centered model, based on visual information. From each viewpoint, only part of the visual features of a 3D object can be seen; we model objects by adding invisible features in the domains and select only the most informative assignments by means of a partial order. DESCRIPTORS Visual Search Constraint Logic Programming Partial Order Constraint Satisfaction Interactive Constraints iv TABLE OF CONTENTS Page ACKNOWLEDGMENTS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii ABSTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii LIST OF FIGURES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . x LIST OF TABLES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiii NOMENCLATURE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiv I Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.0 Artificial Vision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1 Modelling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Efficiency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Effectiveness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4 Synopsis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . II Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.0 Constraint Satisfaction Problems . . . . . . . . . . . . . . . . . . . . . . . 2.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.1 Systematic Search Algorithms . . . . . . . . . . . . . . . . . . . . . . 2.2.1.1 Backtracking . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.1.2 Forward Checking . . . . . . . . . . . . . . . . . . . . . . . 2.2.2 Consistency Techniques . . . . . . . . . . . . . . . . . . . . . . . . . 1 2 3 3 4 5 6 7 7 7 8 8 8 9 2.2.3 Heuristic Search Algorithms . . . . . . . . . . . . . . . . . . . . . . . 11 3.0 Constraint Optimization Problems . . . . . . . . . . . . . . . . . . . . . . 12 3.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 12 v