In this work, we focus on problems modeled as a set of tasks to be scheduled and accomplished by mobile autonomous devices that communicate via a mobile ad hoc network. In such situations, the communication cost, computational efforts and environment uncertainty are key challenges.
It is intuitive to consider that keeping information about tasks globally known by devices can provide better schedules. However, there are some contexts - such as those where tasks require startup based on location - where information restricted to coalitions of devices can still produce satisfactory scheduling. The existing heuristics, however, do not consider this approach.
In this paper, we propose a multiagent system that coordinates the dynamic formation of overlapping coalitions and the scheduling of tasks within them. Heuristics for calculating the size of coalitions, as well as for scheduling tasks are proposed based on a Markov decision process. The system is applied to solve the problem of area coverage in a simulated environment and the results show that good schedules are obtained with lower cost of communication and computation compared with the solution based on globally known information.