Algorithms and Ordering Heuristics for Distributed Constraint Satisfaction Problems E-Book

Mohamed Wahbi

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Englisch

Seitenzahl: 284

Veröffentlichungsjahr: 2013

Beschreibung

DisCSP (Distributed Constraint Satisfaction Problem) is a general framework for solving distributed problems arising in Distributed Artificial Intelligence.

A wide variety of problems in artificial intelligence are solved using the constraint satisfaction problem paradigm. However, there are several applications in multi-agent coordination that are of a distributed nature. In this type of application, the knowledge about the problem, that is, variables and constraints, may be logically or geographically distributed among physical distributed agents. This distribution is mainly due to privacy and/or security requirements. Therefore, a distributed model allowing a decentralized solving process is more adequate to model and solve such kinds of problem. The distributed constraint satisfaction problem has such properties.

Leseprobe

Contents

Preface

Introduction

PART 1: Background On Centralized and Distributed Constraint Reasoning

1 Constraint Satisfaction Problems

1.1. Centralized constraint satisfaction problems

1.2. Algorithms and techniques for solving centralized CSPs

1.3. Summary

2 Distributed Constraint Satisfaction Problems

2.1. Distributed constraint satisfaction problems

2.2. Methods for solving DisCSPs

2.3. Summary

PART 2: Synchronous Search Algorithms for DisCSPs

3 Nogood-Based Asynchronous Forward Checking (AFC-ng)

3.1. Introduction

3.2. Nogood-based asynchronous forward checking

3.3. Correctness proofs

3.4. Experimental evaluation

3.5. Summary

4 Asynchronous Forward-Checking Tree (AFC-tree)

4.1. Introduction

4.2. Pseudo-tree ordering

4.3. Distributed depth-first search tree construction

4.4. The AFC-tree algorithm

4.5. Correctness proofs

4.6. Experimental evaluation

4.7. Other related works

4.8. Summary

5 Maintaining Arc Consistency Asynchronously in Synchronous Distributed Search

5.1. Introduction

5.2. Maintaining arc consistency

5.3. Maintaining arc consistency asynchronously

5.4. Theoretical analysis

5.5. Experimental results

5.6. Summary

PART 3: Asynchronous Search Algorithms and Ordering Heuristics for Discsps

6 Corrigendum to “Min-Domain Retroactive Ordering for Asynchronous Backtracking”

6.1. Introduction

6.2. Background

6.3. ABT_DO-Retro may not terminate

6.4. The right way to compare orders

6.5. Summary

7 Agile Asynchronous Backtracking (Agile-ABT)

7.1. Introduction

7.2. Introductory material

7.3. The algorithm

7.4. Correctness and complexity

7.5. Experimental results

7.6. Related works

7.7. Summary

PART 4: DisChoco 2.0: A Platform for Distributed Constraint Reasoning

8 DisChoco 2.0

8.1. Introduction

8.2. Architecture

8.3. Using DisChoco 2.0

8.4. Experimentations

8.5. Conclusion

Conclusions

Bibliography

Index

In memory of a great man,

Mouhamed Moumane

First published 2013 in Great Britain and the United States by ISTE Ltd and John Wiley & Sons, Inc.

Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms and licenses issued by the CLA. Enquiries concerning reproduction outside these terms should be sent to the publishers at the undermentioned address:

ISTE Ltd

27-37 St George’s Road

London SW19 4EU

UK

www.iste.co.uk

John Wiley & Sons, Inc.

111 River Street

Hoboken, NJ 07030

USA

www.wiley.com

© ISTE Ltd 2013

The rights of Mohamed Wahbi to be identified as the author of this work have been asserted by him in accordance with the Copyright, Designs and Patents Act 1988.

Library of Congress Control Number: 2013937865

British Library Cataloguing-in-Publication Data

A CIP record for this book is available from the British Library

ISSN: 2051-2481 (Print)

ISSN: 2051-249X (Online)

ISBN: 978-1-84821-594-8

Preface

Constraint programming is an area in computer science that has gained increasing interest in recent years. Constraint programming is based on its powerful framework called constraint satisfaction problem (CSP). CSP is a general framework that can formalize many real-world combinatorial problems such as resource allocation, car sequencing, natural language understanding and machine vision. A CSP consists of looking for solutions to a constraint network, i.e. a set of assignments of values to variables that satisfy the constraints of the problem. These constraints represent restrictions on value combinations allowed for constrained variables.

Various applications that are of a distributed nature exist. In this kind of application, the knowledge about the problem, i.e. variables and constraints, is distributed among physically distributed agents. This distribution is mainly due to privacy and/or security requirements: constraints or possible values may be strategic information that should not be revealed to other agents that can be seen as competitors. Several applications in multi-agent coordination are of such kind. Examples of applications are sensor networks [JUN 01, BÉJ 05], military unmanned aerial vehicle teams [JUN 01], distributed scheduling problems [WAL 02, MAH 04], distributed resource allocation problems [PET 04], log-based reconciliation [CHO 06], distributed vehicle routing problems [LÉA 11], etc. Therefore, the distributed framework distributed constraint satisfaction problem (DisCSP) is used to model and solve this kind of problem.

A DisCSP is composed of a group of autonomous agents, where each agent has control of some elements of information about the whole problem, i.e. variables and constraints. Each agent owns its local constraint network. Variables in different agents are connected by constraints. Agents must assign, in a distributed manner, values to their variables so that all constraints are satisfied. Hence, agents assign values to their variables, attempting to generate locally consistent assignments that are also consistent with constraints between agents [YOK 98, YOK 00a]. To achieve this goal, agents check the values assigned to their variables for local consistency and exchange messages to check the consistency of their proposed assignments against constraints that contain variables that belong to other agents.

Many distributed algorithms for solving DisCSPs have been designed in the last two decades. They can be divided into two main groups: synchronous and asynchronous algorithms. The first category includes algorithms in which agents assign values to their variables in a synchronous and sequential way. The second category includes algorithms in which the process of proposing values to the variables and exchanging these proposals is performed asynchronously between the agents. In the former category, agents do not have to wait for decisions of others, whereas, in general, only one agent has the privilege of making a decision in the synchronous algorithms.

This book tries to extend the state of the art by proposing several algorithms and heuristics for solving the DisCSPs. The book starts with a brief introduction to the state of the art in the area of centralized constraint programming. The (CSP) formalism is defined and some academic and real examples of problems that can be modeled and solved by CSP are presented. Then, typical methods for solving centralized CSPs are briefly reported. Next, preliminary definitions on the DisCSP formalism are given. Afterward, the main algorithms that have been developed in the literature to solve DisCSPs are described.

The second part of this book provides three algorithms for solving DisCSPs. These algorithms are classified under the category of synchronous algorithms. The first algorithm is the nogood-based asynchronous forward checking (AFC-ng). AFC-ng is a nogood-based version of the asynchronous forward checking (AFC) [MEI 07] algorithm. Besides its use of nogoods as justification of value removals, AFC-ng allows simultaneous backtracks to go from different agents to different destinations. AFC-ng only needs polynomial space. Proofs of the correctness of the AFC-ng are also given. A comparison of its performance with other well-known distributed algorithms for solving DisCSP is presented. The results are reported for random DisCSPs and instances from real benchmarks: sensor networks and distributed meeting scheduling.

The second algorithm, called asynchronous forward-checking tree (AFC-tree), extends the AFC-ng algorithm using a pseudo-tree arrangement of the constraint graph. To achieve this goal, agents are ordered a priori in a pseudo-tree such that agents in different branches of the tree do not share any constraint. AFC-tree does not address the process of ordering the agents in a pseudo-tree arrangement. The construction of the pseudo-tree is done in a preprocessing step. Using this priority ordering, AFC-tree performs multiple AFC-ng processes on the paths from the root to the leaves of the pseudo-tree. The good properties of the AFC-tree are demonstrated. AFC-tree is compared to AFC-ng on random DisCSPs and instances from real benchmarks: sensor networks and distributed meeting scheduling.

In the third synchronous algorithm, maintaining the arc consistency in a synchronous search algorithm is proposed. Instead of using forward checking as a filtering property like the AFC-ng algorithm does, it is suggested maintaining arc consistency asynchronously (MACA). Thus, two new algorithms based on the same mechanism as AFC-ng that enforce arc consistency asynchronously are presented. The first, called MACA-del, enforces arc consistency due to an additional type of message: deletion message. The second, called MACA-not, achieves arc consistency without any new type of message. A theoretical analysis and an experimental evaluation of the proposed approaches are provided.

The third part of the book presents two contributions in the asynchronous algorithms category. Under this category, Zivan et al. presented the asynchronous backtracking algorithm with dynamic ordering using retroactive heuristics (ABT_DO-Retro) [ZIV 09]. ABT_DO-Retro allows changing the order of agents during distributed asynchronous complete search. Unfortunately, the description of the time-stamping protocol used to compare orders in ABT_DO-Retro may lead to an implementation in which ABT_DO-Retro may not terminate. The first contribution under the asynchronous category provides a corrigendum of the protocol designed for establishing the priority between orders in ABT_DO-Retro. An example that shows, if ABT_DO-Retro uses that protocol, how it can fall into an infinite loop is presented. The correct method for comparing time stamps and the proof of its correctness are given.

Afterwards, the agile asynchronous backtracking algorithm (Agile-ABT), the second contribution under the asynchronous category, is presented. Agile-ABT is a distributed asynchronous search procedure that is able to change the ordering of agents more than previous asynchronous approaches. In Agile-ABT, the order of agents appearing before the agent receiving a backtrack message can be changed with great freedom, while ensuring polynomial space complexity. This is done via the original notion of termination value, a vector of stamps labeling the new orders exchanged by agents during the search. First, the concepts needed to select new orders that decrease the termination value are described. Next, the details of Agile-ABT algorithm are given. A description of how agents can reorder themselves as much as they want, as long as the termination value decreases as the search progresses, is shown.

The book ends by describing the new version of the DisChoco open-source platform for solving distributed constraint reasoning problems. The new version, DisChoco 2.0, provides an implementation of all algorithms mentioned so far and, obviously, many others. DisChoco 2.0 is a complete redesign of the DisChoco platform. DisChoco 2.0 is a Java library, which aims at implementing distributed constraint reasoning algorithms. DisChoco 2.0 then offers a complete tool to the research community for evaluating algorithms performance or being used for real applications.

This book is the result of 3 years of intense research with the supervisors of my PhD thesis: Christian Bessiere and El-Houssine Bouyakhf. It is with immense gratitude that I acknowledge their support, advice and guidance during my PhD studies at the University of Montpellier, France, and Mohammed V University–Agdal, Morocco. Much of the work presented in this book has been done in collaboration with such highly motivated, smart, enthusiastic and passionate co-authors. I want to thank them for their teamwork and devotion. My special gratitude goes to Redouane Ezzahir and Younes Mechqrane.

Introduction

Constraint satisfaction problems (CSPs) can formalize many real-world combinatorial problems such as resource allocation, car sequencing and machine vision. A CSP consists of looking for solutions to a constraint network, i.e. finding a set of assignments of values to variables that satisfy the constraints of the problem. These constraints specify admissible value combinations. Numerous powerful algorithms have been designed for solving CSPs. Typical systematic search algorithms try to construct a solution to a CSP by incrementally instantiating the variables of the problem. However, proving the existence of solutions or finding a solution in a CSP are NP1-complete tasks. Thus, many heuristics have been developed to improve the efficiency of search algorithms.

Sensor networks [JUN 01, BÉJ 05], military unmanned aerial vehicle teams [JUN 01], distributed scheduling problems [WAL 02, MAH 04], distributed resource allocation problems [PET 04], log-based reconciliation [CHO 06], distributed vehicle routing problems [LÉA 11], etc., are real applications of a distributed nature, i.e., the knowledge about the problem is distributed among several entities/agents that are physically distributed. These applications can be naturally modeled and solved by a CSP process once the knowledge about the whole problem is delivered to a centralized solver. However, in such applications, gathering the whole knowledge into a centralized solver is undesirable. In general, this restriction is mainly due to privacy and/or security requirements: constraints or possible values may be strategic information that should not be revealed to other agents that can be seen as competitors. The cost or the inability of translating all information into a single format may be another reason. In addition, a distributed system provides fault tolerance, which means that if some agents disconnect, a solution might be available for the connected part. Thereby, a distributed model allowing a decentralized solving process is more adequate. The distributed constraint satisfaction problem (DisCSP) has such properties.

A DisCSP is composed of a group of autonomous agents, where each agent has control of some elements of information about the whole problem, i.e. variables and constraints. Each agent owns its local constraint network. Variables in different agents are connected by constraints. To solve a DisCSP, agents must assign values to their variables so that all constraints are satisfied. Hence, agents assign values to their variables, attempting to generate a locally consistent assignment that is also consistent with constraints between agents [YOK 98, YOK 00a]. To achieve this goal, agents check the values assigned to their variables for local consistency and exchange messages among them to check the consistency of their proposed assignments against constraints that contain variables that belong to others agents.

In solving DisCSPs, agents exchange messages about the variable assignments and conflicts of constraints. Several distributed algorithms for solving DisCSPs have been designed in the last two decades. They can be divided into two main groups: synchronous and asynchronous algorithms. The first category are algorithms in which the agents assign values to their variables in a synchronous, sequential way. The second category are algorithms in which the process of proposing values to the variables and exchanging these proposals is performed asynchronously between the agents. In the former category, agents do not have to wait for decisions of others whereas, in general, only one agent has the privilege of making a decision in the synchronous algorithms.

The first complete asynchronous search algorithm for solving DisCSPs is asynchronous backtracking (ABT) [YOK 92, YOK 00a, BES 05]. ABT is an asynchronous algorithm executed autonomously by each agent in the distributed problem. Synchronous backtrack (SBT) is the simplest DisCSP search algorithm [YOK 00a]. SBT performs assignments sequentially and synchronously. SBT agents assign their variables one by one, recording their assignments on a data structure called the current partial assignment (CPA). In SBT, only the agent holding a CPA performs an assignment or backtrack [ZIV 03]. Meisels and Zivan extended SBT to asynchronous forward checking (AFC), an algorithm in which the FC algorithm [HAR 80] is performed asynchronously [MEI 07]. In AFC, whenever an agent succeeds to extend the CPA, it sends the CPA to its successor and sends copies of this CPA to the other unassigned agents in order to perform FC asynchronously.

A major motivation for research on DisCSP is that it is an elegant model for many everyday combinatorial problems that are distributed by nature. Incidentally, DisCSP is a general framework for solving various problems arising in distributed artificial intelligence. Improving the efficiency of existing algorithms for solving DisCSP is an important key for research in the distributed artificial intelligence field. In this book, we extend the state of the art in solving the DisCSPs by proposing several algorithms. We believe that these algorithms are significant as they improve the current state of the art in terms of run-time and number of exchanged messages experimentally.

Nogood-based asynchronous forward checking (AFC-ng): AFC-ng is a synchronous algorithm based on asynchronous forward checking (AFC) for solving DisCSPs. Instead of using the shortest inconsistent partial assignments, AFC-ng uses nogoods as justifications of value removals. Unlike AFC, AFC-ng allows concurrent backtracks to be performed at the same time, coming from different agents having an empty domain to different destinations. Because of the time stamps integrated into the CPAs, the strongest CPA coming from the highest level in the agent ordering will eventually dominate all others. Interestingly, the search process with the strongest CPA will benefit from the computational effort done by the (killed) lower-level processes. This is done by taking advantage of the computational effort of nogoods recorded when processing these lower-level processes.

Asynchronous forward-checking tree (AFC-tree): the main feature of the AFC-tree algorithm is using different agents to search non-intersecting parts of the search space concurrently. In AFC-tree, agents are prioritized according to a pseudo-tree arrangement of the constraint graph. The pseudo-tree ordering is built in a preprocessing step. Using this priority ordering, AFC-tree performs multiple AFC-ng processes on the paths from the root to the leaves of the pseudo-tree. The agents that are brothers are committed to concurrently finding the partial solutions of their variables. Therefore, AFC-tree exploits the potential speedup of a parallel exploration in the processing of distributed problems.

Maintaining arc consistency asynchronously (MACA): instead of maintaining forward checking asynchronously on agents not yet instantiated, as is done in AFC-ng, we propose to maintain arc consistency asynchronously on these future agents. We propose two new synchronous search algorithms that maintain arc consistency asynchronously (MACA). The first algorithm we propose, MACA-del, enforces arc consistency due to additional type of messages, deletion messages (del). Hence, whenever values are removed during a constraint propagation step, MACA-del agents notify other agents that may be affected by these removals, sending them a del message. The second algorithm, MACA-not, achieves arc consistency without any new type of message. We have achieved this by storing all deletions performed by an agent on domains of its neighboring agents, and sending this information to these neighbors within the CPA message.

Corrigendum to “min-domain retroactive ordering for asynchronous backtracking”: a corrigendum of the protocol designed for establishing the priority between orders in the asynchronous backtracking algorithm with dynamic ordering using retroactive heuristics (ABT_DO-Retro) is proposed. We present an example that shows how ABT_DO-Retro can enter an infinite loop following the natural understanding of the description given by the authors of ABT_DO-Retro. We describe the correct way for comparing time stamps of orders. We give the proof that our method for comparing orders is correct.

Agile asynchronous backtracking (Agile-ABT): Agile-ABT is an asynchronous dynamic ordering algorithm that does not follow the standard restrictions in ABT algorithms. The order of agents appearing before the agent receiving a backtrack message can be changed with a great freedom while ensuring polynomial space complexity. Furthermore, the agent receiving the backtrack message, called the backtracking target, is not necessarily the agent with the lowest priority among the conflicting agents in the current order. The principle of Agile-ABT is built on termination values exchanged by agents during search. A termination value is a tuple of positive integers attached to an order. Each positive integer in the tuple represents the expected current domain size of the agent in that position in the order. Orders are changed by agents without any global control so that the termination value decreases lexicographically as the search progresses. Because a domain size can never be negative, termination values cannot decrease indefinitely. An agent informs the others of a new order by sending them its new order and its new termination value. When an agent compares two contradictory orders, it keeps the order associated with the smallest termination value.

DisChoco 2.0: DisChoco 2.02 is an open-source platform for solving distributed constraint reasoning problems. The new version 2.0 is a complete redesign of the DisChoco platform. DisChoco 2.0 is not a distributed version of the centralized solver Choco3, but it implements a model to solve distributed constraint networks with local complex problems (i.e. several variables per agent) by using Choco as the local solver to each agent. The novel version we propose has several interesting features: it is reliable and modular, it is easy to personalize and extend, its kernel is independent from the communication system and it allows for a deployment in a real distributed system as well as a simulation on a single Java virtual machine. DisChoco 2.0 is an open-source Java library, which aims at implementing distributed constraint reasoning algorithms from an abstract model of agent (already implemented in DisChoco). A single implementation of a distributed constraint reasoning algorithm can run as simulation on a single machine, or on a network of machines that are connected via the Internet or via a wireless ad hoc network or even on mobile phones compatible with J2ME.

2http://www2.lirmm.fr/coconut/dischoco/.

3http://choco.emn.fr/.

PART 1

Background on Centralized and Distributed Constraint Reasoning