As to evaluate your work done during the tutorial, you have to send your source code (in an archive) at the end of the session to Gauthier Picard

I. Preliminary Concepts and Setup

Jason Environment

In the MAOP course you have already installed a Jason environment. In this tutorial, we will only use the core Jason functionalities (no Jade, Cartago, etc.), and will concentrate on the agent behaviours to solve a toy constraint satisfaction problem: the n-queens problem.

The goal of this tutorial is to implement the Asynchronous Backtracking 1 (ABT) algorithm presented in the course using the Jason language and environment.

We propose to develop ABT in an iterative way. Even if not specified in the exercises, you should test your development step-by-step, using the Jason console and debugger.

Asynchronous Backtracking (ABT)

ABT is the most famous multi-agent algorithm to asynchronously solve distributed constraint satisfaction problems (DisCSP). For more information, have a look at your lecture notes pdf.gif.

As a reminder, here are the main procedures in ABT, excerpt from 1:

ABT Procedures

ABT Procedures

Therefore, the objective of the session is to develop Jason agents that implement these procedures and a multi-agent system that launches some ABT agents to solve a CSP (n-Queens Problem). Since agents will have the same code concerning the ABT implementation, you will create a simple abt.asl file that will be included by all the Jason agent files.

Initializing the project

To sum up, you will have to develop:

  • a .mas2j file describing the multi-agent system
  • a abt.asl file containing the code of ABT procedures
  • as many .asl file as agents in the system, including the abt.asl code using the { include("abt.asl") } pre-processing directive

To simplify the development, we will only consider for the moment the 4-queens problem.

Exercise 1

  1. Launch the Jason editor
  2. Create a new project and save it as 4queens.mas2j in a dedicated directory
  3. Add 4 agents in the 4queens.mas2j file, for instance: 
    MAS abt {
    infrastructure: Centralised
    agents:
            q1; q2; q3; q4; 
}
  4. Create the abt.asl file and include it into each agent file 
    // Agent q1_4 in project 4queens.mas2j
{ include("abt.asl") }

Now, your project is ready for development. You can run it and see agents talking to you.

Data structures

Views and Nogoods representation in ABT

In the remainder of the session, we will consider assignment lists (views and nogoods) as being lists of pairs [X,D] where X is the name of an agent and D is a value. For instance, an agent view or a nogood can be represented as follows for simple integer values: 

[[X1,2],[X2,3]]

Values and Domains in n-Queens Problem

Concerning the n-queens problem, we will represent possible values for agents as [X,Y] pairs. So the domain for the agent 1, in the 4-queens problem, should be: 

[[1,1],[1,2],[1,3],[1,4]]

In fact, it is obvious that queens can't be on the same row, so it is useless to put values for different rows in each queen's domain.

Some useful functions for manipulating structures

Even if shortly described using pseudo-code, ABT relies on prerequisite functions to manipulate the different data structures (views, nogoods, etc.) used during the solving process by each agent. In order to only focus on ABT and agent communication, we provide a set of useful functions in the abt-utils.asl file, that should be included in the abt.asl file using the { include("abt-utils.asl") } file.

Here a short description of each of these functions:

  • remove(V,L,UL) is true if UL is equal to L without V
  • contains(L,X) is true if L contains at least one X
  • includes(L1,L2) is true if all elements of L2 are in L1
  • value_of(X,L,D) is true if D is the value of X in the assignment list L
  • contains_entry(L,X) is true if L is an assignment list and X is on entry in this list
  • add_to_view([Xi,Di],L1,L2) is true if L2 is the same assignment list than the assignment list L1 with a new value Di for Xi
  • add_all_to_view(V,L1,L2) is true if L2 is the same list than L1 with all new values from V
  • add_to_nogoods(Ng,Ngs1,Ngs2) adds a nogood Ng in a nogood list Ngs1, resulting in Ngs2 list, only if it is not already in (nogoods are equal if they are reciprocally compatible)
  • get_agents_from_view(Agents,View) is true if Agents is the list of all agents in View
  • lowest_priority_view_in_agent_view([Xj,Dj],View) is true if Xj is the lowest priority agent in View with the value Dj
  • missing_values_from_links(Links,L,UL) is true if UL is the assignment list containing all assignments [Xi,Di] from L where Xi is not in Links
  • missing_values_from_view(Xi,View,U,UL) is true if UL is the assignment list containing all assignments [Xj,Dj] from L where Xj is not an entry in View and Xi ≠ Xj

Consistency checking

Back to Yokoo's definition of consistency

#consistency

In ABT, agents have to check consistency of some values wrt their current view and nogoods (in the procedure check_agent_view). Let us look at the definition of consistency provided in Makoto Yokoo's book:

(An) assignment is consistent with the agent_view if all constraints the agent evaluates are true under the value assignments described in the agent_view and (xi, current_value), and if all communicated nogoods are not compatible with the agent_view and (xi, current_value).

This means that an agent checks the consistency of a value by :

  • (check 1) checking whether the value has no conflict with values from its view (to avoid conflicts with neighbours)
  • (check 2) checking whether the value and view are not in the same nogood, in order to avoid past errors

Both checks have to success for a value to be consistent. The second check relies on the compatibility definition :

A nogood is compatible with the agent_view and (xi, current_value) if all variables in the nogood have the same value in the agent_view and (xi, current_value).

Some useful functions for checking consistency

As for data structures, we provide some useful functions to check consistency in the abt-utils.asl file:

  • full_consistent(Agent,Value,View,Nogoods) is true if Value is consistent with Agent's View and all Nogoods are not compatible with [Agent,Value]|View (definition of consistency, see above)
  • consistent(D,L) is true is D has no conflict with every value in assignment list L (check 1, see above)
  • uncompatible(Nogoods,View) is true if all Nogoods are not compatible with View (check 2, see above)
  • consistent_values(Values,Agent,Domain,View,Nogoods) is true if Values is the set of all consistent values in Domain wrt the View
  • compatible(Nogood,View) is true if all variables in Nogood have the same values in the View

Constraints in n-Queens Problem

If you look at the consistent rule in abt-utils.asl you will see a call to a rule called conflict. This rule represents the constraints. It is true if the two input values violate a constraint. These rule is not provided because it is problem dependent (conflict differs from a CSP to another).

In the n-Queens Problem, two values are in conflict if they represent positions on a chessboard that are respectively attackable by queens.

Exercise 2

  1. Save abt-utils.asl into your project directory
  2. Read it carefully as to handle all the provided functions (data structures and consistency checking)
  3. Include abt-utils.asl into abt.asl file 
    // abt.asl:
// { include("abt-utils.asl") }
...
  4. Create a file called queen-conflict.asl, and implement the conflict rule for the n-queens problem.
  5. Include queen-conflict.asl into each agent file. 
    // Agent q1 in project queen_4.mas2j
{ include("abt.asl") }
{ include("queen_conflict.asl") }
...

II. Adding Agent Initial Beliefs and Plans

Initial Beliefs

In ABT agents encapsulate several data they manipulate during the solving process:

  • the domain: a list of possible values, represented by a list of values, see above
  • the current_value: a value from the domain
  • the agent_view: an assignment list, see above
  • the nogood_list: a list of assignment lists, above
  • the links: a list of agent names

Exercise 3

Add the five initial beliefs an agent begins with. Initially, an agent has empty agent_view and nogood_list, and outgoing links to agent with lower priority (lexicographical order). The current_value is the first value from the domain.

As a reminder, initial beliefs are facts that are add using the following syntax: 

my_belief(<parameters>).

For instance, for agent q1, we will have : 

current_value([1,1]).

ABT Message Handlers

Reminder: Messages in Jason

In Jason message handlers are specified using beliefs under some conditions, by using the following syntax: 

+my_message(<parameters>)[source(P)]: <conditions> <- <actions>

which means "the agent is able to receive messages called my_message with some parameters from an agent called P. Once the agent receives this message under the given conditions, the agent will perform some actions.

For instance, the following code: 

+propose(Id,Offer)[source(A)] : all_proposals_received(Id) <- !contract(Id).

means the agent can receive proposals using propose messages. If all the proposals are received, the agent will sign a contract for this proposal.

To send messages, we use the .send internal action using the following syntax: 

.send(receiver,illocutionary_force,propositional_content)

In ABT, agents only communicate directly with other agents, so we will only consider the tell illocutionary force. For instance: 

.send(r,tell,open(left_door));

means the agent sends a message open with the parameter left_door to the agent r.

Messages in ABT

In ABT (see the figure), we consider three different kinds of messages (represented as beliefs):

  • ok(Xi,Xj,Dj) message: Xi believes Xj's new value is Dj
  • nogood(Xi,Xj,Nogood) message: Xi believes Xj discovered a new nogood Nogood
  • add_link(Xi,Xj) message: Xi believes it has to add a link to Xj

Exercise 4

Add in the abt.asl file the new (empty) message handlers for the ABT algorithm. For now, the agent does nothing when receiving these messages. These handlers should be atomic2, which is obtained using the atomic annotation, e.g.: 

@lmy_message01[atomic]
+my_message(...)...

where lmy_message01 is a unique label.

Initial Plan and Goal

Commonly, we call !start the initial plan of an agent (e.g. look at the generated agent source files): 

/* Initial goals */

!start.

/* Plans */

+!start : true <- .print("hello world.").

These means that the initial goal to achieve for the agent is !start. To do so, the agent will follow the plan declared using +!start…, which consist here in displaying a message in the console.

In ABT, the first action that agents do is to send their current_value to their outgoing links.

Exercise 5

  1. Create a new !start plan in abt.asl. It will be the starting point for agents. Remove the !start plan from all the agent files.
  2. Modify the !start declaration in order to send ok messages to all the outgoing links. You can implement first a plan to send ok messages to outgoing links and then use it into the !start plan.

III. Deep into ABT

ok Message Handler

When receiving a ok message, an agent simply add/replace the new value in its view and check if its current value is still consistent. To check consistency we will implement the check_agent_view procedure.

Exercise 6

Implement the atomic ok message handler. You should add an empty !check_agent_view plan.

check_agent_view Plan

The check_agent_view procedure will be implemented using a plan. In this procedure, three cases are possible:

  1. the current value is consistent: the agent does nothing and rests.
  2. there is another value in the domain that is consistent: the agent sets its current value to this consistent one, and informs all its outgoing link using ok messages.
  3. there is no consistent value in the domain: the agent has to backtrack as to ask to its ingoing link to change its value. Backtrack will be implemented using a plan named backtrack.

Exercise 7

Implement the atomic !check_agent_view plan for the three presented cases. You should add an empty !backtrack plan.

backtrack Plan

The backtrack procedure in ABT consists in sending nogoods to ingoing agents as soon as a consistency check fails in the check_agent_view plan for instance.

As to simplify the implementation and the computational cost of some checks, we will take a shortcut (proposed by Yokoo in his book). In fact, computing the set of all inconsistent subsets of the agent view requires a certain computation cost. So Yokoo proposes to only consider the current view as a nogood, even if not minimal.

Therefore, we propose to consider only one nogood V (see (iii-a) in the algorithm) which is the current view.

Exercise 8

Implement the atomic !backtrack plan wrt the proposed simplification.

nogood Message Handler

When receiving a nogood, an agent adds the nogood to its nogood list, adds unknown agents (and values) appearing in the nogood and asks for adding links, checks its view wrt the new nogoods, changes its value if necessary and then inform outgoing links of the new value.

Exercise 9

Implement the atomic nogood message handler. You should add an empty !add_link plan.

add_link Messages Handler

Sometimes, all the links are not specified at the beginning of the process, but agents can add links when receiving nogood messages fro mother agent. In short, agents enlarge their social network during the solving process.

Exercise 10

Implement the add_link message handler.

IV. Testing and Debugging ABT

Now, all the procedures required for running ABT properly should be implemented. But does it really work?

Exercise 11

  1. Test and debug ABT on the 4-queens problem.
  2. Test and debug ABT on another n-queens problem.

V. Extra Developments

You have completed all the levels and you are not replete, lets have a look at the following exercises…

Exercise X1

Implement (in Java for instance) an MAS generator that produces a .mas2j, all the .asl agent files, given the size of the n-queens problem you consider.

Exercise X2

Add a termination procedure in ABT, because it does not terminate properly in Jason.

Exercise X3

Extend your ABT solver to implement AWCS (see the lecture notes).

Footnotes:

1 M. Yokoo. Distributed Constraint Satisfaction: Foundations of Cooperation in Multi-Agent Systems. Springer, 2001.

2 Atomic: if an instance of a plan with an atomic annotation is chosen for execution by the intention selection function, this intention will be selected for execution in the subsequent reasoning cycles until that plan is finished. In short, an atomic plan cannot be interrupted by another plan.

Gauthier Picard, October 2013