Overview

Introduction

An important feature of an advanced coordination and control system is the ability to plan ahead, thus avoiding problems before they occur and offering the possibility to optimize system performance.

To realise this highly desirable functionality, it is necessary to be able to to predict the behaviour of the underlying system and provide an accurate forecast.

Food foraging behaviour in ant colonies is the source of inspiration for the design for the emergent generation of short-term forecasts in coordination and control systems. This design is applied to multi-agent manufacturing control systems. Finally the PROSA reference architecture and the delegate MAS architectural pattern is combined into one system.

Ant colonies

Food foraging in ant colonies is the source of inspiration for the design of self-organizing systems. Ants coordinate each other’s behavior through signs in the environment. Ants are able to locate a food source or the way back to their nest without interacting with their environment or with other ants. They do this by observing  signs in the environment and placing signs themselves.

Figure 1: Food foraging in ant colonies

Ants execute a simple procedure:

• In absence of any signs in the environment (consisting of scents from a pheromone), ants perform a randomized search for food.
• When an ant discovers a food source, it drops a smelling chemical substance, a pheromone, on its way back to the nest while carrying some of the food. Thus, it creates a pheromone trail between nest and food source. This pheromone trail will evaporate if none of the other ants deposes fresh pheromones.
• When an ant senses a pheromone trail it will be urged by its instinct to follow this trail to the food source. When the ant finds the food source, it will return with food, while depositing pheromones itself. In this manner, the strength of the pheromone trail is maintained and even reinforced.
• When the ant finds an exhausted food source, it starts a randomized search for a new food source and the trail disappears because of the evaporation.

These simple behavior patterns result in an emergent behavior of the ant colony that is highly ordered and effective at foraging food. Global information (where to find food in a remote location) is made available locally (in which direction must the ant move to get to this food).

The main achievement is that individual ants are not exposed to the complexity and dynamics of the situation. Instead, the environment is incorporated into the solution and allows the overall system to cope with its complexity. None of the ants need a mental map of the environment. There is no information in the head of the ants that reflect reality. The evaporation and refreshing of the pheromone trails allows the ants to cope with the dynamic environment.

For the design and development of coordination and control systems, the following principles are recognized:

• Make the environment part of the solution to handle a complex environment without being exposed to its complexity.
• Place relevant information as sign (pheromones) in this environment ensuring that locally available data is provided about remote system properties, supporting system-wide coordination.
• Limit the lifetime of this information (evaporation) and refresh the information as long as it remains valid. This allows the system to cope with changes and disturbances.

These engineering principles are used to design an emergent forecasting multi-agent schema for manufacturing control systems and other application areas.

Delegate Multi-Agent Systems

A delegate multi-agent system is a swarm of functionally homogeneous agents that explore multiple alternatives concurrently for individual agents in a manufacturing system.

The delegate MAS pattern consists of three elements: the environment, the agent and the ant. This section discusses each of these elements together with the relations between the elements.

Figure 1 shows a module view of the delegate MAS pattern.

Figure 2: Delegate MAS: module view

Environment

The environment is a software representation of the world of interest. The environment contains a directed graph, which may change over time. The nodes in the graph represent a location in the world of interest and the edges represent the connections between different locations. An agent is located on a node in this graph.

The environment contains a pheromone infrastructure. Ants deposit, observe and modify pheromones in the pheromone infrastructure.

Agent

An agent delegates a responsibility to a swarm of lightweight agents. These agents are called ant agents from now on. This delegation involves two main responsibilities: maintaining the swarm of ants and interpreting the results made available by the ants in the environment.

The agent is responsible for maintaining the swarm of ants. This responsibility involves maintaining the population size and the diversity of the swarm. An individual ant is not aware of these swarm properties.

Interpreting the results involves fetching the pheromones on the node on which the agent is located and interpreting these pheromones. The interpretation depends on the responsibility that is delegated by the agent.

Note that delegation is not the same as total dependency. The swarm of ants supports the agent by providing a service. If this service is not delivered properly, the agent should exert its best effort to cope on its own.

Ant

An ant is responsible for executing a task that serves a responsibility of the issuing agent. For instance, the ant explores one possible solution or the ant follows one possible path to find food.

The ant is created and initialised from the agent and travels autonomously. The ant has its own life cycle. Each ant may only perform a bounded computational effort within its bounded lifetime and has a bounded footprint (memory).

Relations between the elements

The issuing agent creates and sends ants into the environment at regular times. The agent may use a different creation frequency and initialisation for every ant type. In this way the population size and the diversity of the swarm are maintained.

The environment enables indirect communication between the issuing agents and the ants. Ants from different originating agents or from other generations are able to drop, modify and observe pheromones in the environment. Agents observe the pheromones in the environment. Some of these pheromones contain the results of the different ants. The agents interpret and adapt their behaviour according to these results.

Environment augmentation

The basic PROSA design needs to be augmented in three ways to support agents that implement ant colony
inspired coordination. These agents are called ant agents from now on.

1. Ant agents must be able to navigate virtually through the underlying system.
2. The ant agents must be able to deposit, observe and modify information in this virtual environment reflecting the underlying system.
3. The ant agents must be able to interact in a what-if mode with the other agents in the coordination and control system.

1. Navigation

The multi-agent control system provides a reflection of the underlying system by means of the resource agents. In current implementations, the resource agents implement a navigation graph on which the ant agents can travel virtually through the underlying system. Because this happens in cyberspace, ant agents can travel up and down the underlying system much faster than in reality.

2. Information spaces

PROSA agents and in particular resource agents provide the ant agents with information spaces. These spaces are like blackboards attached to the (resource) agents or entries and exits of the resource agents. Ant agents can  drop, observe, modify and delete any serialize-able software object in these spaces. The objects in such information space have a limited lifetime and disappear after a finite amount of time. If they want to keep it available, the ant agents must refresh information at a frequency above the evaporation rate.

3. What-if mode

The resource agent can be given the ability to operate in a what-if mode (in addition to and in parallel with the normal operating mode), meaning the agent can be designed to be knowledgeable on how a resource will behave without the need to actually bring the resource in that situation. Ant agents inform the resource agent about the intentions of prospective users, from which the resource agent computes its expected workload, which can be used to answer the what-if queries.

For example:

A conveyor belt agent not only knows its status (switched on, speed setting, identity of the connected resources, identity of items on top, etc.), but the agent also can give informed answers about an anticipated but still fictitious future. For instance, the resource agent can answer questions like ‘‘if a pallet were to arrive in half an hour, at what time will it reach the other side of the belt?’’

Ant agents

 There are 3 types of ant agents, which serve a different purpose. They are explained briefly here. To read more detailed information about the different ants, go to this page.

• Feasibility ant agents travel virtually through the factory in the opposite direction of the production flows. They put signposts on the information spaces enabling order and product agents to decide locally which routing options are available to them. If an agent obeys these signposts, the order will eventually get produced in a technically correct manner.
• Exploring ant agents are scouts that each search for an attractive route through the underlying system that accomplishes the given task. They search forward from the current state of the task on or backwards from the final delivery point. They have to work in  a sufficiently large group to ensure the ant colony will work.
  Exploring ants virtually execute a sequence of processing steps which involves a given task. Their choice of strategy depends on certain criteria (time / cost), is randomised and biased toward the choices that proved successful and choices that are unexplored.
  In the end, the explorer agent will report back to his associated agent. This will provide the product and resource agents with options to achieve their goal. The main advantage is that the emergent forecasting does not rely on which strategy is employed by these scouting agents.

Figure 3: Exploring agents

Example:

Consider an explorer agent moving forward from the current position of a work piece on a conveyor belt. The scout queries the conveyor belt agent about the estimated remaining traveling time on the belt. The explorer agent then virtually travels to the exit of the belt and adjust its internal clock indicating the expected arrival time.

At this point,  the exploring ant retrieves the signposts, placed by the feasibility ants, and presents them to the associated product agent to learn the available routing options. The exploring ant selects one of the available options and continues its virtual journey.

When the exploring ant arrives at a processing unit (e.g., furnace), it retrieves the processing capabilities from the resource agent and presents them to the product agent to discover which processing steps can be performed. In addition, the signpost information is used to decide whether leaving the processing unit is already an option. Again, the ant agent selects and virtually executes an option that is available. The explorer agent queries the resource agent of the processing unit about estimated queuing and processing times as well as processing results.

In this manner, the virtual journey continues until the final delivery point is reached. Note that the resource agents will virtually execute their own execution strategies. The emergent forecasting mechanism does not require any specific strategy from these resources.

• Intention ant agents provide the resource agents with an adequate estimate of their future workload. When a suitable set of candidate solutions has been constructed and the estimated starting time for the processing of the product instance(s) approaches, the order agent selects one of the candidate solutions to become its intention (e.g. rush orders rank solutions by their estimated finishing time) and it maintains a small collection of attractive solutions. Then, the order agent starts to create intention ants at a regular frequency to notify the agents of the affected resources of its intentions (Fig. 3).
  The intention ants execute a similar procedure as as the exploring ants except that they set out for their selected candidate solution. Furthermore, they inform the resource agent that their order agent is likely to visit them at the estimated time. In this way, intention agents make a (evaporating) booking on the resource, and the resource agent adapts its local schedule of the resource to account for the visit of which it is informed by an intention ant.

Figure 4: Intention ant

The above enables the coordination and control system to generate short-term forecasts of the system behavior both for resources and orders. It thus suffices to combine software agents that are developed on the basis of local knowledge only, including a what-if self-model, to generate these forecasts that reflect how the system is likely to behave as a whole. There is however one caveat: the order agents must behave in a socially acceptable manner as is discussed below.

Read more ...

Responsiveness versus forecast reliability  

To have useful forecasts, the control system designer must ensure that the order agents have a ‘socially acceptable behavior’. When order agents strongly stick to previously declared intentions, the manufacturing system will be unable to respond to disturbances and it is likely to become locked into the (sub-optimal) routings that got explored first. Conversely, if order agents change their intentions too easily, minor disturbances like a very short breakdown of a resource may create an avalanche of orders that shift to alternative resources, thus the system will behave chaotically and the forecasts will be useless.

Order agents refrain from changing their intentions to easily and too frequently in multiple ways:

• The perceived improvement must be higher than a threshold value before the current intention is replaced by the more-promising alternative.
• The frequency at which order agents may change their intentions, is limited. 

• Different order agents may have different thresholds and frequency limits e.g. rush order agents are more responsive/nervous than unsold make-to-stock order agents.

• Changes of intentions for actions which are further in the future, are favored above last minute changes, as is the case in socially acceptable human behavior.
• A proper distributed design randomizes the behavior of the agents therein, the threshold values, the frequency limits, etc. This avoids that several agents, independently, decide to switch to the same resource/route/etc.
• Order agents change their intentions probabilistically such that within a single refresh cycle only a small fraction of order agents may change their intentions, and the other agents are able to observe the consequences before changing their intentions as well. With such a design, order agents will gradually shift toward alternative routes when a disturbance occurs until a new equilibrium is reached. Note how this last mechanism only works well if there are sufficient refresh cycles between events in the physical underlying system.

  

Combining the PROSA  and the delegate MAS architectural pattern

This section explains the mapping between the PROSA reference architecture and the delegate MAS architectural pattern.

The PROSA reference architecture has three basic holon types (order, product and resource holons) with a corresponding agent and the delegate MAS architectural pattern has three types of delegate MASs: feasibility, exploring and intention MASs.

Each of the three basic PROSA agents is a candidate to apply the delegate MAS pattern. An agent may simultaneously have several delegate MASs. The agent may also use a combination of delegate MASs to handle just one of its responsibilities.

Figure 5 shows one possible mapping between the delegate MAS services and the PROSA base agent types, which is applied in several manufacturing applications. The mapping is most suitable for an order-driven production system with a flow-shop layout. A flow-shop layout is a combination of different production lines, with switches in between. Therefore early choices in routing may hinder product completion later on, since certain operations may not be available on all production lines. The configuration is suitable for order-driven production since only order agents send out intention ants. Therefore, they drive the decision making (although resource and product agents are involved in the decision process, they do not initiate this process).

Figure 5: Delegate MAS versus PROSA

When the mapping in Figure 5 is used, the cooperation between the delegate MASs and the basic PROSA agents has a strong resemblance with how a tourist books a hotel room.

Example:

The feasibility delegate MAS takes care of the marketing. The hotel (resource) spreads word of its existence to other resources so that other ants can find the information. The exploration delegate MAS originates from the tourist order agent. The exploring ants search through these ‘advertisements’ and report the results back to the tourist order
agent. Out of these, the order agent makes a choice. The difference with people is that the agent does not make this choice once, but over and over again. The intention delegate MAS propagates the chosen hotel rooms through the environment. Hotel resource agents have a ‘reservation department’ (e.g., a blackboard) which keeps track of the reservations of the order agents. There is no explicit cancellation strategy. Reservations disappear after a short time if no confirmations are received anymore.

Note that different mappings are also possible and have been implemented in various applications already.

 Traveling analogy

Figure 6: Traveling analogy

To clarify how the MES handles production requirements and produces short-term forecasts in resource allocation, this item utilizes an analogy: human agents making travel arrangements.

Manufacturing Example

This example illustrates how an agent and a delegate MAS cooperate. For simplicity reasons, the example considers a job-shop layout, where all resources are accessible from all other resources. Therefore, the presence of feasibility pheromones, indicating the presence of other resources on the blackboards, are unnecessary in this case. The order agent only makes use of a combination of exploring and intention ants.

Creation of the order

As soon as the order is created (e.g. by the Material Requirements Planning system), a corresponding order holon is created and added to the manufacturing control system. The state of the order is initialised at the entrance of the factory, which in turn is connected to a transporting unit. From this moment, exploring ants and intention ants will start moving periodically and in parallel. The explorer ants will provide the order holon with pheromones and it will compare the various explored paths with the current intention of the order holon. If the explored path is better than the intention, the order holon in this example takes this path as its intention with a chance of 60% if the order holon already had an intention and 90% otherwise.

The exploring and intention ants travel through the environment. On their journey, they request information of the resource holons. The resource holons store these requests and observe and schedule them. The ants fetch the results based on the schedule in the resource holon and travel to the next resource. The bookings from the intention ants create a local schedule on the resource holon that is used to steer production.

Release of the order into production

Once the start time of the next operation equals the current time, the resource holon sends a command to its respective physical entity (the actual machine). It also receives sensory information on the progress of the operation, on eventual breakdowns and on the completion of the operation.

The order agents observe the operation start and stop and keep sending exploring and intention ants during execution. The local schedules are continuously refreshed. If something goes wrong, the ant agents discover this and make this information available. The order agent then decides if he changes his intention or not. If he switches, the old intention is discarded and evaporates automatically.

Removal of the order from the system

Once the order has completed the production process, the order agent is discarded (archived).