Cooperative Distributed Problem Solving through ad hoc agent coalitions

Cooperative Distributed Problem Solving refers to a loosely coupled network of problem solvers working together to solve problems that may be beyond the capabilities of individual agents. Individual nodes may not have sufficient expertise, resources or information to solve the entire problem but every node is capable of solving some part. A group of autonomous agents in a Multi-agent System often work in a cooperative manner and form coalitions to obtain higher payoff than they can get individually. The coalition formation framework of Multi-agent Systems can be extended to a Distributed Problem Solving formulation where agents strive to achieve higher group benefits. This paper tries to demonstrate how a group of autonomous agents can solve a package delivery domain problem with reasonably good parameters in a purely distributed manner. Unlike traditional distributed problem solving experiments, here the agents are distributed across the problem domain and all control decisions are decentralized with no agent acting as a central dispatcher/ scheduler.