  We address a problem of area protection in graph-based scenarios with
multiple agents. The problem consists of two adversarial teams of agents that
move in an undirected graph shared by both teams. Agents are placed in vertices
of the graph; at most one agent can occupy a vertex; and they can move into
adjacent vertices in a conflict free way. Teams have asymmetric goals: the aim
of one team - attackers - is to invade into given area while the aim of the
opponent team - defenders - is to protect the area from being entered by
attackers by occupying selected vertices. We study strategies for allocating
vertices to be occupied by the team of defenders to block attacking agents. We
show that the decision version of the problem of area protection is PSPACE-hard
under the assumption that agents can allocate their target vertices multiple
times. Further we develop various on-line vertex-allocation strategies for the
defender team in a simplified variant of the problem with single stage vertex
allocation and evaluated their performance in multiple benchmarks. The success
of a strategy is heavily dependent on the type of the instance, and so one of
the contributions of this work is that we identify suitable vertex-allocation
strategies for diverse instance types. In particular, we introduce a
simulation-based method that identifies and tries to capture bottlenecks in the
graph, that are frequently used by the attackers. Our experimental evaluation
suggests that this method often allows a successful defense even in instances
where the attackers significantly outnumber the defenders.
