Implementing a Multi-Agent Problem Solver in Jason

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 ¹ (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.

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 .

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

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.

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.

• 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]]
  

• 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

• Back to Yokoo's definition of 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 (x_i, current_value), and if all communicated nogoods are not compatible with the agent_view and (x_i, 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 (x_i, current_value) if all variables in the nogood have the same value in the agent_view and (x_i, 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.

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

• 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

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.

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.

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.

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.

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.

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.