• heuristic search methods
• task assignment

This work consider the Task Assignments Problem for fleets of Automated Guided Vehicles (AVGs), while taking into account the subsequent path planning problem and the coordination problem. The estimated costs are interrelated and the overall performance of the team need not be a standard sum of cost model, enabling straightforward treatment of the additional costs incurred by precedence constraints due to coordination problem. Additional penalization costs are incurred by overlap between paths. This work shows that the general problem is NP-hard, and investigate specialized subinstances with particular cost structures. Sequential application of task assignment and path planning often gives rise to pathological situations, such as deadlocks, in which AGVs block each other, thus preventing tasks completion. The MRTA problem can take widely differences depending on the characteristics of the robots in the fleet and of the application context. Goals can be shared or individual. Robots may be aware of each other’s tasks or not; tasks may or may not require interaction between robots; The fleet can be a centralized or distributed system; in this study, a centralized system is considered. The aim of this report is to expose the work tread for final master thesis which was held at ̈Orebro University. A modified systematic algorithm is proposed, that finds a solution in a reasonable time both on small instances (if interference is considered) and on big instances (if interference is not considered). Aiming at larger problems, some changes are introduced that allow to find an optimal assignment quickly even for problems of considerable size. Simulations are performed on maps of real industrial environments, to compare the proposed method with traditional task assignment algorithms.