Artificial Intelligence and Logic Programming

Course: ARTFICIAL INTELLIGENCE | Bachelor of Science (Computer Science)
Software: Prolog (SICStus Prolog, SWI Prolog, GNU Prolog)

Inteligenta Artificiala / Programare declarativa / Sisteme Expert
Artificial Intelligence / Declarative Programming / Expert Systems

Languages and Knowledge: Natural environments are ruled by languages. Computer science use artificial languages. Languages exist therefore, not for communication purposes alone, but particularly for knowledge. (Vlada, CNIV & eLSE 2005)

Computer Program: "A program is a theory (in some logic) and computation is deduction from the theory." J. A. Robinson

Sciencies: Sciences are models and virtual representations of knowledge. (CNIV 2008, M. Vlada)

Artificial Intelligence: The name "artificial intelligence" was proposed by John McCarthy when he and other AI influential figures (Marvin Minsky, Allen Newell, Herbert Simon, and others) organized a summer workshop at Dartmouth in 1956. (Gh. Tecuci, Wiley Interdisciplinary Reviews: Computational Statistics, Vol. 4/2, 2012)

OBIECTIVE

• Cunoasterea si utilizarea conceptelor si tehnicilor AI pentru rezolvarea problemelor folosind programarea declarativa;  sisteme expert
  
• fundamente de logica matematica de ordinul I pentru cunoasterea si utilizarea reprezentarii si procesarii bazelor de cunostinte oferite de limbajul Prolog;
  
• prin activitatile de la laborator se urmareste ca studentii sa obtina competente privind utilizarea limbajului Prolog ca motor de inferente (demonstrator de teoreme) in reprezentarea si procesarea bazelor de cunostinte.

Comentariu introductiv. Dezvoltarea stiintelor si experienta umana in rezolvarea problemelor folosind rationamentul uman si utilizarea calculatorului, au condus la definirea urmatoarelor tipuri de activitati de rezolvare:

1. programare procedurala (imperativa) sustinuta de limbajele de programare ce reclama conceperea unui algoritm de rezolvare si codificarea intr-un limbaj de programare; problema -> rationament rezolvare -> algoritm -> program (LINK-1, LINK-2)

2. programare declarativa (baze de cunostinte) sustinuta de limbajul Prolog (conceput ca motor de inferenta prin implementarea fundamentelor logicii de ordinul I in reprezentarea si prelucrarea cunostintelor) ce ofera reprezentarea problemelor in termeni de obiecte si definirea relatiilor (clauze Horn: fapte si reguli) dintre obiecte; o astfel de reprezentare defineste baze de cunostinte ce vor fi interogate (procesate prin inferente logice) prin motorul de inferente Prolog (cautarea de solutii se realizeaza prin metoda backtracking) (LINK)

3. metode (tehnici) de rezolvare sustinute de rationamente specifice de cautare a solutiilor diverselor clase de probleme, de exemplu: metoda "divide et impera", metoda "greedy", metoda "backtracking" etc. (LINK)

An example is “The four colour problem”  (Thomas 2007, Vlada 2003) that was resolved in 1977 simply by using computer and using a new method  (Backtracking). The fact that there are alternative ways of executing a logic program has been characterised by the pseudo-equation:

• AlGORITHM = LOGIC +  CONTROL (Kowalski 1979)

where "Logic" represents a logic program and "Control" represents different theorem-proving strategies.

The research and development, innovation and improvement, foundation work and new concepts for the implementation and development of modern technology on the use of computers led to define the following pseudo-equation:             

• PROGRAM =  ALGORITHM  + DATA STRUCTURES (Wirth 1975)

• EXPERT SYSTEM  = KNOWLEDGE  +  META-INTERPRETER (Sterling 1984)

CONTINUT

• Structura unui sistem inteligent
• Spatiu starilor unei probleme. Exemple
• Reprezentarea problemelor si spatiul starilor
• Arborele solutiilor pentru metoda backtracking
• Spatiul starilor pentru problema “Misionarii si Canibalii”
• Spatiul starilor pentru problema “8-puzzle”
• Baza de cunostinte si structura unui program logic
• Arborele de demonstrare atasat unui scop. Exemple
• Procesarea bazei de cunostinte in Prolog. Exemple
• Procedura EXEC- semantica procedurala in executia programelor Prolog
• Reprezentarea formulelor in forma CNF
• Reprezentarea formulelor in forma prenex
• Reprezentarea formulelor in forma Skolem
• Conceptele de substitutie si unificare. Exemple
• Argoritmul de unificare Robinson
• Sistem expert pentru derivarea simbolica.Exemplu
• Program Prolog pentru colorarea hartilor
• Sisteme de rezolvare:spatii de reprezentare, structuri de cautare, proceduri de cautare
• Algoritmul de cautarea Breadh-First-forma procedurala
• Algoritmul de cautarea Breadh-First-forma Prolog
• Algoritmul de cautarea Depth-First-forma Prolog
• Algoritmul de cautarea Besth-First-forma generala/Prolog
• Algoritmul de cautarea A*-forma procedurala/Prolog

Bibliografie / Resurse software

TUTORIALE: Probleme_prolog met_BACKTRACKING (sau http://www.scribd.com/) , Poole and Mackworth, 2010: http://artint.info/, Detlovs Vilnis and Podnieks Karlis, Introduction to Mathematical Logic (LINK), 2012:Hyper-textbook for students (Propositional Logic, Predicate Logic, Completeness Theorems - Model Theory, Normal Forms, Clause Form, Resolution Method)

PROIECTE: Proiecte-1 Proiecte-2

1. Bratko, Ivan - Prolog Programming for Artificial Intelligence (LINK , Prolog code for all chapters ): www.pearsoned.co.uk
2. DOCUMENTATION: SWI Prolog - www.swi-prolog.org/pldoc/refman/ , SICStus Prolog - http://www.sics.se/sicstus/docs/latest4/html/sicstus.html/
3. David Poole, Alan Mackworth, Artificial Intelligence: Foundations of Computational Agents, Cambridge University Press, 2010 (ONLINE, Complete BOOK) - http://artint.info/
4. Reid G. Smith, Knowledge-Based Systems: Concepts, Techniques, Examples:MYCIN , Ottawa, ON, May 8, 1985 |  LINK (pdf, http://www.reidgsmith.com)
5. Gheorghe Tecuci, Artificial intelligence, Wiley Interdisciplinary Reviews: Computational Statistics, Vol. 4/2, 2012 (OnLine HTML, PDF) - http://onlinelibrary.wiley.com/
6. Robert Kowalski, http://www.doc.ic.ac.uk/~rak/ | http://www.doc.ic.ac.uk/~rak/papers/Chapter6.pdf

- M. Vlada, Algorithms for Testing Satisfiability Formulas, ARTIFICIAL INTELLIGENCE REVIEW,  Kluwer Academic Publishers – ISSN 0269-2821 , vol.15 , No 3, 2001, pag.153-163

- M. Vlada, An efficient algorithm for testing propositional formulas, COMPUTERS AND ARTIFICIAL  INTELLIGENCE - ISSN 1335-9150 , Vol. 17, No. 4, 1998, pag. 383-391

- M. Vlada,  Modele pentru explorarea  bazelor de cunoştinţe şi aplicaţii   în inteligenţa artificială (1997)

- St. Andrei, Counting for Satisfiability by Inverting Resolution, Artificial Intelligence Review 22: 339–366, 2004

- Jurgen Schmidhuber, Optimal Ordered Problem Solver, Machine Learning, 54, 211–254, Kluwer Academic, 2004 OOPS

- D. Dumitrescu – Principiile Inteligenţei Artificiale, Ed. Albastră, 2005

"All mathematical theories were indeed reduced to systems of axioms and rules of inference without any admixture of sophisticated human skills, intuitions etc. Today, the logical techniques developed by these brilliant people allow ultimate axiomatization of any theory that is based on a stable, self-consistent system of principles (i.e. of any mathematical theory)." Detlovs Vilnis and Podnieks Karlis, Introduction to Mathematical Logic (LINK), 2012.

Language of knowledge:

• Natural languages (the languages of the peoples) - "entity"=word; lexical constructions describe states, images, actions, etc.
• Languages of sciences (used in the fields of science: mathematics, physics, chemistry, economics, etc.) - "entity"= knowledge/meet; study of objects and relationships between objects in the fields of mathematics, physics, chemistry, computer science, biology, economics, etc.
• Artificial languages (used computer) consisting of 
  • Procedural Programming languages - "entity" =memory location
  • Functional Programming Languages - "entity" = item list
  • Logic Programming Languages - "entity "= object, clause
  • Object Oriented Programming - "entity" = object
  • Web Programming Languages - "entity" = web/multimedia elements
  • Languages for Databases - "entity" = registration
  • Languages for Computer graphics - "entity" = graphics object
  • Languages for Modeling-Simulation - "entity "= event
  • Languages for Operating Systems- "entity" = process/ task
  • Languages for Artificial Intelligence - "entity" = meet/ knowledge

Definition. A language of knowledge is virtual system/logical

                       L = ( V, Sin, Sem, O, C, T, Tc)  , where

V = vocabulary / alphabet, Sin = syntax (rules), Sem = semantics (rules), O = objects, C = concepts / terms, T = theories / methods / techniques to solve, Tc = treasury of knowledge (knowledge base).

(Vlada 2005)

Propose the following: MODELING = KNOWLEDGE +  REPRESENTATION                LANGUAGES =  PROCESSING  + INTERPRETATION News 2012 - University of Sussex: "Anthropomimetic" Robot (Robotul antropomimetic) - LINK-video.

• Avron Barr and Edward A. Feigenbaum, Handbook of AI, Addison-Wesley Longman Publishing Co., Inc. Boston, MA, USA 1986, ISBN:0201118114
• Bilaniuk, S. (2009), Deduction Theorem, [online] Trent University, Peterborough, Ontario, Canada, http://us.metamath.org/mpegif/mmdeduction.html#dedvsth
• Clocksin, W. F. and Mellish, C. S. (1984 ) Programming in Prolog Using the ISO Standard, New York: Springer-Verlag, and [online] Wolfram Math, http://mathworld.wolfram.com/HornClause.html
• CSAIL, (2009) Learning and Intelligent Systems, Computer Science and Artificial Intelligence Laboratory, [online], MIT - The Massachusetts Institute of Technology,  Cambridge,  http://www.csail.mit.edu/
• Kowalski, R. (1979) Logic for Problem Solving. Artificial Intelligence, Series North Holland, [online] http://www.doc.ic.ac.uk/~rak/, http://en.wikipedia.org/wiki/Robert_Kowalski
• Lloyd, J.W. (1984). Foundations of Logic Programming. Springer-Verlag: Berlin, Germany.
• Minsky, M. (1986) The Society of Mind, Touchstone Books, New York,
• Robinson, J. A. (1965). A Machine Oriented Logic Based on the Resolution Principle. Journal of the ACM 12: 23–41.
• Sterling L. (1984) Logical Levels of Problem Solving, Proceedings 2nd Intl. Logic Programming Conference, Uppsala, Sweden, pp. 231-242
• Thomas, R. (2007) The Four Color Theorem [online] School of Mathematics, Georgia Institute of Technology, Atlanta, http://www.math.gatech.edu/~thomas/FC/fourcolor.html
• Vlada, M. (2003) "Eureka: Algorithmic thinking", Solving Problems using Eureka [online], University of Bucharest,  http://ebooks.unibuc.ro/informatica/eureka/index.htm.
• Vlada, M. (2005) "Role of Language in processing Information and Knowledge",  Proceedings of The International Scientific Conference – eLearning and Software for Education”, eLSE 2005, “Carol I” National Defence University, Bucharest, University Publishing House, pp 165-178
• Wirth N. (1975) Algorithms + Data Structures = Programs, Prentice-Hall, pp 1-366.
• S. Russell, P. Norvig. Artificial Intelligence: A Modern Approach, Prentice Hall, 2002, http://aima.cs.berkeley.edu
• D. Poole, A. Mackworth, R. Goebel. Computational Intelligence – a Logical Approach. Oxford University Press, 1998, http://www.cs.ubc.ca/~poole/ci.html

1. http://www.sics.se/sicstus.html | Sicstus PROLOG
2. http://www.cs.nuim.ie/~jpower/Courses/PROLOG/ (James F. Power) |GNU Prolog
3. http://cis.stvincent.edu/html/tutorials/prolog/index.html
4. http://bach.istc.kobe-u.ac.jp/llp/current/examples/prolog/
5. http://cs.wwc.edu/~cs_dept/KU/PR/Prolog.html (Computer Science Department Walla WallaCollege)
6. http://invaders.mars-attacks.org/~boklm/prolog/ (Loiseleur Michel & Vigier Nicolas)
7. http://www.visual-prolog.com/vip6/Community/userExamples/OpenGL.htm (Visual Prolog)
8. Warren's Abstract Machine -http://fr.wikipedia.org/wiki/Warren%27s_Abstract_Machine

Languages of the World (Wide Web)

by Daniel Ford and Josh Batson

Ref.: Research Blog (News on Google Research), http://googleresearch.blogspot.com/2011/07/languages-of-world-wide-web.html