Proceedings of STeP'96. Jarmo Alander, Timo Honkela and Matti Jakobsson (eds.),
Publications of the Finnish Artificial Intelligence Society, pp. 115-121.

An Object-Oriented Distributed
Problem Solving Environment

Martti Paajanen
ViSolutions, Inc.
P.O.Box 458
00101 HELSINKI, Finland
Tel. +358 0 567 3608 / +358 40 505 4543
e-mail Martti.Paajanen@icl.fi

Abstract

This paper describes an object-oriented approach for building distributed problem solving and decision support systems. The framework has been developed to solve problems encountered in building decision support applications for business planning tasks e.g. in the areas of strategic planning and budgeting, where the distribution of decision making authority and the nature of the tasks favours the implementation of a distributed support environment. The framework is based on MUST Modeller(TM), a flexible application development and modelling tool developed by ViSolutions, Inc., in Helsinki, Finland. The MUST development has been partially funded by the Technological Development Centre of the Finnish Ministry of Trade and Industry (TEKES).

1. Background

Business decision-making problems encountered in larger organisations have typically certain characteristics that motivate the employment of distributed problem solving techniques, and can be used to derive requirements for the support system:

There are decision-making tasks that repeat themselves in basically the same form within different periods.
The members of the decision-making teams have roles that are related to their tasks and positions within the organisation. These roles can define the scope of allowed decisions and decision options, available information and possible ability of readjusting assumptions of the problem-solving environment.
The roles have typically hierarchical structures that reflect the organisational positions and responsibilities of the decision makers. The decision power associated with the roles is derived from these positions. This determines the ability of setting and adjusting goals and associated targets, and the set of decision options available for each decision maker.
The decision maker roles can often be used to guide the design of the structure of the decision support environment. The different roles need different support agents, and the inter-agent cooperation strategies need to support in the achievement of the overall objectives set to the decision-making team. Typically the agents support in the solution of some sub-problem, whose assumptions and solution interact with those of the other sub-problems.
Each sub-solution is defined by a set of goals and constraints it must satisfy. The detail level approach taken to local decisions is assumed to be uninteresting from the global point of view, which means that the decision makers are assumed to be autonomous within their responsibility area as far as overall objectives are met.
The decision making is asynchronous and can be distributed in time and space. The progress of the problem-solving process requires exchange of goal and sub-problem information between the agents. The goal structure guides the local decision making to make decisions that change the state so that it satisfies the goals.
Each task at hand typically has time constraints and schedules, and a solution (hopefully the best available by the time limit) is reached in each case. For instance, a budget for an organisation is made by the date it is handled and accepted by the board, and every effort is taken to make a budget that satisfies the objectives set by the board.

The decomposition of the overall task into a distributed problem-solving environment reflects the organisational responsibilities. This division of the tasks and responsibilities guides the design of the distributed problem solving agent architecture. We have found examples of both task-related and organisational hierarchy related agent compositions. Our experience from practical applications is that the division of tasks and roles in actual organisations is rather stable. Changes in organisation structure, in persons holding different positions, or in objectives on different levels of the organisation due to changes in market or competitive environment can necessitate immediate reactions from the organisation and therefore from the decision support environment. If essential changes in the business responsibilities between the corporate management and division management would be made the design of the decision support system might need to be revised. The basic application structure including inter-agent interfaces for a given task can be assumed to be the same over several problem- solving situations. We have found the approach presented by Wooldridge and Jennings (Wooldridge- Jennings 1994a) useful for positioning the efforts in the field of DAI (Distributed Artificial Intelligence). To define and analyse problem solving agents in more detail, the following dimensions can be seen:

Agent theories are mathematical and logical formalisms developed for representing and reasoning about the properties of agents.
Agent architectures are construction models and paradigms for the implementation of computer and software agents and inter-operating groups of agents.
Agent languages are software systems for the construction of agents.

Within this framework, we propose an agent architecture for business decision support applications, based on an agent language, which in our case is based on the MUST object-oriented modelling platform.

2. The Problem Solving Framework

The problem solving application framework consists of a set of agents implemented as object models, communicating together to support the human decision makers in their solution of decision support tasks in a coordinated fashion. In object-oriented decision support applications the object model is used to define the domain model containing application area specific knowledge and problem solving ability. To make several such application agents cooperate in a useful way the agents must have a problem-solving support model that maintains knowledge and awareness about the problem solving tasks, their objectives, and the current situation in the model in relation to these objectives. The framework consists of several agents, each implemented as an object-oriented application, having the following structure:

The problem solving model contains the following elements:

Definitions of the objectives represent the goals of the agent, and they are used for evaluating each situation in relation to these goals. As the object models of the problem-solving application are typically used by a human decision maker the changes in the model are initiated by actions of the user. The changes either move the subsolution modelled by the application closer to its goal or further from it. Therefore it is necessary to calculate in the application the distance from the goal in possibly several dimensions so that the progress of the problem solving can be enforced by useful feedback given to the user.
Another similar component is formed by the constraints set to the agent by its problem-solving role, or the role of the agent or its human user within the overall organisation. If some variable values within the application can only be changed within preset limits or if these limits are dynamically communicated by other agents, each agent needs a mechanism to calculate the current situation in relation to the constraints and give feedback to all attempted changes that would violate the constraints.
Definitions of the elements needed to monitor changes in the application model that necessitate communication between the agents are needed for initiating inter-agent communication when some subresults are achieved, or when in some object model a change needs further information, updating or querying the constraints, or passing of information to other agents. These definitions are based on the calculation dependency control capability of the calculation rule language, and the ability of implementing method-like constructs using calculation rules.
Definitions of the inter-agent communication control and behaviour use information management system classes of MUST to produce the contents of the messages sent to other agents and to interpret the contents of the received messages.
Inter-agent communication is based on sending messages consisting of object definition macros between the agent applications. In MUST, each object (both the classes and instances) can produce a definition macro that reproduces a similar object. When such a definition is interpreted in the context of another agent application it creates a new object that is defined by the class structure of the other application.

Our approach is based on MUST Modeller, an object-oriented modelling and application development tool (Lehto 1995). MUST has features that combine benefits of declarative programming to the object oriented modelling environment:

The MUST objects have two kinds of attributes: typed data attributes and relations, whose values are links to other objects. The relation attributes provide an effective way for representing structural information and dependencies between individual objects.
MUST has a calculation rule language which is used to declaratively define calculational properties of the attributes. The dependency maintenance mechanism guarantees consistency of the model still allowing delayed calculation for performance purposes.
In addition to this declarative and functional nature the calculation rule language has extensions for controlling the calculation and a set of operations with side-effect, which can be used to create procedural definitions. These features can be used to implement methods and message passing structures. Together with the ability of monitoring calculation and value invalidation this makes it possible to define objects that monitor defined values and have a degree of awareness of the calculational events in the model.

The object-oriented approach supports problem abstraction and representation of it in a class structure. The structural and calculational properties of the problem domain are declaratively defined as an integral part of the object structure. An essential element of MUST's application building tools is the calculation rule language and its dependency management and consistency maintenance methods. They provide the tools for implementing the problem-solving agents' mechanisms for recognising the changes in their knowledge base and their problem-solving status.

3. Applications

We have employed the framework in the implementation of decision support applications in the areas of strategic planning and financial planning or budgeting. Applications with their objectives and lessons learned have been described by Paajanen (Paajanen 1996). The evaluation of distributed problem solving applications can be made to consist of the development of validity axioms and their proofs. As the framework is based on an object-oriented tool utilising descriptive calculation rules, the axioms can be based on those developed for the underlying modelling platform (Lehto 1995). Because the object model is a descriptive representation of the logic related to the problem domain and problem solving methods, the development of axioms that are required to hold during the progress of problem solving is the basic approach to validation. Technical elements of such validation schemes would include:

Development of axioms the application model is required to satisfy during all phases of problem solving.
Development of traditional software validity proofs for procedural parts included in side-effect calculation rules used to implement methods attached to object classes.
Analysis of the structure of the application model (both the domain model and the problem solving model) to ensure that the model covers all elements needed for the application.
Analysis of the problem solving coordination and control strategies to be able to ensure convergence towards a solution.
Analysis of the functionality of the application especially in comparison to predefined user expectations.

To validate a distributed problem solving system based on the proposed framework one has to find a validation to each agent model and then be able to validate the communication and communication based coordination schemes for the group of agents. On the agent model level the declarative nature of the object model definitions makes the effort of validation theoretically simpler than in the case of procedural definitions. In addition, as the definitions are declarative, the increase of complexity of the models does not necessarily complicate the validations, as each declarative definition can be seen as an axiom stated about the model. To validate the inter-operation of the agent models one should be able to find proofs for the correct exchange of object definitions between the object models. The agent level validation for the applications built using the framework presented here can be seen to consist of two elements: the validation of the domain model and the validation of the problem solving model. The validation of the domain model is based on the specifications and functionality descriptions made with the application users to define the required application characteristics. The essential requirement for the problem solving model is that it correctly evaluates the state of the model against the goals and handles the communication between different agents according to interface definitions. A basic guideline for the validation is based on defining and monitoring the following axioms about the problem solving model:

At all times each agent knows the existing goals, their target values and how the current comparison value is calculated, and can thus calculate the difference between target and current values.
Each agent has an ability to evaluate the progress of the problem solving, and is able to measure its possible actions against that information.
At all times each agent knows which goals are satisfied and which are not.
At all times each agent knows which object definitions to send to which other agents, and knows when transmission should be done. In addition, each agent must know the communication channel to the other agents.
At all times each agent knows which agents can send object definitions to it and what are the communication channels it must check. As communication can be asynchronous, the channels must provide a buffering capability and the agents must be able to retrieve the messages in chronological order.

Basically the proof of the validity of these axioms in the framework of the previous chapter is based on the validity of the underlying object model representations.

References