A Distributed Constraint Satisfaction Problem (DisCSP) is a CSP which is divided into several inter-related complex local problems, each assigned to a different agent. Thus, each agent has knowledge of the variables and corresponding domains of its local problem together with the constraints relating its own variables (intra-agent constraints) and the constraints linking its local problem to other local problems (inter-agent constraints). DisCSPs have a variety of practical applications including, for example, meeting scheduling and sensor networks. Existing approaches to Distributed Constraint Satisfaction can be mainly classified into two families of algorithms: systematic search and local search. Systematic search algorithms are complete but may take exponential time. Local search algorithms often converge quicker to a solution for large problems but are incomplete. Problem solving could be improved through using hybrid algorithms combining the completeness of systematic search with the speed of local search. This thesis explores hybrid (systematic + local search) algorithms which cooperate to solve DisCSPs. Three new hybrid approaches which combine both systematic and local search for Distributed Constraint Satisfaction are presented: (i) DisHyb; (ii) Multi-Hyb and; (iii) Multi-HDCS. These approaches use distributed local search to gather information about difficult variables and best values in the problem. Distributed systematic search is run with a variable and value ordering determined by the knowledge learnt through local search. Two implementations of each of the three approaches are presented: (i) using penalties as the distributed local search strategy and; (ii) using breakout as the distributed local search strategy. The three approaches are evaluated on several problem classes. The empirical evaluation shows these distributed hybrid approaches to significantly outperform both systematic and local search DisCSP algorithms. DisHyb, Multi-Hyb and Multi-HDCS are shown to substantially speed-up distributed problem solving with distributed systematic search taking less time to run by using the information learnt by distributed local search. As a consequence, larger problems can now be solved in a more practical timeframe.

No description available.

No description available.

No description available.

No description available.

No description available.

No description available.

Thesis (Ph.D.)--Boston University / PLEASE NOTE: Boston University Libraries did not receive an Authorization To Manage form for this thesis or dissertation. It is therefore not openly accessible, though it may be available by request. If you are the author or principal advisor of this work and would like to request open access for it, please contact us at open-help@bu.edu. Thank you. / This dissertation is dedicated to optimization of Stochastic Hybrid Systems (SHS). The concentration is on both online optimization of these systems and extending the known optimal policies in Discrete-Event Systems (DES) to a broader context of SHS. A SHS involves both continuous and discrete dynamics and is suitable for modeling almost any physical system of interest. The first part of this dissertation focuses on applications of SHS and, particularly, a subclass known as Stochastic Flow Models (SFM) used in fluid scheduling. To this end, a classic problem for optimally allocating a resource to multiple competing user queues is considered in the DES context and placed in the framework of SFMs. Infinitesimal Perturbation Analysis (IPA) is used to calculate the gradient estimates for the average holding cost of this system with respect to resource allocation parameters. The monotonicity property of these estimates allows us to prove the optimality of a well-known rule called the "c - mu-rule" under non-idling policies. Furthermore, nonlinear cost functions are considered, yielding simple distribution-free cost sensitivity estimates. Next, we take the first step in using IPA for optimally calculating timeout thresholds in SHS. A Transmission Control Protocol (TCP) communication link is used to examine the effectiveness of SHS and IPA in calculating derivative estimates of a goodput objective with respect to a timeout parameter. The analysis is also extended to the case of multinode communications. Our results reveal a great potential in using IPA to control delay thresholds and motivate more investigations in future. Finally, we propose a general framework for analysis and on-line optimization of SHS which facilitates the use of IPA. In doing so, we modify the previous structure of a Stochastic Hybrid Automaton (SHA) and show that every transition is associated with an explicit event which is defined through a "guard function." This enables us to uniformly treat all events observed on the sample path of the SHS. As a result, a unifying matrix notation for IPA equations is developed which eliminates the need for the case-by-case analysis of event classes as usually done in prior works involving IPA for SHS. / 2031-01-01

1 / Brittan Rosendahl

No description available.