An Optimization-Based Distributed Planning Algorithm: A Blackboard-Based Collaborative Framework

Motivated by the need for multiple agents to collaborate in order to solve a distributed resource allocation planning problem, this paper develops a distributed framework that combines each agent´s information, expertise, responsibility, and asset ownership with the goal of optimizing a given mission objective. A mission is a collection of interdependent tasks to be executed in a directed/sequential sequence. Each task is modeled by a vector of resource requirements, a processing time, and a start time (release time). Each agent has a subset of tasks for which it is responsible, and owns a set of heterogeneous assets, where each asset is modeled by a vector of resource capabilities that it provides. Multiple agents must collaboratively allocate assets to tasks to maximize an expected mission performance, defined by how well all of the tasks´ requirements are satisfied by the allocated asset capabilities. Our agent-based distributed planning framework uses a blackboard communication paradigm to exchange information among agents. The framework contains an intra-agent and an interagent module that support individual and cooperative planning, respectively. The intra-agent module employs an optimization-based m-best asset allocation algorithm to match an agent´s own tasks with its locally owned assets. The interagent module coordinates the exchange of information and asset allocations among agents to improve the local plans using an asset pricing mechanism, and includes a means for characterizing an agent´s cooperative behavior.