On Infinite Domain Csps Parameterized By Solution Cost

On Infinite-Domain CSPs Parameterized by Solution Cost

In this thesis we study the computational complexity of MinCSP - an optimization version of the Constraint Satisfaction Problem (CSP). The input to a MinCSP is a set of variables and constraints applied to these variables, and the goal is to assign values (from a fixed domain) to the variables while minimizing the solution cost, i.e. the number of unsatisfied constraints. We are specifically interested in MinCSP with infinite domains of values. Infinite-domain MinCSPs model fundamental optimization problems in computer science and are of particular relevance to artificial intelligence, especially temporal and spatial reasoning. The usual way to study computational complexity of CSPs is to restrict the types of constraints that can be used in the inputs, and either construct fast algorithms or prove lower bounds on the complexity of the resulting problems. The vast majority of interesting MinCSPs are NP-hard, so standard complexity-theoretic assumptions imply that we cannot find exact solutions to all inputs of these problems in polynomial time with respect to the input size. Hence, we need to relax at least one of the three requirements above, opting for either approximate solutions, solving some inputs, or using super-polynomial time. Parameterized algorithms exploits the latter two relaxations by identifying some common structure of the interesting inputs described by some parameter, and then allowing super-polynomial running times with respect to that parameter. Such algorithms are feasible for inputs of any size whenever the parameter value is small. For MinCSP, a natural parameter is optimal solution cost. We also study parameterized approximation algorithms, where the requirement for exact solutions is also relaxed. We present complete complexity classifications for several important classes of infinite-domain constraints. These are simple temporal constraints and interval constraints, which have notable applications in temporal reasoning in AI, linear equations over finite and infinite fields as well as some commutative rings (e.g., the rationals and the integers), which are of fundamental theoretical importance, and equality constraints, which are closely related to connectivity problems in undirected graphs and form the basis of studying first-order definable constraints over infinite domains. In all cases, we prove results as follows: we fix a (possibly infinite) set of allowed constraint types C, and for every finite subset of C, determine whether MinCSP(), i.e., MinCSP restricted to the constraint types in , is fixed-parameter tractable, i.e. solvable in f(k) · poly(n) time, where k is the parameter, n is the input size, and f is any function that depends solely on k. To rule out such algorithms, we prove lower bounds under standard assumptions of parameterized complexity. In all cases except simple temporal constraints, we also provide complete classifications for fixed-parameter time constant-factor approximation.

On Infinite-Domain CSPs Parameterized by Solution Cost

Companion Robots for Older Adults

This thesis explores, through a mixed-methods approach, what happens when companion robots are deployed in care homes for older adults by looking at different perspectives from key stakeholders. Nine studies are presented with decision makers in municipalities, care staff and older adults, as participants, and the studies have primarily been carried out in the field in care homes and activity centres, where both qualitative (e.g., observations and workshops) and quantitative data (surveys) have been collected. The thesis shows that companion robots seem to be here to stay and that they can contribute to a higher quality of life for some older adults. It further presents some challenges with a certain discrepancy between what decision makers want and what staff might be able to facilitate. For future research and use of companion robots, it is key to evaluate each robot model and potential use case separately and develop clear routines for how they should be used, and most importantly, let all stakeholders be part of the process. The knowledge contribution is the holistic view of how different actors affect each other when emerging robot technology is introduced in a care environment. Den här avhandlingen utforskar vad som händer när sällskapsrobotar införs på omsorgsboenden för äldre genom att titta på perspektiv från olika intressenter. Nio studier presenteras med kommunala beslutsfattare, vårdpersonal och äldre som deltagare. Studierna har i huvudsak genomförts i fält på särskilda boenden och aktivitetscenter där både kvalitativa- (exempelvis observationer och workshops) och kvantitativa data (enkäter) har samlats in. Avhandlingen visar att sällskapsrobotar verkar vara här för att stanna och att de kan bidra till en högre livskvalitet för vissa äldre. Den visar även på en del utmaningar med en viss diskrepans mellan vad beslutsfattare vill införa och vad personalen har möjlighet att utföra i sitt arbete. För framtida forskning och användning av sällskapsrobotar är det viktigt att utvärdera varje robotmodell och varje användningsområde var för sig och ta fram tydliga rutiner för hur de ska användas, och viktigast av allt, låta alla intressenter vara en del av processen. Kunskapsbidraget med avhandlingen är en helhetssyn på hur olika aktörer påverkar varandra när ny robotteknik introduceras i en vårdmiljö