We consider a number of min-max coverage problems. In each problem, the input is an unweighted graph G and an integer k, and possibly some additional information, such as a root vertex r. In the Min-Max Path Cover problem, the task is to cover all vertices of the graph by k walks, minimizing the length of the longest walk. The variant of Min-Max Path Cover in which all walks start and end at the same prescribed root vertex r is called the k-Traveling Salesmen Problem. In the Min-Max Tree Cover problem, the task is to cover all vertices of the graph by k trees, minimizing the size (number of edges) of the largest tree. In the rooted version, Min-Max k-Rooted Tree Cover, the input also contains k roots r1, . . ., rk, and the ith tree must contain the root ri. These four problems are all known to be APX-hard and to admit a constant-factor approximation. In this paper, we initiate the systematic study of these problems on trees and, more generally, on graphs of constant treewidth. As opposed to most graph problems, all four of the above coverage problems remain NP-hard even when G is a tree. We obtain an nO(k)-time exact algorithm for all four problems on graphs of bounded treewidth. Our main contribution is a quasi-polynomial-time approximation scheme (QPTAS) for the k-Traveling Salesmen Problem, Min-Max Path Cover, and Min-Max Tree Cover on graphs of bounded treewidth.

This paper discusses the multi-robot, multi-depot Map Visitation Problem, a multi-robot inspection problem in which a team of robots originating from multiple home base depots must visit a collection of previously identified critical locations in a two-dimensional navigation environment. In its precise focus on location inspection, it is related yet complementary to other inspection or surveillance problems such as boundary coverage or patrol. In the paper, we analyze graph representations and an agent model appropriate for the Map Visitation Problem, and we present complexity results for a variety of categories of map structures, including lines, rings, trees, and general graphs. In addition to complexity results, we present an algorithm for the Map Visitation Problem on trees that is optimal for single-robot problems and a second algorithm that is provably within a factor of two of optimal for two robots inspecting arbitrary graphs.

Animated characters may exhibit several kinds of dynamic intelligence when performing low-level navigation (i.e., navigation on a local perceptual scale): they decide among different modes of behavior selectively discriminate entities in the world around them, perform obstacle avoidance, etc. In this paper we present a hybrid dynamical system model of low-level navigation that accounts for the above-mentioned kinds of intelligence. In so doing, the model illustrates general ideas about how a hybrid systems perspective can influence and simplify such reactive/behavioral modeling for multi-agent systems. In addition, we directly employed our formal hybrid system model to generate animations that illustrate our navigation strategies. Overall, our results suggest that hierarchical hybrid systems may provide a natural framework for modeling elements of intelligent animated actors.

We formalize the notion of underspecification as a means of avoiding problems with partial functions in modal logic S5 and some semantically related logics. For these logics, underspecification preserves validity, so incorporating it into their semantics leaves their classes of valid formulae unchanged.