MenciĂłn Internacional en el tĂ­tulo de doctorMulti-agent planning deals with the task of generating a plan for/by
a set of agents that jointly solve a planning problem. One of the biggest
challenges is how to handle interactions arising from agents’ actions. There
exist some other relevant challenges such as planner’s scalability when agents, goals
or resources increase; or improving the makespan of the resulting plan. In this Thesis,
we present Plan Merging by Reuse, PMR, a multi-agent planner that automatically
adjusts its behaviour to the level of interaction. Given a multi-agent planning task,
PMR decides which agents will try to achieve each goal. The chosen agents solve their
individual planning tasks. The resulting plans are merged and PMR checks the plan’s
validity. Given the potential interactions, merged plans are not always valid. When that
happens, PMR performs planning by reuse to generate a valid plan. In order to deal with
the problem of agents’ coordination, another contribution presented on this Thesis is
RRPT, a stochastic plan-reuse planner. RRPT is able to adjust itself to two different cases:
when the input invalid plan is very similar to the final valid solution (classic plan reuse
scenario) and also when the input plan is completely different from the final solution.
RRPT combines plan reuse and standard search. It will decide stochastically on each
iteration which technique to run. Thus, RRPT adapts itself to a wide variety of scenarios.
We have performed extensive sets of experiments in order to analyze when to use the
different PMR variants, as well as which tasks are more appropriate to be solved by PMR.
Our contributions obtain solutions to multi-agent planning tasks where PMR and RRPT
can successfully adapt their behavior to the particularities of the problems.Programa de Doctorado en Ciencia y Tecnología Informática por la Universidad Carlos III de MadridPresidente: Eva Onaindía de la Rivaherrera.- Secretario: Dirk Sascha Ossowski.- Vocal: Michael Wayne Barley