More Web Proxy on the site http://driver.im/

research-article

Knowledge revision in systems based on an informed tree search strategy: application to cartographic generalisation

Authors:

Patrick Taillandier,

Cécile Duchêne,

Alexis DrogoulAuthors Info & Claims

CSTST '08: Proceedings of the 5th international conference on Soft computing as transdisciplinary science and technology

Pages 273 - 278

https://doi.org/10.1145/1456223.1456281

Published: 28 October 2008 Publication History

Abstract

Many real world problems can be expressed as optimisation problems. Solving this kind of problems means to find, among all possible solutions, the one that maximises an evaluation function. One approach to solve this kind of problem is to use an informed search strategy. The principle of this kind of strategy is to use problem-specific knowledge beyond the definition of the problem itself to find solutions more efficiently than with an uninformed strategy. This kind of strategy demands to define problem-specific knowledge (heuristics). The efficiency and the effectiveness of systems based on it directly depend on the used knowledge quality. Unfortunately, acquiring and maintaining such knowledge can be fastidious. The objective of the work presented in this paper is to propose an automatic knowledge revision approach for systems based on an informed tree search strategy. Our approach consists in analysing the system execution logs and revising knowledge based on these logs by modelling the revision problem as a knowledge space exploration problem. We present an experiment we carried out in an application domain where informed search strategies are often used: cartographic generalisation.

References

[1]

Atzmüller, M., Baumeister, J., and Puppe F. Introspective Subgroup Analysis for Interactive Knowledge Refinement. In FLAIRS, 2006, 402--407

[2]

Barrault, M., Regnauld, N., Duchêne, C., Haire, K., Baejis, C., Demazeau, Y., Hardy, P., Mackaness, W., Ruas, A., and Weibel, R. Integrating multi-agent, object-oriented, and algorithmic techniques for improved automated map generalization. In ICC, 2001, 2100--2116.

[3]

Battiti, Y., and Protasi, M. Reactive local search for the maximum clique problem. Algorithmica, 29, 2001, 610--637.

Digital Library

[4]

Brassel, K., and Weibel, R. A review and conceptual framework of automated map generalization. IJGIS, 1988.

[5]

Burghardt, D., and Neun, M. Automated sequencing of generalization services based on collaborative filtering. In GIScience, 2006.

[6]

Carbonara, L., and Sleeman, D. Effective and Efficient Knowledge Base Refinement. Machine Learning, 37, 1999.

Digital Library

[7]

Dempster, A. P., Laird, N. M., and Rubin, D. B. Maximum likelihood from incomplete data via the em algorithm (with discussion). Journal of the Royal Statistical Society, B 39, 1977, 1--38.

[8]

Fayyad, U. M., and Irani, K. B. On the Handling of Continuous-Valued Attributed in Decision Tree Generation. Machine learning, 8, 1992, 87--102.

Digital Library

[9]

Ginsberg, A., Weiss, S. M. and Politakis, P. Automatic knowledge base refinement for classification systems. Artificial Intelligence, 35, 1988, 197--226.

Digital Library

[10]

Glover, F. Tabu search. Journal on Computing, 1989.

[11]

Kirkpatrick, S., Gelatt, C. D., and Vecchi, M. P. Optimization by Simulated Annealing. Science, 1983.

[12]

Mustière, S. Cartographic generalization of roads in a local and adaptive approach: A knowledge acquisition problem. IJGIS, 19, 8--9 (Sept-Oct. 2005), 937--955.

[13]

Ourston, D., and Mooney, R. J. Changing the rules: A comprehensive approach to theory refinement. AAAJ, 1990.

[14]

Ruas, A. Modèle de gènéralisation de données géographiques à base de contraintes et d'autonomie. Thèse de l'UMLV, 1999.

[15]

Ruas, A., Dyèvre, A., Duchêne, C., and Taillandier, P. Methods for improving and updating the knowledge of a generalization system. In Autocarto, 2006.

[16]

Ruas, A., and Duchêne, C. A Prototype Generalisation System Based on the Multi-Agent Paradigm. Generalisation of Geographic Information: Cartographic Modelling and Applications, 2007.

[17]

Webb, G. I. DLGref2: Techniques for Inductive Rule Refinement. IJCAI Workshop W16: Machine Learning and Knowledge Acquisition, 1993.

[18]

Weibel, R., Keller, S., and Reichenbacher, T. Overcoming the Knowledge Acquisition Bottleneck in Map Generalization: the Role of Interactive Systems and Computational Intelligence' knowledge of generalization. In COSIT, 13, 1995.

Cited By

Regnauld NTouya GGould NFoerster T(2014)Process Modelling, Web Services and GeoprocessingAbstracting Geographic Information in a Data Rich World10.1007/978-3-319-00203-3_7(197-225)Online publication date: 15-Feb-2014
https://doi.org/10.1007/978-3-319-00203-3_7
Taillandier PDrogoul A(2010)Supervised Feature Evaluation by Consistency AnalysisProceedings of the 2010 Second International Conference on Knowledge and Systems Engineering10.1109/KSE.2010.28(63-68)Online publication date: 7-Oct-2010
https://dl.acm.org/doi/10.1109/KSE.2010.28
Taillandier PDuchene CDrogoul A(2009)Using Belief Theory to Diagnose Control Knowledge Quality: Application to Cartographic Generalisation2009 IEEE-RIVF International Conference on Computing and Communication Technologies10.1109/RIVF.2009.5174663(1-8)Online publication date: Jul-2009
https://doi.org/10.1109/RIVF.2009.5174663
Show More Cited By

Index Terms

Knowledge revision in systems based on an informed tree search strategy: application to cartographic generalisation
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies

Recommendations

Diagnosis in systems based on an informed tree search strategy: application to cartographic generalisation
CSTST '08: Proceedings of the 5th international conference on Soft computing as transdisciplinary science and technology

Many real world problems can be expressed as optimisation problems. Solving such problems means to find, among all possible solutions, the one that maximises an evaluation function. One approach to solve it is to use an informed search strategy. The ...
Automatic revision of the control knowledge used by trial and error methods: Application to cartographic generalisation

Abstract: Humans frequently have to face complex problems. A classical approach to solve them is to search the solution by means of a trial and error method. This approach is often used with success by artificial systems. However, when facing highly ...
Knowledge Revision for Reinforcement Learning with Abstract MDPs
AAMAS '15: Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems

Reward shaping is a method often used in RL so as to provide domain knowledge to agents and thus improve learning. An unrealistic assumption however is that the provided knowledge is always correct. This assumption can lead to poor performance in terms ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

CSTST '08: Proceedings of the 5th international conference on Soft computing as transdisciplinary science and technology

October 2008

733 pages

ISBN:9781605580463

DOI:10.1145/1456223

Conference Chair:
Lotfi A. Zadeh
University of California
,
General Chairs:
Youakim Badr
INSA-Lyon, France
,
Ajith Abraham
Norwegian University of Science and Technology, Norway
,
Yukio Ohsawa
Tokyo Institute of Technology, Japan
,
Program Chairs:
Richard Chbeir
University of Bourgogne, France
,
Fernando Ferri
IRPPS-CNR, Italy
,
Mario Koeppen
Kyushu Institute of Technology, Japan
,
Dominique Laurent
University of Cergy-Pontoise, France

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

The French Chapter of ACM Special Interest Group on Applied Computing
Ministère des Affaires Etrangères et Européennes
Région Ile de France
Communauté d'Agglomération de Cergy-Pontoise
Institute of Electrical and Electronics Engineers Systems, Man and Cybernetics Society
The European Society For Fuzzy And technology
Institute of Electrical and Electronics Engineers France Section
Laboratoire des Equipes Traitement des Images et du Signal
AFIHM: Ass. Francophone d'Interaction Homme-Machine
The International Fuzzy System Association
Laboratoire Innovation Développement
University of Cergy-Pontoise
The World Federation of Soft Computing
Agence de Développement Economique de Cergy-Pontoise
The European Neural Network Society
Comité d'Expansion Economique du Val d'Oise

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 28 October 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
90
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Regnauld NTouya GGould NFoerster T(2014)Process Modelling, Web Services and GeoprocessingAbstracting Geographic Information in a Data Rich World10.1007/978-3-319-00203-3_7(197-225)Online publication date: 15-Feb-2014
https://doi.org/10.1007/978-3-319-00203-3_7
Taillandier PDrogoul A(2010)Supervised Feature Evaluation by Consistency AnalysisProceedings of the 2010 Second International Conference on Knowledge and Systems Engineering10.1109/KSE.2010.28(63-68)Online publication date: 7-Oct-2010
https://dl.acm.org/doi/10.1109/KSE.2010.28
Taillandier PDuchene CDrogoul A(2009)Using Belief Theory to Diagnose Control Knowledge Quality: Application to Cartographic Generalisation2009 IEEE-RIVF International Conference on Computing and Communication Technologies10.1109/RIVF.2009.5174663(1-8)Online publication date: Jul-2009
https://doi.org/10.1109/RIVF.2009.5174663
Taillandier P(2009)Heuristic Revision by Heuristic Space ExplorationProceedings of the 2009 International Conference on Knowledge and Systems Engineering10.1109/KSE.2009.31(137-143)Online publication date: 13-Oct-2009
https://dl.acm.org/doi/10.1109/KSE.2009.31
Taillandier PBuard E(2009)Designing Agent Behaviour in Agent-Based Simulation through Participatory MethodProceedings of the 12th International Conference on Principles of Practice in Multi-Agent Systems10.1007/978-3-642-11161-7_43(571-578)Online publication date: 15-Dec-2009
https://dl.acm.org/doi/10.1007/978-3-642-11161-7_43

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents