Lecture Notes in Artificial Intelligence Edited by R. Goebel, J. Siekmann, and W. Wahlster Subseries of Lecture Notes in Computer Science 6404 Antônio Carlos da Rocha Costa Rosa Maria Vicari Flavio Tonidandel (Eds.) Advances in Artificial Intelligence – SBIA 2010 20th Brazilian Symposium on Artificial Intelligence São Bernardo do Campo, Brazil, October 2328, 2010 Proceedings 13 Series Editors Randy Goebel, University of Alberta, Edmonton, Canada Jörg Siekmann, University of Saarland, Saarbrücken, Germany Wolfgang Wahlster, DFKI and University of Saarland, Saarbrücken, Germany Volume Editors Antônio Carlos da Rocha Costa Universidade Federal do Rio Grande – FURG Centro de Ciências Computacionais Av. Itália, km 8 – Campus Carreiros, 96.201900 Rio Grande, RS, Brazil Email: [email protected] Rosa Maria Vicari Universidade Federal do Rio Grande do Sul – UFRGS Instituto de Informática Av. Bento Gonçalves 9.500, 91501970 Porto Alegre, RS, Brazil Email: [email protected] Flavio Tonidandel Centro Universitário da FEI Departamento de Ciência da Computação Av. Humberto A. C. Branco 3972, 09850901 São Bernardo do Campo, SP, Brazil Email: fl[email protected] Library of Congress Control Number: 2010935023 CR Subject Classification (1998): I.2, H.3, H.4, I.4, I.5, H.5 LNCS Sublibrary: SL 7 – Artificial Intelligence ISSN ISBN10 ISBN13 03029743 3642161375 Springer Berlin Heidelberg New York 9783642161377 Springer Berlin Heidelberg New York This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer. Violations are liable to prosecution under the German Copyright Law. springer.com © SpringerVerlag Berlin Heidelberg 2010 Printed in Germany Typesetting: Cameraready by author, data conversion by Scientific Publishing Services, Chennai, India Printed on acidfree paper 06/3180 Preface The SBIA conference series started in 1984 at the Federal University of Rio Grande do Sul (UFRGS) and through the years has benefited the Artificial Intelligence and Computer Science communities in Brazil. After 26 years and 20 conferences SBIA is now a mature event, constituting a discussion forum for new ideas in all subareas of AI. In this book you will find the full papers selected for publication in the SBIA 2010 proceedings. The papers cover the AI subareas in the following way: – – – – – – – Ontologies, Knowledge Representation, and Reasoning: 8 Machine Learning: 2 Autonomous Agents and Multiagent Systems: 6 Natural Language Processing: 2 Planning and Scheduling: 5 Logics for AI: 3 Constraints and Search: 5 We would like to thank all the authors that contributed to SBIA 2010. We also thank all the members of the international Program Committee and the additional reviewers, who did an excellent job in reviewing the papers. We are very grateful to Flavio Tonidandel, General Chair of SBIA 2010 and of the Joint SBIA/SBRN/JRI 2010 Conference, for all the support that he and his team at FEI provided. Yoav Shoham, Jaime Sichman, and David Hogg were the keynote speakers of the event. We thank them very much for their acceptance of the invitation. A special acknowledgement is due to Tiago Thompsen Primo, for his dedi cated effort in the editing of these proceedings. Finally, we thank the SBIA 2010 sponsors (CAPES, CNPq, FAPESP, and SBC) for their support. August 2010 Antônio Carlos da Rocha Costa Rosa Maria Vicari Organization Organizing Committee General Chair Flavio Tonidandel Centro Universitário da FEI Workshop Chair Plı́nio Thomaz Aquino Jr. Centro Universitário da FEI Tutorial Chair Paulo Sérgio Silva Rodrigures Centro Universitário da FEI Steering Committee (CEIA) Augusto Loureiro da Costa Solange Oliveira Rezende Fernando Santos Osório Fabio Gagliardi Cozman Marcelo Finger Fred Freitas Alexandre da Silva Simões Universidade Federal da Bahia (Coordinator) Universidade de São Paulo Universidade de São Paulo Universidade de São Paulo Universidade de São Paulo Universidade Federal de Pernambuco Universidade Estadual Paulista Program Committee Adina Magda Florea Adolfo Arenas Adolfo Neto Adriano Werhli Alejandro Zunino Alessio Lomuscio Alexander Gelbukh Alexandre Silva Aline Villavicencio Alneu Lopes Alvaro Moreira Amilcar Cardoso Ana Bazzan Ana Bicharra Polytechnic University of Bucharest, Romania Inst. Politec. Nal. Campus “Lopez Mateos”, Mexico UTFPR, Brazil FURG, Brazil ISISTANUNICEN, Argentina Imperial College, UK National Polytechnic Institute, Mexico UFRJ, Brazil UFRGS, Brazil USP, Brazil UFRGS, Brazil University of Coimbra, Portugal UFRGS, Brazil UFF, Brazil VIII Organization Ana Casali Universidad Nacional de Rosario, Argentina Ana Carolina Bertoletti De Marchi UPF, Brazil Ana Teresa Martins UFC, Brazil Anarosa Brandao USP, Brazil André Campos UFRN, Brazil André Ponce de Leon F. de Carvalho USP, Brazil Andrea Omicini University of Bologna, Italy Anna Helena Reali Costa USP, Brazil Anne Canuto UFRN, Brazil Antônio Braga UFMG, Brazil Antonio Carlos da Rocha Costa FURG, Brazil Artur Garcez City University of London, UK Augusto Loureiro da Costa UFBA, Brazil Aurora Pozo UFPR, Brazil Barbara Hammer Clausthal University of Technology, Germany Benjamin Bedregal UFRN, Brazil Bianca Zadrozny UFF, Brazil Blai Bonet Universidad Simón Bolı́var, Venezuela Carlos ReyesGarcia INAOE, Mexico Carlos Ribeiro ITA, Brazil Cassio de Campos Dalle Molle Institute for AI, Switzerland Celso Kaestner UTFPR, Brazil Christian Lemaitre Universidad Autónoma Metropolitana, Mexico Clarisse de Souza PUCRio, Brazil Daniel Berrar University of Ulster, UK Diana Adamatti FURG, Brazil Donato Malerba Università degli Studi di Bari, Italy Edson Matsubara UFMS, Brazil Edward Hermann Haeusler PUCRio, Brazil Eric Matson Purdue University, USA Eugenio Oliveira Universidade do Porto, Portugal Evandro Costa UFAL, Brazil Fabiano Silva UFPR, Brazil Fariba Sadri Imperial College, UK Fábio Cozman USP, Brazil Federico Barber Universidad Politecnica de Valencia, Spain Fernando Osório USP, Brazil Filip Zelezny Czech Techn. University in Prague, Czech Republic Flavio Tonidandel FEI, Brazil Flávio Soares Corra da Silva USP, Brazil Francisco de Carvalho UFPE, Brazil Organization Frank Dignum Fred Freitas Gabriel Lopes Geber Ramalho Gerardo Schneider Gerson Zaverucha Graça Gaspar Graçaliz Dimuro Guilherme Barreto Guillermo Simari Gustavo GiménezLugo Hector Geffner Helder Coelho Heloisa Camargo Ines Dutra Irwin King Ivandré Paraboni Jaime Sichman James Cussens Jan Ramon João Gama João Marcos João Balsa João Luis Tavares da Silva Jomi Hübner Juergen Dix Julie Dugdale Krysia Broda Laurent Perrussel Lúcia Drummond Leliane Nunes de Barros Leonardo Emmendorfer Li Weigang Luis Antunes Luis Fariñas del Cerro Luis Lamb Luis Otávio Alvares Luiz Satoru Ochi Luiza Mourelle Mara Abel Marcelo Finger Marcilio de Souto Marco Gori IX Utrecht University, Netherlands UFPE, Brazil Universidade Nova de Lisboa, Portugal UFPE, Brazil University of Gothenburg, Sweden UFRJ, Brazil Universidade de Lisboa, Portugal FURG, Brazil UFC, Brazil Universidad Nacional del Sur, Argentina UTFPR, Brazil Universitat Pompeu Fabra, Spain Universidade de Lisboa, Portugal UFSCar, Brazil Universidade do Porto, Portugal The Chinese University of Hong Kong, China USP, Brazil USP, Brazil University of York, UK Katholieke Universiteit Leuven, Belgium Universidade do Porto, Portugal UFRN, Brazil Universidade de Lisboa, Portugal UCS, Brazil UFSC, Brazil Clausthal University of Technology, Germany Laboratoire d’Informatique de Grenoble, France Imperial College, UK Université de Toulouse, France UFF, Brazil USP, Brazil FURG, Brazil UnB, Brazil Universidade de Lisboa, Portugal Université Paul Sabatier, France UFRGS, Brazil UFRGS, Brazil UFF, Brazil UERJ, Brazil UFRGS, Brazil USP, Brazil UFRN, Brazil University of Siena, Italy X Organization Marco Antonio Casanova Marcos Castilho Maria Monard Maria das Graças Volpe Nunes Marilton Aguiar Mario Fernando Campos Marley Vellasco Mário Benevides Michael Thielscher Nuno David Olivier Boissier Pablo Noriega Patrı́cia Tedesco Patricia Jaques Paulo Ferreira Jr. Paulo Quaresma Paulo Santos Paulo Trigo Pedro Larrañaga Ramon de Mantaras Reinaldo Bianchi Rejane Frozza Renata de Freitas Renata Vieira Renata Wassermann Ricardo Rabelo Ricardo Silva Ricardo Silveira Ronaldo Prati Rosa Viccari Rui Camacho Sandra Sandri Sheila Veloso Silvia Botelho Silvia Schiaffino Siome Goldenstein Solange Rezende Soumya Ray Stan Matwin Stanley Loh Stefano Ferilli Teresa Ludermir Thiago Pardo PUCRio, Brazil UFPR, Brazil USP, Brazil USP, Brazil UFPEL, Brazil UFMG, Brazil PUCRio, Brazil UFRJ, Brazil TU Dresden, Germany ISCTE, Portugal EMSE, France IIIACSIC, France UFPE, Brazil UNISINOS, Brazil UFPEL, Brazil Universidade de Évora, Portugal FEI, Brazil ISEL, Portugal Polytechnic University of Madrid, Spain IIIACSIC, Spain FEI, Brazil UNISC, Brazil UFF, Brazil PUCRS, Brazil USP, Brazil UFSC, Brazil University College of London, UK UFSC, Brazil UFABC, Brazil UFRGS, Brazil Universidade do Porto, Portugal IIIA, Brazil UERJ, Brazil FURG, Brazil ISISTAN, Argentina UNICAMP, Brazil USP/S.Carlos, Brazil Oregon State University, USA University of Ottawa, Canada UCPEL/ULBRA, Brazil Università degli Studi di Bari, Italy UFPE, Brazil USP, Brazil Organization Toby Walsh Torsten Schaub Virginia Dignum Valerie Camps Vania Bogorny Vı́tor Santos Costa Vera Lúcia Strube de Lima Viviane Torres da Silva Vladik Kreinovich Wagner Meira, Jr. Walter Carnielli Walter Daelemans Wamberto Vasconcelos Wiebe van der Hoek Yves Demazeau Zhao Liang XI NICTA and Univ. New South Wales, Australia University of Potsdam, Germany Delft Univ. of Technology, Netherlands Université Paul Sabatier, France UFSC, Brazil Universidade do Porto, Portugal PUCRS, Brazil UFF, Brazil University of Texas at El Paso, USA UFMG, Brazil UNICAMP, Brazil University of Antwerp, Belgium University of Aberdeen, UK University of Liverpool, UK Laboratoire d’Informatique de Grenoble, France USP, Brazil Additional Reviewers André Lins Aquino Caecilia Zirn Cassia Santos Christian Vogler Daniel Weingaertner Eder Mateus Gonçalves Eugenio Silva Francicleber Ferreira Frédéric Moisan Gustavo Batista Illya Kokshenev João Alcântara Karla Figueiredo Luis Künzle Martin Musicante Natasha Lino Nicolau Werneck Paulo Schreiner Regivan Hugo Nunes Santiago Rinaldo Lima Rodrigo Wilkens Rosiane de Freitas Rodrigues Sérgio Almeida Thiago Noronha UFOP, Brazil Univ. Heidelberg, Germany Evora University, Portugal ILSP, Greece Universidade Federal do Paraná, Brazil FURG, Brazil PUCRio, Brazil UFC, Brazil Université de Toulouse, France USP, Brazil UFMG, Brazil UFC, Brazil PUCRio, Brazil UFPR, Brazil UFRN, Brazil UFPb, Brazil USP, Brazil UFRGS, Brazil UFRN, Brazil UFPE, Brazil UFRGS, Brazil UFAM, Brazil UCPel, Brazil UFMG, Brazil XII Organization Supporting Scientific Society SBC Sociedade Brasileira de Computação. Sponsoring Institutions CNPq Conselho Nacional de Desenvolvimento Cientı́fico e Tecnológica CAPES Coordenação de Aperfeiçoamento de Pessoal de Nı́vel Superior FAPESP Fundação de Amparo à Pesquisa do Estado de São Paulo Table of Contents Chapter 1: Ontologies, Knowledge Representation and Reasoning Ontological Primitives for Visual Knowledge . . . . . . . . . . . . . . . . . . . . . . . . . Alexandre Lorenzatti, Mara Abel, Sandro Rama Fiorini, Ariane Kravczyk Bernardes, and Claiton Marion dos Santos Scherer A Semiautomatic Method for Domain Ontology Extraction from Portuguese Language Wikipedia’s Categories . . . . . . . . . . . . . . . . . . . . . . . . Clarissa Castellã Xavier and Vera Lucia Strube de Lima 1 11 Ontology Reasoning in AgentOriented Programming . . . . . . . . . . . . . . . . . Claudio Fuzitaki, Álvaro Moreira, and Renata Vieira 21 System Design Modification with Actions . . . . . . . . . . . . . . . . . . . . . . . . . . . Maria Viviane de Menezes, Silvio do Lago Pereira, and Leliane Nunes de Barros 31 Learning Terminologies in Probabilistic Description Logics . . . . . . . . . . . . Kate Revoredo, José Eduardo OchoaLuna, and Fabio Gagliardi Cozman 41 KnowledgeBased System for the Maintenance Registration and Consistency among UML Diagrams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Cleverton Ferreira Borba and Ana Estela Antunes da Silva 51 Semantic Mapping with a Probabilistic Description Logic . . . . . . . . . . . . . Rodrigo Polastro, Fabiano Corrêa, Fabio Cozman, and Jun Okamoto Jr. 62 Markov Decision Processes from Colored Petri Nets . . . . . . . . . . . . . . . . . . Monica Góes Eboli and Fabio Gagliardi Cozman 72 Chapter 2: Machine Learning Incremental Learning of Multivariate Gaussian Mixture Models . . . . . . . . Paulo Martins Engel and Milton Roberto Heinen Bayesian Network Structure Inference with an Hierarchical Bayesian Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Adriano Velasque Werhli 82 92 XIV Table of Contents Chapter 3: Autonomous Agents and Multiagent Systems On the Construction of Synthetic Characters with Personality and Emotion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Ary Fagundes Bressane Neto and Flávio Soares Corrêa da Silva 102 Towards Automated Trading Based on Fundamentalist and Technical Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Carlos Henrique Dejavite Araújo and Paulo André Lima de Castro 112 Developing a ConsciousnessBased Mind for an Artificial Creature . . . . . . Ricardo Capitanio Martins da Silva and Ricardo Ribeiro Gudwin Simulating the Emergence of Social Relationship Networks in Groups of Believable Agents: The XBARIM Model . . . . . . . . . . . . . . . . . . . . . . . . . Pablo Barbosa, Danielle Silva, Geber Ramalho, and Patricia Tedesco Using Jason to Develop Normative Agents . . . . . . . . . . . . . . . . . . . . . . . . . . Baldoino Fonseca dos Santos Neto, Viviane Torres da Silva, and Carlos José Pereira de Lucena Improving Space Representation in Multiagent Learning via Tile Coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Samuel Justo Waskow and Ana Lúcia Cetertich Bazzan 122 133 143 153 Chapter 4: Natural Language Processing Factored Translation between Brazilian Portuguese and English . . . . . . . . Helena de Medeiros Caseli and Israel Aono Nunes 163 Question Answering for Portuguese: How Much Is Needed? . . . . . . . . . . . . Rodrigo Wilkens and Aline Villavicencio 173 Chapter 5: Planning and Scheduling Planning for Multirobot Localization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Paulo Pinheiro and Jacques Wainer 183 Symbolic Bounded RealTime Dynamic Programming . . . . . . . . . . . . . . . . Karina Valdivia Delgado, Cheng Fang, Scott Sanner, and Leliane Nunes de Barros 193 An Adaptive Genetic Algorithm to the Single Machine Scheduling Problem with Earliness and Tardiness Penalties . . . . . . . . . . . . . . . . . . . . . . Fábio Fernandes Ribeiro, Marcone Jamilson Freitas Souza, and Sérgio Ricardo de Souza 203 Table of Contents A Dijkstra Algorithm for FixedWing UAV Motion Planning Based on Terrain Elevation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Felipe Leonardo Lôbo Medeiros and José Demisio Simões da Silva Feasible UAV Path Planning Using Genetic Algorithms and Bézier Curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Douglas Guimarães Macharet, Armando Alves Neto, and Mario Fernando Montenegro Campos XV 213 223 Chapter 6: Constraints and Search HighLevel Modeling of ComponentBased CSPs . . . . . . . . . . . . . . . . . . . . . Raphaël Chenouard, Laurent Granvilliers, and Ricardo Soto Improving the Distributed Constraint Optimization Using Social Network Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Allan Rodrigo Leite, André Pinz Borges, Laércio Martins Carpes, and Fabrı́cio Enembreck A Survey and Classification of A* Based BestFirst Heuristic Search Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Luis Henrique Oliveira Rios and Luiz Chaimowicz 233 243 253 Chapter 7: Logics for AI A Sequent Calculus for 3Dimensional Space . . . . . . . . . . . . . . . . . . . . . . . . Norihiro Kamide 263 Intuitionistic Fuzzy Probability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Claudilene Gomes Da Costa, Benjamin Callejas Bedregal, and Adrião Duarte Doria Neto 273 A Proof System for Temporal Reasoning with Sequential Information . . . Norihiro Kamide 283 A Refuted Conjecture on Probabilistic Satisfiability . . . . . . . . . . . . . . . . . . Marcelo Finger and Glauber De Bona 293 A Logic for Conceptual Hierarchies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Norihiro Kamide 303 Author Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313