Distributed Reasoning

Introduction

There are many reasons why we might want to implement or adopt a distributed approach to reasoning in an AI system:

• Humans do it — psychological models.
• Parallel machines exist – hardware and software.
• Some applications will have improved efficiency and speed up.

Not all procedures a parallelisable. Indeed many AI procedures being very complex can be hard to parallelise. However, many can benefit from speed on a number of nodes alone. A more formal parallelisation – adopting parallel programming paradigms – is obviously advantageous.

• Modular development of systems — Easy to build and maintain and add /delete knowledge and reasoning strategies.
• Multiple reasoning techniques — we can support a variety of techniques some of which might perform better at certain tasks and on certain knowledge.
• Multiple view points — knowledge required when reasoning could be represented in over many domains.
• Reliability — if one module fails then the system may still be functional.

Distributed reasoning systems

A distributed reasoning system is one that is composed of separate modules (called agents) and a set of communication paths between them.

• Each agent usually acts as a problem solving entity itself.
• Many kinds of system exist ranging across:
  • Centralised control systems with shared knowledge,
  • Totally distributed control and knowledge.

Such a system must provide:

• Good coordination between the agents.
• Good communication structure.
• Distributed reasoning techniques.

Rich and Knight deal with aspects of general coordination, control and communication structures. In this lecture we will look at two specific structures that have become popular distributed reasoning mechanisms:

• Blackboard systems.
• Message passing systems.

Blackboard systems

The basic idea of a blackboard system is illustrated in Fig 23.

Fig. 23 Blackboard model

The system consists of:

Knowledge sources

— a set of independent modules containing domain-specific knowledge.

Blackboard

— the shared data structure through which knowledge sources communicate.

Control system

— determined the order in which knowledge sources will operate on entries in the blackboard.

Knowledge organisation and reasoning

• The blackboard structure is highly structured.
• The blackboard prescribes the organisation of domain knowledge and all the input, intermediate and partial solutions needed to solve problems.
• The solution space is organised into one or more application-dependent hierarchies.
• Information at each level of the hierarchy represents partial solutions.
• Domain knowledge is partitioned into individual knowledge sources.
• Transformation in the blackboard hierarchy performed using algorithmic or heuristic procedure by interrogating knowledge modules under the control system.

Consider a group of people assembling a jigsaw with a blackboard:

• Volunteers look at their pieces and select most promising pieces and place then on the board.
• Each member would then look at his/her pieces and see if any fit those already on the board. Those with such pieces evolve the solution.
• The new solutions causes other pieces to fall into place and so on.

For the solution to be a blackboard solution:

• No direct communication is allowed to take place. The jigsaw could be assembled in total silence with no real problems.
• It would not matter who held what pieces.
• All communication is visual on the board.
• Each person is self-activating — knowing when his/her pieces fit.
• No a priori order is established — cooperation is mediated by state of solution on the blackboard.
• The solution is being assembled incrementally and opportunistically — both important attributes of AI blackboard systems.

To illustrate the importance of the control systems consider one constrain in the above problem:

The blackboard lies in a narrow corridor so that only one person can view the board at a single instance.

• We now need some monitor to control how the board is viewed and the puzzle assembled.
• This can be quite simple or could involve a lot of complex strategies, such as viewing everybody’s pieces and deciding which piece fits “best”.
• Care will be needed so as not to compromise the one essential characteristic of a blackboard system, opportunistic problem solving.
• Computer implementations of blackboards often face similar problems.

Implementation issues

The above example illustrates some problems that may arise when implementing a blackboard system. In this section we consider some general considerations needed when implementing and designing a blackboard framework.

Knowledge sources

• Domain knowledge should be divided up so that sources are kept separate and independent.
• Each knowledge source is responsible for knowing the conditions under which it can contribute a solution:
  • A set of preconditions are specified that must be satisfied before the source can be activated.
• Knowledge sources are represented as sets of rules, procedures or logic assertions.
• Knowledge sources only modify blackboard or control data structures. And only knowledge sources modify the blackboard (Fig 23).

Blackboard data structure

• Knowledge sources produce changes to this structure that lead incrementally to a solution.
• The data structure consists of objects from the solution space:
  • input data,
  • partial solutions,
  • alternatives,
  • final solutions,
  • control data.
• Final form of structure is problem dependent although objects are hierarchically organised  tree/graph type structure.
• multiple hierarchies or blackboard panels are permitted.

Control

• Knowledge sources respond opportunistically to changes on the blackboard.
• A set of control modules monitor the changes on the blackboard and a scheduler decides what actions to take next.
• Various kinds of information are made globally available to the control modules and are stored either
  • on the blackboard, or
  • separately in control structures

Their purpose is to focus attention.

• The focus of attention can either be:
  • blackboard structures, or
  • knowledge sources, or
  • both.
• Solutions built up on step at a time. Many kinds of reasoning (e.g. data driven, goal driven, expectation driven) have been applied.