MRG home page · Research · Publications · Projects · Software · People

Linear Logic and Dialogue Planning


We propose a framework for agent communication based on Linear Logic which aims to simplify the task of agent design. In particular, our goals are to allow significant reuse of agent specifications as well as make agent interaction robust to unexpected events and failures. Using Linear Logic as the foundational machinery also improves upon previous plan-based dialogue systems by providing a clear underlying logical model for dialogue planning. This has applications in human-computer interfaces as well as agent interaction such as that proposed for the semantic web.


Customer: Hello, I'd like a white coffee please.

Seller: Sugar?

Customer: Yes please.

Seller: OK, that will be one pound fifty.

Customer: (gives Seller the money), here you go.

Dialogue planning refers to the process of deciding what to say in order to achieve some goal. Even in simple dialogues from our daily life, we must be able to handle interruptions, while maintaining dialogue context to ensure that relevant responses are given at the correct time. The above example shows how this might be the case in a coffee ordering scenario - the question about sugar can be seen as an interruption to the original request, while the customer knows that in order to proceed to achieve her goal she will need to answer the question first.

We propose a Linear Logic representation for modelling dialogue planning, hypothesising that by viewing speech acts as planning operators, a formal representation of the structure of human dialogues can be given in Linear Logic. By specifying these planning operators in Linear Logic, this representation aims to provide a simple and robust framework for agents interaction while maintaining expressivity.

The resource-sensitive nature of Linear Logic means that it is able to provide a formalism for STRIPS style planning. This has the advantage of modelling actions without explicit frame axioms, while allowing internal states of agents to be modelled as resources.

A robust framework would allow failures which occur in planning or execution to be handled correctly. Additionally, our framework aims to make the specification of agents reusable across different domains.

Using Lolli, a Linear Logic programming language developed by Hodas and Miller, we tested our hyposthesis by building a system which illustrates how various speech acts and physical actions can be represented by Linear Logic.

Documentation and Publications

Source code for Case Studies

The case studies in the paper Plans, Actions and Dialogue using Linear Logic have all been implemented and be found in the case studies directory. Examples 1-5 are the coffee selling domain and example 6 is a reimplementation of the door problem described in Power'79. Examples 1-5 separate the world from the agent specification files and use Lolli to automate communication between distributed agents. Example 6 uses a simpler (in terms of Lolli code) approach where the world is modelled within the agent's definition and communication is copy and pasted by hand. Note Power's example can take several minutes when running in Lolli under Alice and upto a minute running in Lolli under other SML platforms.

[R. Power (1979) "The organisation of purposeful dialogues" Linguistics 17, 107-152.]

We have also used the framework for teaching Agent Based Systems:

Implementation in Lolli for Alice

The software we have used to implement our system is a ported version of Lolli which runs on Alice and has two additional commands:

Download our ported Lolli for Alice (tar-gzip of source). This requires version 1.4 of Alice.

Our local copy of the documentation is available here.

A Little Related Work:

Mathematical Reasoning Group, Informatics Forum, 10 Crichton Street, Edinburgh, EH8 9AB, Scotland
Tel: +44 (0)131 650 2733      Fax: +44 (0)131 650 6899
Please send corrections and suggestions for this page to the Lucas Dixon
Unless explicitly stated otherwise all material on this web site is copyright © The University of Edinburgh.