TASK DEFINITION: In this task, you are given a part of an article. Your task is to generate headline (title) for this text. Preferred headlines are under fifteen words.
PROBLEM: There are many complex combinatorial problems which involve searching for an undirected graph satisfying given constraints. Such problems are often highly challenging because of the large number of isomorphic representations of their solutions. This paper introduces effective and compact, complete symmetry breaking constraints for small graph search. Enumerating with these symmetry breaks generates all and only non-isomorphic solutions. For small search problems, with up to 10 vertices, we compute instance independent symmetry breaking constraints. For small search problems with a larger number of vertices we demonstrate the computation of instance dependent constraints which are complete. We illustrate the application of complete symmetry breaking constraints to extend two known sequences from the OEIS related to graph enumeration.

SOLUTION: Breaking Symmetries in Graph Search with Canonizing Sets

PROBLEM: The folksonomy is the result of free personal information or assignment of tags to an object (determined by the URI) in order to find them. The practice of tagging is done in a collective environment. Folksonomies are self constructed, based on co-occurrence of definitions, rather than a hierarchical structure of the data. The downside of this was that a few sites and applications are able to successfully exploit the sharing of bookmarks. The need for tools that are able to resolve the ambiguity of the definitions is becoming urgent as the need of simple instruments for their visualization, editing and exploitation in web applications still hinders their diffusion and wide adoption. An intelligent interactive interface design for folksonomies should consider the contextual design and inquiry based on a concurrent interaction for a perceptual user interfaces. To represent folksonomies a new concept structure called "Folksodriven" is used in this paper. While it is presented the Folksodriven Structure Network (FSN) to resolve the ambiguity of definitions of folksonomy tags suggestions for the user. On this base a Human-Computer Interactive (HCI) systems is developed for the visualization, navigation, updating and maintenance of folksonomies Knowledge Bases – the FSN – through the web. System functionalities as well as its internal architecture will be introduced.

SOLUTION: Intelligent Interface Architectures for Folksonomy Driven Structure Network

PROBLEM: Multi-agent path planning is a challenging problem with numerous real-life applications. Running a centralized search such as A* in the combined state space of all units is complete and cost-optimal, but scales poorly, as the state space size is exponential in the number of mobile units. Traditional decentralized approaches, such as FAR and WHCA*, are faster and more scalable, being based on problem decomposition. However, such methods are incomplete and provide no guarantees with respect to the running time or the solution quality. They are not necessarily able to tell in a reasonable time whether they would succeed in finding a solution to a given instance. We introduce MAPP, a tractable algorithm for multi-agent path planning on undirected graphs. We present a basic version and several extensions. They have low-polynomial worst-case upper bounds for the running time, the memory requirements, and the length of solutions. Even though all algorithmic versions are incomplete in the general case, each provides formal guarantees on problems it can solve. For each version, we discuss the algorithm’s completeness with respect to clearly defined subclasses of instances. Experiments were run on realistic game grid maps. MAPP solved 99.86% of all mobile units, which is 18–22% better than the percentage of FAR and WHCA*. MAPP marked 98.82% of all units as provably solvable during the first stage of plan computation. Parts of MAPP’s computation can be re-used across instances on the same map. Speed-wise, MAPP is competitive or significantly faster than WHCA*, depending on whether MAPP performs all computations from scratch. When data that MAPP can re-use are preprocessed offline and readily available, MAPP is slower than the very fast FAR algorithm by a factor of 2.18 on average. MAPP’s solutions are on average 20% longer than FAR’s solutions and 7–31% longer than WHCA*’s solutions.

SOLUTION:
MAPP: a Scalable Multi-Agent Path Planning Algorithm with Tractability and Completeness Guarantees