A Maximal Tractable Class of Soft Constraints

By Dieter Fox, Wolfram Burgard, Sebastian Thrun. International Joint Conference on Artificial Intelligence, 2003

802 citations recorded by the source corpus.

Many researchers in artificial intelligence are beginning to explore the use of soft constraints to express a set of (possibly conflicting) problem requirements. A soft constraint is a function defined on a collection of variables which associates some measure of desirability with each possible combination of values for those variables. However, the crucial question of the computational complexity of finding the optimal solution to a collection of soft constraints has so far received very little attention. In this paper we identify a class of soft binary constraints for which the problem of finding the optimal solution is tractable. In other words, we show that for any given set of such constraints, there exists a polynomial time algorithm to determine the assignment having the best overall combined measure of desirability. This tractable class includes many commonly-occurring soft constraints, such as 'as near as possible' or 'as soon as possible after', as well as crisp constraints such as 'greater than'. Finally, we show that this tractable class is maximal, in the sense that adding any other form of soft binary constraint which is not in the class gives rise to a class of problems which is NP-hard.

Subfields: Computational Theory and Mathematics, Computer Networks and Communications, Industrial and Manufacturing Engineering

View Paper: https://www.semanticscholar.org/paper/86a5154b6bcbe3d56f8a0efeca76432e1d1c093f

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Computer Networks and Communications

In Industrial and Manufacturing Engineering

Citations in the corpus

Robotic mapping: a survey (2003, background): “Conversely, if we already had a map of the environment, there exist computationally elegant and efficient algorithms for determining the robot’s pose at any point in time [7, 36].”
Pedestrian localisation for indoor environments (2008, methodology): “This approach was shown to allow successful robot localisation and subsequent tracking with a mean position error of 5 cm for a robot equipped with a laser-range finder [66].”
Localization of wireless sensor networks with a mobile beacon (2004, background): “In robotics, the exact location, as well as the orientation, of a robot was extensively considered [19]–[23].”
Robotics-Based Location Sensing Using Wireless Ethernet (2002, background): “Possibly the most powerful family of global localization algorithms to date is based on Bayesian inference, in particular Markov localization [24, 15] and Monte Carlo localization [13, 37].”
Map building with mobile robots in dynamic environments (2003, background): “[9] present a probabilistic technique to identify range measurements that do not correspond to the given model of the environment.”
Distributed Multirobot Exploration and Mapping (2005, methodology): “Step 12 handles locations inside the partial map by multiplying the trajectory weight with the observation likelihood, which can be extracted from the map, exactly as in regular robot localization [8], [9], [34].”
Subgroup Discovery with CN2-SD (2004, methodology): “SUBGROUP DISCOVERY WITH CN2-SD As a remedy to this problem we propose the use of a weighted covering algorithm (Gamberger and Lavrač, 2002), in which the subsequently induced rules (i.e., rules induced in the later stages) also represent interesting and sufficiently large subgroups of the…”