A vibrant theoretical research area are efficient exact parameterized algorithms. Very recent solving competitions such as the PACE challenge show that there is also increasing practical interest in the parameterized algorithms community. An important research question is whether dedicated parameterized exact algorithms exhibit certain practical relevance and one can even beat well-established problem solvers. We consider the logic-based declarative modeling language and problem solving framework Answer Set Programming (ASP). State-of-the-art ASP solvers rely considerably on Sat-based algorithms. An ASP solver (DynASP2), which is based on a classical dynamic programming on tree decompositions, has been published very recently. Unfortunately, DynASP2 can outperform modern ASP solvers on programs of small treewidth only if the question of interest is to count the number of solutions. In this paper, we describe underlying concepts of our new implementation (DynASP2.5) that shows competitive behavior to state-of-the-art ASP solvers even for finding just one solution when solving problems as the Steiner tree problem that have been modeled in ASP on graphs with low treewidth. Our implementation is based on a novel approach that we call multi-pass dynamic programming (M-DPSINC).
Jun 29 2017 cs.AI
Learning relations based on evidence from knowledge bases relies on processing the available relation instances. Many relations, however, have clear domain and range, which we hypothesize could help learn a better, more generalizing, model. We include such information in the RESCAL model in the form of a regularization factor added to the loss function that takes into account the types (categories) of the entities that appear as arguments to relations in the knowledge base. We note increased performance compared to the baseline model in terms of mean reciprocal rank and hits@N, N = 1, 3, 10. Furthermore, we discover scenarios that significantly impact the effectiveness of the type regularizer.
Class-agnostic object tracking is particularly difficult in cluttered environments as target specific discriminative models cannot be learned a priori. Inspired by how the human visual cortex employs spatial attention and separate "where" and "what" processing pathways to actively suppress irrelevant visual features, this work develops a hierarchical attentive recurrent model for single object tracking in videos. The first layer of attention discards the majority of background by selecting a region containing the object of interest, while the subsequent layers tune in on visual features particular to the tracked object. This framework is fully differentiable and can be trained in a purely data driven fashion by gradient methods. To improve training convergence, we augment the loss function with terms for a number of auxiliary tasks relevant for tracking. Evaluation of the proposed model is performed on two datasets of increasing difficulty: pedestrian tracking on the KTH activity recognition dataset and the KITTI object tracking dataset.
In sequence prediction task, there mainly exist two types of learning algorithms. One genre based on maximum likelihood estimation (MLE) supervises the training in every time step via a surrogate loss function but leads to train-test discrepancy and hard-to-train problem. The other genre based on Reinforcement Learning gives the model freedom to generate samples and guides the training by feeding back task-level reward but suffers from high variance and instability problem. In general, these two frameworks both have their own trade-offs and complement each other. In this paper, we introduce a hybrid-coach framework to combine these two existing algorithms so that the supervision from MLE can stabilize RL training while RL can incorporate task-level loss into MLE training. To augment more easy-to-learn samples for MLE training and denser reward for RL training, the coach is encouraged to be close to both the data and model distribution. During training, the coach acts as a proxy target and pulls the model distribution to the data distribution, as the model makes progress it correspondingly upgrades itself to become harsher and finally anneal to the ultimate target distribution. With the coordination of the coach system, our hybrid-coach framework can efficiently resolve RL's reward sparsity problem and MLE's data sparsity problem. We apply our algorithm on two Machine Translation Task and show significant improvements over the state-of-art systems.
A descriptive approach for automatic generation of visual blends is presented. The implemented system, the Blender, is composed of two components: the Mapper and the Visual Blender. The approach uses structured visual representations along with sets of visual relations which describe how the elements (in which the visual representation can be decomposed) relate among each other. Our system is a hybrid blender, as the blending process starts at the Mapper (conceptual level) and ends at the Visual Blender (visual representation level). The experimental results show that the Blender is able to create analogies from input mental spaces and produce well-composed blends, which follow the rules imposed by its base-analogy and its relations. The resulting blends are visually interesting and some can be considered as unexpected.
In this paper, we study Reiter's propositional default logic when the treewidth of a certain graph representation (semi-incidence graph) of the input theory is bounded. We establish a dynamic programming algorithm on tree decompositions that decides whether a theory has a consistent stable extension or can even be used to enumerate all generating defaults that lead to stable extensions. We show that, for input theories whose semi-incidence graph has bounded treewidth, our algorithm decides whether a theory has a stable extension in linear time and enumerates all characteristic generating defaults with linear delay.
This paper presents a collection of path planning algorithms for real-time movement of multiple robots across a Robotic Mobile Fulfillment System (RMFS). Robots are assigned to move storage units to pickers at working stations instead of requiring pickers to go to the storage area. Path planning algorithms aim to find paths for the robots to fulfill the requests without collisions or deadlocks. The state-of-the-art path planning algorithms, including WHCA*, FAR, BCP, OD&ID and CBS, were adapted to suit path planning in RMFS and integrated within a simulation tool to guide the robots from their starting points to their destinations during the storage and retrieval processes. Ten different layouts with a variety of numbers of robots, floors, pods, stations and the sizes of storage areas were considered in the simulation study. Performance metrics of throughput, path length and search time were monitored. Simulation results demonstrate the best algorithm based on each performance metric.
Retinal vessel segmentation is an indispensable step for automatic detection of retinal diseases with fundoscopic images. Though many approaches have been proposed, existing methods tend to miss fine vessels or allow false positives at terminal branches. Let alone under-segmentation, over-segmentation is also problematic when quantitative studies need to measure the precise width of vessels. In this paper, we present a method that generates the precise map of retinal vessels using generative adversarial training. Our methods achieve dice coefficient of 0.829 on DRIVE dataset and 0.834 on STARE dataset which is the state-of-the-art performance on both datasets.
Additively separable hedonic games and fractional hedonic games have received considerable attention. They are coalition forming games of selfish agents based on their mutual preferences. Most of the work in the literature characterizes the existence and structure of stable outcomes (i.e., partitions in coalitions), assuming that preferences are given. However, there is little discussion on this assumption. In fact, agents receive different utilities if they belong to different partitions, and thus it is natural for them to declare their preferences strategically in order to maximize their benefit. In this paper we consider strategyproof mechanisms for additively separable hedonic games and fractional hedonic games, that is, partitioning methods without payments such that utility maximizing agents have no incentive to lie about their true preferences. We focus on social welfare maximization and provide several lower and upper bounds on the performance achievable by strategyproof mechanisms for general and specific additive functions. In most of the cases we provide tight or asymptotically tight results. All our mechanisms are simple and can be computed in polynomial time. Moreover, all the lower bounds are unconditional, that is, they do not rely on any computational or complexity assumptions.
This paper investigates how high school students approach computing through an introductory computer science course situated in the Logic Programming (LP) paradigm. This study shows how novice students operate within the LP paradigm while engaging in foundational computing concepts and skills, and presents a case for LP as a viable paradigm choice for introductory CS courses.