2. Another transportation problem is scheduling for truck dispatch in surface         mining. In this case, the problem is how to assign jobs to the appropriate         truck so that certain performance demand effectiveness is optimised.

The goals of this transportation scheduling are minimize transport cost and transport time. We are introduced to the concept of multi agents, which can optimise the distribution and execution of tasks (order). The multi agents can handle the situation where the constraints change, such as the arrival of new order or the changing traffic situation.

My study is about using the concept of multi agent for transportation scheduling. There are 2 studies for approaching an optimisation of task assignment in transportation scheduling.
     1. Using Contract Net Protocol and Internal Market Place
     2. Formalized the multi agent transportation scheduling using the concept of          Distributed Constraint Satisfaction Problem.

This paper will provide a description of these 2 studies. It is organised as follows: Starts with a literature review of all the paper that relate to my research in part 2. In part 3, I will discuss about my research, which are 2 studies that I have mentioned above. Part 4 is my conclusion.

2 . LITERATURE REVIEW

The Literature Review will be discussed as follow: Firstly, In part 2.1, I will briefly discuss a concept of agent and multi agent. Follow by description of concept of Contract Net Protocol, Simulated Trading, and Distributed Constraint Satisfaction Problem in part 2.2. In part 2.3, I will describe briefly the example of transportation scheduling application that has been developed.


2.1. AGENT & MULTI AGENT

Agent

The term of agent is widely used in Artificial Intelligence. What is an agent? The Workers involved in agent research have offered a variety of definition.
Russel and Norvig define an agent as :
        An agent is anything that can be viewed as perceiving its environment         through sensors and acting upon that environment through effector [18].

Pattie Maes describe an agents as :
        Autonomous agents are computational systems that inhabit some complex         dynamic environment, sense and act autonomously in this environment, and         by doing so realize a set of goals or tasks for which they are design [14].

Instead of Russel & Norvig and Maes definitions, there are many other definition vary from the simple to the long and severe definition. Hence, we can identify the term of agent as a component of software and/or hardware, which is capable of acting exactingly in order to accomplish tasks on behalf of its user. This term can cover a variation of other specific agent type [15].
There are two general usages of the term agent, which are weak and strong [22].

A weak term of agents
The agent is hardware or software based computer systems that have the following characteristic:
          · Autonomy: agents interact without interference of human or other             agent, and have some kind of control over their action and internal             state.
          · Social ability: agents interact with other artificial agents or humans in             order to complete their own problem solving and to help others with their             activities. The agents can communicate with other agents or human via             some kind of agent-communication language. [11]
          · Reactivity: agents perceive their environment and respond in a timely             fashion to changes that occur in it. The environment here can be a             physical world, a user via a graphical user interface, a collection of other             agents, the INTERNET, or perhaps all of these combined.
          · Pro-activeness: agents do not simply act in response to their             environment; they are able to exhibit opportunistic, goal-directed             behaviour and take the initiative where appropriate.
In some condition, agents can have others characteristics which are
          · Adaptability: the ability of an agent to modify its behaviour over time in             response to changing environmental conditions or an increase in             knowledge about its problem solving role.
          · Mobility: the ability of an agent to change its physical location to             enhance its problem solving [21].
          · Veracity: the assumption that an agent will not knowingly communicate             false information [5 , pp. 159-164].
          · Rationally: the assumption that an agent will act in order to achieve its             goals and will not act in such a way as to prevent its goals being             achieved without good cause [5, pp. 49-54].
          · Benevolence: the assumption that agents do not have conflicting goals,             and that every agent will therefore always try to do what is asked for it.             [17 pp. 91].


A strong term of agents
As state above, the agent is a computer system that has property of autonomy, social ability, reactivity, and pro-activeness. In stronger term, this computer system is either conceptualised or implemented using concepts that are more usually applied to humans such as knowledge, belief, intention, obligation, and emotional [16].


Multi Agent

The various agent technologies existing today can be classified as being either single-agent or multi-agent system. In Single Agent systems, an agent may interact with the user or with local or remote system resource. In contrast, A Multi Agent System (MAS) is a system is designed and implemented as several interacting agents. Hence, MAS can communicate either with human and system resource or with other agent. Consistent with the degree of cooperation exhibited by the individual agent, multi agent system (MAS) is classified into 2 types:
     · Competitive agents: Each agent goal is to optimise its own interest, while        attempting to reach agreement with other agents. Example of the system        that using competitive agent are :
            o BargainFinder [12]
              The user give a specific product that she/he is looking for. The system               quesries a fixed set of web merchant sites for its price and present the               user with a ranked set of price quotes.
            o Jango
              It is an advanced version of BargainFinder which makes product price               requests originate from customer web-sites.
            o Kasbah [4]
              Kasbah is a ads service on the WWW that incorporates interface               agents. A web site represent a 'market-place' where Kasbah agents,               acting on behalf of their owners, can filter through the ads and find               those that their users might be interested in. The agent negotiates to               buy and sell items.
            o MAGMA [7]
              Magma introduces an open marketplace involving agents that               buying/selling physical goods, investments and forming               competitive/cooperative alliances. Magma has "offer board" that               contains offers from buyer and sellers. Seller agent posts the highest               price of offered product to the offer board through its Personal               Assistants (PA). The buyers inform the PA to retrieve a number of best               offers of a specific product that they interested in. The buyer PA will               display a set of offers. The buyer will select which offer to follow up.               Finally, the buyer PA will then post an accept offer to the relevant               seller agent.

      · Cooperative agents: Agents share their knowledge and beliefs to try to         maximise the benefit of the community as a whole. Example of the system         that using competitive agent are:
            o Air Traffic Control
              Chu & Carrol [6,13] have developed a cooperative negotiation model               among the agents (pilot, air traffic control). They cooperate to develop               the best plan for flight and handle the entire situation, which affect the               flight.

We can classify multi-agent transportation scheduling as cooperative multi agent since the agents cooperate to optimise distribution and execution task in time and cost constraint.


2.2 . CONCEPTS OF NEGOTIATION AMONG AGENTS

Contract Net Protocol [19]
(see figure 1)

The contract net protocol is a negotiation protocol proposed by Smith and David on 1980, which facilitates distributing subtask among various agents. Each agent in the system takes on one of the role in the execution of task, which are manager role or contractor role. A manager is responsible for monitoring the execution of a task and processing the results of its execution. On the other hand, a contractor is responsible for the actual execution of the task. The manager broadcast a message of task to be executed to all of contractors. Each message in the CNP has a set of slots for task-specific information such as task eligibility specification, task abstraction, bid specification, expiration time.

     · Task eligibility specification is a list of criteria that the contractor must meet        to be eligible to submit a bid. The purpose of this slot is reducing message        traffic by pruning contractors whose bids would clearly unacceptance.
     · Task abstraction is a brief description of the task to be executed. It enables        the contractor to rank the task relative to other announced task. The task        abstraction is used rather than a full description of a task in order to reduce        the length of the message.
     · Bid Specification is a description of the expected form of a bid. It prevent        the contractor submit the bid with irrelevant description to the task.        Therefore, it will simplify the task of the manager in evaluating bids.
     · Expiration time is a deadline for receiving bids.

The manager waits for reply from the contractor for some length of time, and then awards the contract to the best offers from the contractor according to its selection criteria.

There are some modified versions of this Classic Contract Net Protocol. Some researchers modify this protocol to meet some special requirement of their application such as B-Contract Net by Scalabrin on 1996 and Extended Contract Net Protocol (ECNP) [6,7,8].

For example, the classic Contract Net Protocol will hit upon problems on the situation where the task exceeds the capacity of every single VA. Because of this reason, Fischer proposed Extended Contract Net Protocol for transportation scheduling. We will briefly discuss about ECNP in the subsection below.

               capacity of each VA < amount of order to transport

The idea to solve this problem is split an order into parts and assign each parts of the task to different VA. Hence, the main different of ECNP to the CNP is that the contractor agents are allowed to bid for only parts of a task. ECNP is available as standard protocol in MARS. MARS system is model of multi agent scenario for shipping company [7]. In ECNP, VA (contractor) may receive four kinds of speech acts: temporal grant, temporal reject, definitive grant, and definitive reject from CA (manager) instead of only grant and reject.

Firstly, the CA announces an order to its VAs and wait for some length of time, and then sent a temporal grant to contractor that offers the best bid according to some specific selection criteria. All others contractor will receive a temporal reject. If the best bid does not cover the whole amount of an order, the remaining part of the order is re-announced by the CA. This procedure is repeated until there is a set of bids that covers the total amount of the original order. CA sent this set of bids to the customer. The CA send the definitive grant to all VAs that got temporal grants before, based on customer approval. VA store a copy of its local situation when it receive a temporal grant since it must be able to restore this situation in case it receive a definitive reject. On the other hand, when VA is sent a definitive grant for an order, it removes the copy created above and switches to the new plan.

The original idea of simulating trading heuristic is for improving a heuristic of solving vehicle routing problems with additional side constraints. The basic problem of vehicle routing problems is given as follows: a set of n customers with demands di has to be served from a depot using t trucks of capacity Q. The objective is to minimize the total distance covered by the trucks or some other measure such as cost, time, etc. The current exist heuristic is only used for local improvement within one of the available tours. Simulated Trading introduce a global improvement, which is changing customers between tours. Consider the following example of below:
      - Truck 1 would like to give up order A since it will give him an extra hours of         driving time
      - Truck 2 can take order A since position of order A is on the way of his tour.         If truck 2 takes order A, the problem is he will need additional time for order         B.
      - Truck 3 is qualified to take order B but if he would insert order B in his tour          then he would violate the time window of order C.
      - Truck 4 will have an extra hours of driving time if he would take order C.          But if another truck would be able to take order D then it would be possible          for him to take order C.
      - Truck 1 is able to take order C by 15 minutes cost.
      - In Conclusion, If truck would take order D then the global improvement for         the whole tours is 40 minutes from the original tours plans.

We can draw above example by using a graph which is called trading graph (figure 1). The nodes represent either an insertion (buy) of a customer into a tour or a deletion (sell). The edge represents the possibility of exchange an order, which is weighted with the value of the achievement or the value of lost of the corresponding action. The term value of matching is used to describe a sum of the weight of the matching edge. For example : The value of matching {(A,60),(A,10)} is 50.

Repeat
          Sell-And-Buy phase
          Trading-Matching-Search phase
          If Trading -Matching M is found then
          Update tour plan T according to M
Until time limit is reached

The trading graph will construct level by level until a given maximum level is reached. In each level, the tour may select 3 possibilities decision (figure 2):

  i. Sell decision: An order will be removed from the tour, if it causes a      large cost. An order will be inserted into a selling list.
 ii. Buy decision: An order can be taken from a selling list then is inserted     into tour plan, if the order achieves a large gain.
iii. Waiting decision: waiting for updated selling list.

Figure 5

Trading- Matching-Search phase

Trading Matching is a trading graph with a set of edge M that has the following property
     i . M is a matching
     ii. If a node v in decision level l of tour T is matched then all nodes in lower          decision levels of T have to be matched too.
     iii. The weight of M is positive

The purpose of Trading-Matching is to find a complex customer interchange leading to an improved feasible tour plan. A feasible tour plan is improved if the matching value is positive.

We can conclude that the simulated trading is a heuristic to improve existing solution, not to find a solution from the beginning. This simulated trading mechanism is modelled in transportation scheduling as an auction procedure for optimisation of task distribution. This mechanism is applied to the cooperation between CA. It allows CA exchange the order that optimises the global solution.

Constraint

A constraint is a logical relation among several unknowns (or variable), each taking a value in a given domain. A constraint thus restrict the possible values that variables can take, it represents some partial information about the variables of interest. Example of constraints: A+B = C , X>Y

Constraint Satisfaction Problem (CSP)
The definition of CSP is
3 tuples : <X,D,C>
     - X is a finite set of variables
     - D is a set of domains for each variable in X
     - C is a set of constraints
A goal of CSP is to find the value assignment of variables that satisfy all constraint.

Distributed Constraint Satisfaction Problem (DCSP)

The definition of DSCP is a CSP in which the variables and constraints are distributed among the agents. Hence, there are more than one agent involve in the problem. There are many algorithms for solving problem in Distributed Constraint Satisfaction Problem. The algorithm is classified into 2, which are algorithm for single local variable and algorithm for multiple local variables. Algorithm for single local variable is applied for problem where agent only has one variable. In the other hand, Algorithm for multiple local variables is applied for problem where agent has more than 1 variable. Below is the list of some algorithm for DSCP.

MAS - MARS [6,7,8,9]
MAS - MARS system is a research prototype for transportation scheduling. There are two basic agents in MARS corresponding to the physical entities in the domain : shipping companies and trucks. Three basic cooperation settings among agents are :
     1. Vertical Cooperation
         Cooperation between shipping company and its trucks (ECNP).
     2. Horizontal Cooperation
         Cooperation between groups of autonomous shipping companies (Simulated          Trading).
     3. Enhanced Cooperation
         This is an extension of vertical cooperation. Trucks agent is assigned the          ability to reflect on their plans. If it realizes that it has a poor plan, it can          cancel the contract made with its company for a specific order.

TELETRUCK [2,3 ]

      Teletruck is an extended re-implementation of the MAS-MARS system. The agents of MAS-MARS system represent homogeneous trucks. On the contrary, Teletruck is using heterogeneous agents (drivers, trucks, trailers, containers). Teletruck is an interactive system for computer-supported dispatch in the haulage sector. Teletruck takes care of routine tasks and proposed dispatch solution, thus enhancing the productivity of the dispatcher. The feature of teletruck is allowance of online re-scheduling. The agent society of Teletruck is implemented as a holonic agent system. A Holonic agent is composed of the sub-agents working together in order to pursue a common goal. The user or the other members of the agent society can interact with a holon as if it were a single agent.

The definition of multi agent transportation scheduling is a system with a group of agents that cooperate to optimise the distribution and execution of orders according to cost and time measure.

3.1 Multi Agent Transportation Scheduling Using Contract Net Protocol and Internal Market Place

      Two basic objects that will be agentified: company and vehicle that will execute the task. The company agent (CA) allocates the order to the vehicle agent (VA) and trying to satisfy the constraints provided by the customer including time and to approach a minimal cost. This relationship between CA and VA can be solved by Contract Net Protocol concept but the solution is not optimized. Consider, the situation where the constraints dynamically change such as traffic situation, arrival of new order, defective truck. In this case, it is possible that the current solution is not an optimal solution any longer. Hence, we need to find the way to re-arrange the solution. The good news is we can use the idea of exchange task in Simulated Trading to escape from this problem.
     The main idea is while CA does not have any new order, VAs can exchange orders. On one hand, VA can give up (selling) the order that has been awarded to him for some reason, for example If he take order A, he can offer cheaper cost. But, he has to give up some current order that he has in his tour plan. He choose to take order A since the value of taking order A and give up some current order is better than the value of give up order A and keep the current plan. On the other hand, VAs can take an order (buying) since this order give him better gain.
     The given up order will be insert into a list of selling order and VA can buy an order in this list. We can imagine this situation as a buying and selling process in marketplace. Basically, VA tries to sell the order by release it into the marketplace. If there is another VA that interested on buying this order, they will negotiate. We can use Internal Marketplace term for this relationship.
     In conclusion, we can specify two way of interaction among agents in Multi Agent Transportation Scheduling:
          · Vertical interaction between CA and each VA.
          · Horizontal interaction among VAs or among CA.
We use concept of CNP for vertical interaction between CA and each VA. In Order to optimise the solution of vertical interaction, we propose Internal Marketplace mechanism, which is based on Simulating Trading heuristic for communication among VAs in one company.

3.2 Applying Constraint Satisfaction Problem into Multi Agent Transportation Scheduling

     In this section, I will present the idea of applying Constraint Satisfaction Problem into Multi Agent Transportation Scheduling. As mentioned above, The definition of transportation scheduling is a system that deals with the allocation of vehicle (in my case, it is a truck) to perform a collection of order. The goals of this transportation scheduling are minimize transport cost and transport time. We are introduced to the concept of multi agents, which can optimise the distribution and execution of tasks (order). The multi agents can handle the situation where the constraints change, such as the arrival of new order or the changing traffic situation.
     The Transportation scheduling can be formally defined as follow. Given a set O of o order, a set T of t truck. For every o order, there is 2 tasks that have to be done which are pick up p and delivery d. There are some constraints that has to be considered:
     o A precedence constraint where pickup task has to be done before delivery task.
     o Due time constraint where an actual delivery time is earlier than or equal to         delivery time that request by a customer.
     o Feasibility of order allocations into existing plan constraint. For example:
        In Figure 1 is describing an existing plan of particular truck. O3 (pickup and         delivery task) is a new order that has to be fit in this existing plan. The         constraints are:
          - Delivery task of O3 can be inserted after or before one of existing task             as long as time enables.
        The more detail description about this constraint will be discussed in the         next section.

Figure 6 : Existing Plan

     Each truck agent can locally solve the problem with inserting an order into its journey plan. Truck agent has to find the best journey plan, which has the cheapest cost. Hence, the output from this assignment is the best cost that this truck can offer. Consider, if there is other truck agent that can offer a cheaper cost. Therefore, we have to find the optimal solution where the order can be done by the cheapest cost. It is very easy to find a solution for this problem but the solution is not always an optimal solution. In another case, the situation is dynamically changed such as incoming new order. In order to find an optimal solution, we always have to revise the solution. There are some CSP algorithms that can solve this problem. In this paper, I will not discuss further about the algorithm. Beside I will describe the formalisation of this problem into CSP.

Formalisation of problem into CSP
     We come to the idea of hierarchical composition of CSP where there is a global CSP and a child CSP. A Global CSP handles the situation where one of the trucks is assigned into particular order with cost consideration. A child CSP only handles constraints inside a truck, which is an allocation a new task into the existing plan. Once the truck finds an allocation place for this new task, the cost of this order will be calculated. This cost will be considered in the global CSP.

CSP for Order Allocation in the existing plan

Constants:
dt is due time of delivery that proposed by customer
pt is due time of pickup. We assume that pickup time cannot be changed.

Variables:
pi : pickup time
di : delivery time
where i is a natural number describe an order number.

Domains:
Dom (di): time between pt and dt

Constraints:
o Precedence constraint
   pi + S [pli,dlj] £ di (pi before di)

  S [a,b] is described a length of time that has to be covered between location a   and location b.

  di + S[dli,dlj] £ dj Ú dj + S[dlj,dli] £ di i ¹ j
  Delivery task i can be put before delivery task j if delivery time of task i plus   duration from delivery location i to delivery location j is less than or equal to   delivery time of task j.
                                                         OR
  Delivery task i can be put after delivery task j if delivery time of task j plus   duration from delivery location j to delivery location i is less than or equal to   delivery time of task i.

  pi + S[pli,dlj] £ dj Ú dj + S[dlj,pli] £ pi i ¹ j
  Pickup task i can be put before delivery task j if pickup time of task i plus   duration from pickup location i to delivery location j is less than or equal to   delivery time of task j.
                                                         OR
  Pickup task i can be put after delivery task j if delivery time of task j plus   duration from delivery location j to pickup location i is less than or equal to   pickup time of task i.

  pi £ pj Þ pi + S[pli,plj] £ pj
  Pickup task i can be put before pickup task j if pickup time of task I plus   duration from pickup location i to pickup location j is less than or equal to pickup   time of task  j.

o Due time constraint
  di £ dt
  Delivery time of task I has to be less than or equal to delivery time proposed by   customer.

There is an object function for this case, which is a cost for this order. Once the new order is attached to the existing plan, the cost for this order will be calculated.

CSP for assigning a truck to the order

Variable
Oi: Order
Ci: Cost for this Order

Domain
Dom (Oi): a list of truck {T1, T2, T3… Tn}
Dom (Ci): {CT1, CT2, CT3… CTn}
Where CTn is a cost that proposed by truck Tn

Constraint
CTj < CTk < CT1 Þ Oi = Tj
The truck that can offer the cheapest cost will be assigned to the order variable.