ARTJ?ICIAL INTELLIGENCE IN WESTERN EUROPE

ITALY

Our account of A.I. research in Italy covers work at the following major cen­ ters :

• Milan ?olytechnic Artificial Intelli­ gence ?roject (M?-AI ?roject) of the I stituto di Elettrotecnica ed Elettro-­ nica I ?oli tecnico di ru lano I ~Ulan (Director: M. Somalvico).
• Non-Numerical Information ?rocessing Section of the Istituto di Elaborazio­ ne dell 'Informazione del CNR , ?isa (Director : U. t1ontanari).
• Speech Understanding Group of the Cen­ tro per l'Elaborazione Numerale dei Se ~nali del CNR, ?olitecnico di Torino, ­ Turin (director! R. De Mo~i).
• Artificial Intelligence Group of the Laboratorio pe r la Dinamica dei Siste­ mi e per l'Elettronica Biologica del CNR, Padua (Director: E. ?agello).

- 1. Milan.

In November 1971 tlaico Somalvico has for med the Milan ?olytechnic Artificial In= telligence ?roject (M?-AI ?roject) as a research project at the Laboratorio di Calcolatori of the Istituto di Elettrotec nica ed Elettronica of the ?olitecnico di Milano.

Its research activity has been based on the assumption that Artificial Intelli­ gence is that discipline , within Com~uter Science, which studies the theoretical foundations, the main methodologies,the design and the construction of programs which allow the computer to operate mecha­ nisms and to perform activities that are usually considered as exclusive of human intelligence.

We can examine, in the se0uel , the main research directions which have been follow ed at the M?-AI ?roj ect [1] .

1. Theory of Problem S0l ving. The process of representing a problem in-

ARTJ?ICIAL INTELLIGENCE IN WESTERN EUROPE

J.?itrat and E. Sandewall (session co-chairmen), W.Bibel, G.Huet, H.H. Nagel and !1 . Somalvico

Addendum volves necessarily a passage between two different worlds, namely the world of the intuitive notion that the man has of the nroblem, and the world of the formal and precise description of the nroblem, that will be given to the computer.

This nassage is achieved by means of an approDriate selection of only one part of the information which is pertinent to the intuitive knowledge of the :roblem; the selected information is then arranged in a structured form, thus yielding the re­ presentation of the probleM.

However, even the most structured and riel renresentation,which might be obtained within this nassage, will always present a difference. from the unformal knowledge about the problem.

This distance, which reminds the similar gap between physical nhenomenon and nhysical law, can only be narrowed,but can never be wholly deleted.

The previous considerations have been the basic motivations for the development of a "theory of nroblem-solving" devoted to the understanding of the different as~~8t ~ of the nroblem-solving process, and cente­ red around the focal point of problem re­ presentation.

This theory of nroblem-solving, which is being developed at the ~1? -AI ?roject , is intended to achieve the following goals:

• formalization of problem representation methods [2 , 5, 8] ;
• formalization of solution search tech­ nic::ues [ 3] ;
• formalization and selection of "good" )'1roblem re!Jresentations [6] ;
• automatic evaluation and use of heuris­ tic information [4 , 10] ;
• generalization and operation of learnin~ nrocesses [7] ;
• structured organization of a problem in subnroblems as a basis of automatic nrogramming [9] ;
• design of a general structure for a nroblem solver [11].

The future research directions will be the theoretically guided design and experimentation of a problem solver based on the obtained results.

B. Languages for Artificial Intelligence. On the UNIVAC 1108 computer of the l1:0-AI ?roject, have been implemented, and exp~ rimented, the following interpreters: LIS? I HICRO?LANNER I '?ROLOG I HAGl1ALIS? I REDUCE.

These interpreters have been utilized as tools for designing AI systems in problem solving , robot plan formation, natural language understanding, automa­ tic deduction.

In particular, the characteristics and limitations of MICRO'?LANNER and '?ROLOG have been examined in detail.

Studies and a comparison between the procedural embedding and the axiomatic approaches to knowledge representation have been carried on [12, 13].

c . Robot Plan Formation.

• The research activity which has been peE formed, has been devoted to utilize MICROPLANNER and FIRST ORDER '?REDICATE CALCULUS as representation languages . devoced to in plan formation [14, 1 5, 1 6, 17] .

Also ,an algebraic theory of plan forma­ tion has been developed and two systems, written in LISP, have been developed ~~·

In particular, the following results have been obtained :

• Formalization of environment respresen­ tation;
• Formalization of robot manipulating ac­ tivities (plans, actions);
• Development of a Sjstem for checking the correctness oi plans;
• Development of a system for the optimi­ zation of plans;
• Development of a system for plan forma­ tion, of means-end type;
• Development of a system for plan for­ mation, based on partial ordering of ac tions.

D. Role of Classical and Non-Classical Logic.

The ?ROLOG language has been experimented in application to robotics.

The limitations on the present day rela­ tionals programming languages, have been consider~d , mainly in the adoption of · search st~ategies.

When FIRST ORDER PREDICATE LOGIC is uti­ lized as a programming language, it is essential not only the possibility of pr~ ving a theorem but also the · bechni~ue followed within the proof.

The logic programming language has been arranged in two levels, both using pre­ dicates.

Thus, the program becomes a couple, i.e . . representation program and control pro­ gram.

Interesting research results,have been ob­ tained, mainly in the semantic domain of robotics, and in using temporal features in logic [19, 20, 21, 22].

1. Natural Language Understanding. A quite large system, the DONAU (Domain Oriented NAtural language Understanding) system has been developed for understan­ ding Italian.

A first version of DONAU has been deve­ loped and tested, with success, in the se mantic domain of robotics.

DONAU is written in LISP and HICRO:?LANNER and is based on the orevious work done by the Artificial Intelligence Group of the University of Grenoble, France (di­ rector G. Veillon, with J.C. Latombe, A. Lux) in developing the PIAF system for the syntactic, morphologic, and pho­ netic analysis of French and Italian.

A joint research program on PIAF and DO­ NAU has been developed anC :inancially su~ ported , between Milan and Grenoble.

The semantic analysis of the Italian input sentences is based on a discrimination net.

The extraction of operative information and the control of legality are nart of the mo dular architecture of DONAU 1f3,24,25,26]-:-

Also first studies in the semantic domain of data-bases have been developed [27, 28] .

F. Robotics.

In the Laboratory of Robotics of the .11'?-AI '?roject, a two arms, two light sensors~ix force sensors, six degrees of freedom ro-· bot, the SU:?ERSIGMA robot, is now operat­ ing.

Its main tasks are devoted to the assem­ bly of complex mechanical systems.

The SU'?ERSIGHA architecture is composed of eight NATIONAL SC/HP microcomputers, one LABEN 70 minicomputer; it will be e­ ventually connected to the UNIVAC 1108 computer.

The research activity in this field has been devoted to the following goals

• emergency recovery problem: the problem solving techniques have been applied to automatically solve the problem of recovering from the interruption of the execution of the normal assembly algo­ rithm, when defective component parts are encountered [2 9, 30] ;
• -assembly language: the HAL (r1ultipur~o­ se Assembly Language) language has been developed for enabling the mechanical designer to describe the assembly algo­ rithm; the !ffiL translator can execute either the source program (the determi­ nistic assembly algorithm) or the out put of a simple plan formation program which receives, as input, the SU?ERSIG­ l-1A task representation;
• multimicrocomputer architecture: the u se of eight microcomputer enables the­ conception of the whole SUPERSIG!ffi robot as a special computer (and not as a computer connected to the mecha­

This special computer has a set of ma­ chine instructions which is composed by the classical machine instructions of the LABEN 70 minicomputer augmented of new machine instructions (e.g., !10VE

• nical structure). A x~, GRASP, etc .).

Such new machine instructions correspond to the problems whose solution algori­ thms are programmed in each microcornnu ter [ 31 , 32, 33]. --

• manipulating of concurrent tasks: both the SUPERSIGHA architecture (with the parallel activity of the eight micro­ computers) and the HAL design (with the execution of concurrent processes con­ trolled by a circular precedence sche­ duler) enable the execution of concur­ rent manipulating activities; the ef­ ficiency increase in the execution of task in ;:he goal of the present re­ search activity [;34];
• social and economic implication of robo tics: the organization of work in the­ factory assembly lines is going to be greatly influenced by the advent of robots; these research problems are presently investigated T35, 36].

- 2. PISA .

This research group has been formed since 1971 by Ugo Hontanari and has developed a great deal of theorical and experimen­ tal reserach in A.I.

1. Problem Solving. The chromosome matching has been consi­ dered as a target for investigating the efficiency of the Hart-Nilsson-Raphael algorithm; new properties of this algo­ rithm have been introduced.

The foundations of dynamic programming and the relationships with heuristic searc: methods have been investigated by showing that the AND/OR graph is a general model of dynamic programming and that ·each dy­ namic programming problem can be reduced to the problem of finding an OPtimal so­ lution tree in an AND/OR graph- [ 38 , 39,4g .

In particular, a heuristic search algori­ thm has been Presented, which combines the advantages of dynamic programming, i.e.,the identification of common subpro­ blems, with the advantages of branch-and­ bound, i.e.,the use of heuristic estimate to speed up the search [41].

The study of deriving, from a decision ta ble, a decision tree which is optimal in same sense, has been recently investigat­ ed.

In particular, the minimization of the average execution time has been obtained by utilizing heuristic information ~2].

The generalization of AND/OR graPhs has been investigated, and the relationship with grammars has been introduced 83].

1. Theorem ~roving. In the line of Kowalsky, the logic for­ malisms have been considered as nrogram­ ming languages,the proof checkers as in­ terpreters.

Thus a powerful logic formalism and an efficient proof checker can allow to pro ve manually theorems whose automatic proof would be otherwise very far from the sta­ te of the art.

A new type of efficient unification algo­ rithm has been designed [44] .

Hore recently this unification algorithm has been merged with Boyer and Hoare's techni~ue for storing shared structures in resolution based nroof checkers [45] .

1. Languages for Artificial Intelligence. A new version of LIS~, HA�~ffiLIS? has been developed by Hontangero, :?acini, and Tur­ rini in the last years .

The characteristic of its interpreter ena blesthe availability of powerful primiti=

ves useful for developing, within ~1A�f1A­ LISP, non-deterministic languages.

One of such languages,ND-LISP, has been proposed and implemented.

Levi and Sirovich have developed a pattern matching language and a descumination net work for efficient pattern matching.

This tools are available on an IBH 370 com puter, together with INTERLIS? .

The application to automatic and inter­ active program verifiers is currently be­ ing investigated.

- 3. TURIN.

Research activity in Speech Understand­ ing has been carried on since 1971 [46] .

The use of syntactic methods for automa­ tically interpreting speech pattern,has bee n investigated.

The utility of such method is sustained because most of the phonetic knowledge o f a language is available in terms of de scriptions of spectral patterns or lin guistic events ~7] .

The problem of representing and using such knowledge in a digital computer has been studied .

The details of the implementation of a s yntax controlled acoustic encoder of a speech understanding system (SUS) have been discus .-:- ~ d.

Moreover, the learning ciapability in the SUS system has been developed

Present research activity is devoted to choose a semantic domain, e.g., robotics, in which the application of the SUS is practicable.

- 4. PADUA

Since 1974 1 Enrico :?agello is developing a new group devoted to A. I. researches.

LI~? , 3k0Lv2 , and REDUCE constitute the available languages for experimental acti vity.

The main research work is devoted to theo­ ~ical investigations on the role of logic ln A.I.

In particular, the main research direct­ ion is constituted by the use of logic as a programming language for describing both the problem and the central repre­ sentation to a robot plan formation- sy­ stem [20, 21, 22]. -

REFERENCES - ITALIAN CONTRIBUTION

• t1. SOHALVICO : The Hilan T)olytechnic Artificial Intelligence :?reject. ?re­ ject Technical Report·1977. HEHO tt?-AIM-68 ·(In Italian).
• SANGIOVANNI VINCENTELLI and M. SOr1ALVICO : Theoretical Foundations of State-Space ADProach to Automatic '?roblem-soiving.- 1In Italian). Alta Fre~uenza. Vol. XLIV, N.3. Harch 1975.
• SANGIOVANNI VINCENTELLI and r1. Sm1ALVICO : T)roblem-Sol ving Hethods in Computer Aided Hedical Diagnosis. '?roceedings Twentyth International Scientific Conference on Electronics. Rome, Italy. Harch 1973.
• A. SANGIOVANNI VINCENTELLI and H. S0l1ALVICO: State-Space Aporoach in '?roblem-Solving Optimization. ?rocee­ dings Fifth IFI:? Conference on Opti­ mization Techniques. Springer Verlag, New York, Inc. Rome, Italy. May 1973.
• A. SANGIOVANNI VINCENTELLI and H. S0~1ALVICO: Theoretical Asnects of Sta te-Space Approach to '?robiem-Solving~ Proceedings Seventh International Con gress on Cybernetics. Namur, Belgium~ September 1973.
• HANDRIOLI, A. SANGIOVANNI VINCEN­ TELLI, and H. S0t1ALVICO : Toward a Theory of '?roblem Solving. Harzollo, · A. (ed.). Topics on Artificial Intel­ ligence. Springer Verlag, New York, Inc. October 1973.
• D. ~11\NDRIOLI, A. SANGIOVANNI VINCEN­ TELLI, and H. S0!1ALVICO : A General Approach to Learning in :?roblem-Sol­ ving. Proceedings NATO Advanced Study Institute on Computer Oriented Lear­ ning '?rocesses. Nordhoff Internatio~ nal '?uglishing, Leyden. Bonas, France. August 1974.
• [a] G. GUIDA, D. HANDRIOLI, A. '?ACI,and H. Sm1ALVICO : A Formal Framework for an Unitary Approach to the Theory of ?roblem Solving. '?roceedings IIASA Workshop on Artificial Intelligence: Question Answering Systems. Laxenburg Schloss, Austria. June 1975.

1. G. GUIDA, D. MANDRIOLI, A. ~ACI, and M. SGr1ALVICO : An Integrated Theory of ?roblems as an Algebraic Base for Complexity Understanding and Au­ tomatic Problem Solving. Proceedings Seventh IFI~ Conference on Optimization Techniques. Springer Verlag, New York, Inc. Nice, France. September 1975.
2. GUIDA and M. SOMALVICO: Semantics in Problem Representation and Search. Information Processing Letters. Vo­ lume 5, Number 5. November 1976.
3. G. GUIDA, D. r1ANDRIOLI, and H. SOHAL VICO: An Integrated Model of Proble~ Solver. Information Sciences. Volu­ me 12, Number 3. 1977.
4. G. GINI and H. GINI: Cognitive In­ formation Retrieval by Goal Orient­ ed Languages. Proceedings IIASA Work shop on Artificial Intelligence: - Question Answering Systems. Laxenburg Schloss, Austria. June 1975.
5. GINI and H. GINI : Conniver Pro­ grams by Logical Point of View. Proceedings Fourth International Symposium on Hathematical Foundations of Computer Science. Springer Verlag, New York, Inc. Marianske Lazne, Czechoslovakia. August 1975.
6. CORTI, G. GINI, H. GINI,and E. PAGELLO : Mathematical Logic and Goal-Oriented Languages in Robot Problem Solving. (In Italian). Alta Frequenza. Vol. XLV, N. 1. January 1976.
7. Q5] P. CORTI, G. GINI,and H. GINI : Ob­ ject Manipulation and Goal-Oriented Languages. (In Italian). Proceedings Thirteenth International Automation and Instrumentation Con­ ference on Human Engineering. Milan, Italy. November 1974.
8. G. GINI and r1. GINI : Control of In telligent Robots and Goal-Oriented Languages. Proceedings Conference on Applied Robotics. Cesky Krumlov, Cze­ thoslovakia. Hay 1975. Also, The Industrial Robot. Volume 2. Number 2. June 1975.
9. (17] G. GINI and H. GINI: Programming a Robot by Goal Oriented Languages. Proceedings Third Workshop on Graphsr Systems, and Cybernetics. Bucharest, Roumania. August 1975.
10. G. GUIDA and ? . RIVERA: A !1odel for a Robot ~lanning System. ·HEHO'MP-AIH55.
11. ?AGELLO : Logic for Robots. (in Italian) . Proceedings Thirteenth International Automation and Instru­ mentation Conference on Human Engi­ neering. !1ilan , Italy. November 1974.
12. ?AGELLO : Logic and Interpreters. :?roceedings IIASA l·lorkshop on Arti­ ficial Intelligence: 0uestion Answe­ ring Systems. Laxenburg Schloss, Austria. June 1975.
13. COLOMBETTI and E. PAGELLO: Pro­ grams, Computation and Temporal Fea­ tures. Proceedings Fifth Internatio­ nal Symposium on Mathematical Found­ tions of Computer Science. Springer Verlag, New York, Inc. Gdansk, :?oland. September 1976.
14. M. COLQI1BETTI and E. PAGELLO : A Logical Framework for Robot Program­ ming. :?roceedings Second CISr1-IFTGr1H Symposium on the Theory and :?ractice of Robots and Manipulators. Warsaw, ?oland. September 1976.
15. GINI and H. GINI: A Natural Orien ted Language Based Question Answering System. :?roceedings SSCS Workshop on Computer Models of Natural Lan­ guage, Casuality, and Intention in Language Understanding. Castagnola, Switzerland. August 1975.
16. BERNORIO, M. BERTONI, A. DABBENE, and M. SOMALVICO : r1an-Machine In­ teraction in Quasi Natural Language. (In Italian). :?roceedings Annual AICA Conference. Milan, Italy. October 1 97 6.
17. BERNORIO, M. BERTON I, A. PABBENE, and H. SOMALVICO: A Domain-Oriented Natural Language Understanding Sy­ stem for Han-Machine Interaction with Dynamic Data-Bases. :?roceedings IIASA ~orkshop on Natural Language for Interaction with Data Bases. Laxenburg Schloss, Austria. January 1977.
18. BERNORIO, r1. BERTONI, A. DABBENE, and M. Sm1ALVICO : Quasi Natural Lan guage Understanding in the Semantic­ Domain of Robotics. Proceedings Con ference on Applied Robotics. Plsen~ Czechoslovakia. October 1977.
19. G. GUIDA: Artificial Intelligence Techniques for the Design of Data Bases. (In Italian)· ~roceedings An-

• nual AICA Conference. Milan, Italy. October 1976.
• GUIDA: Ideas About Design of Na­ tural Language Interfaces to Query Systems. Proceedings IIASA Workshop on Natural Language for Interaction with Data Bases. Laxenburg Schloss, Austria . January 1977.
• GINI, H. GINI,and H. SGr1ALVICO: Emergency Recovery in Intelligent Robots. Proceedings Fifth Interna­ tional Symposium on Industrial Ro­ botics. Chicago, Illinois, USA. September 1975.
• [3o] ?. CORTI, G. GINI, M. GINI,and M. Sat1ALVICO : Problem Solving and Automatic Emergency Recovery: Towards the Design of Intelligent Industrial Robots. ?roceedings Second CISH-IFTOHM Symposium on the Theory and Practice of Robots and Manipulators. Warsaw, Poland. September 1976.
• MEZZALIRA and M. SOHALVICO : Towards Firmware Problem Solvers. Proceedings International Symposium on Mini- and Microcomputers and Their Applications. Zurich, Swit­ zerland. June 1975.
• AIRAGHI, G. BERTIN, L. HEZZALIRA, and t1. SOMALVICO: Design and Expe- ' rimentation of a t1icroprograrnrned Problem Solver. Proceedings Inter­ national Symposium on Hini- and Hicrocomputers and Their Applica­ tions. ZUrich, Switzerland. Harch 197 6.
• BISIANI and R. CASSINIS: The Development of a Multi-Microproces­ sor System to be Used in the Control of an Industrial Robot. Proceedings International Symposium on Mini- and Microcomputers and Their Applications. ZUrich, Switzer land. March 1976.
• COLOt1BETTI, :?. CORTI, and E.PA­ GELLO : Hanipulating by High Level Languages. Proceedings Conference on Applied Robotics. Plsen, Cze­ choslovakia. October 1977.
• ?AGELLO and G. '?ASQUALOTTO Artificial Intelligence: A New Scien tific Ideology or a New Technology?­ Scientia. Autumn. 1973.
• CIBORRA: Industrial Robots and Organization of Work. Proceedings Twentythird International Scienti-
• fie Conference on Electronics. Rome, Italy. March 1976.
• HONTANARI : Heurstically Guided Search and Chromosome Hatching. Artificial Intelligence, Vol. 1, n.4. 1970.
• HARTELL! arid U. MONTANARI : On the Foundations of Dynamic Programming. Topics in Combinatorial Optimization (S. Rinaldi ed.) CISH, Springer Ver­ lag.
• t1ARTELLI and U. MONTANARI ? ro­ grammazione Dinamica e ?unto Fisso. Atti Convegno di Informatica Teorica, Hantova. November 1974. 1-19. (In Italian).
• t1ARTELLI and U. !10NTANARI : From Dynamic Programming to Search Algo­ rithms with Functional Costs. ?roc. Fourth Int. Joint Conf. on Artifi­ cial Intelligence, Tbilisi. Septem­ ber 1975. 345-350.
• t1ARTELLI and U. MONTANARI : Addi­ tive AND/ OR Granhs. ?roc. Third Int. Joint Conf. on Artificial Intelligen­ ce, Stanford-August 1973. 1-11.
• MARTELLI and U. HONTANARl: Optimi­ zing Decision Trees Through Heuristi­ cally Guided Search. Internal Report B76-22. IEI-CNR. Pisa. November 1976.
• LEVI and SIROVICH F.: Generalized AND/OR Graphs and Their Relation to Formal Languages. Internal Report B73-15. IEI-CNR Pisa. November 1975.
• A. ~1ARTELLI and U. MONTANARI: Unifi­ cation in Linear Time and Snace: A Structured Presentation. Internal Report B76-16. IEI -CNR. '?isa. July 1976.
• A. t1ARTELLI and U. !10NTANARI : Theo­ rem ?roving with Structure Sharing and Efficient Unification. Internal Renort S-77-7. ISI. Universita di ?isa. February 1977.
• A. R. t1EO and G. U. RIGHINI: A new tech nique for Analyzing Speech by Compu-­ ter. Acustica, vol. 25, pp. 261-268. Nov. 1 971.
• DE MORI : Syntactic Recognition of Speech Patterns. Communication and Cybernetics. Volume 14: Syntac­ tic Pattern Recognition, Applications. Ed. K.S. Fu. Springer-Verlag,Berlin, Heidelberg.1977.