Roger Mailler

AAMAS Conference 2018 Conference Paper

Analyzing the Effect of Information Stagnancy on the Distributed Stochastic Algorithm

• Saeid SamadiDana
• Roger Mailler

Despite the fact that many real world problems change over time, many Distributed Constraint Optimization Problem (DCOP) algorithms assume that the problem is constant or changing at a negligible rate. In addition, these algorithms also assume that changes to the environment are instantaneously observable. However, in highly dynamic environments with communication delays, both of these assumptions can be violated resulting in problem solving with out-of-date information. In this study, we explore the relationship between environmental dynamics, information stagnancy, and solution quality in Dynamic DCOP problems. By using recent advances in the analysis of dynamic, distributed problems, we show that information stagnancy can be characterized and used to accurately predict the behavior of a protocol. To evaluate our finding, we use the Distributed Stochastic Algorithm (DSA) as a basis. Through extensive empirical testing, we show that the prediction function is accurate.

AAMAS Conference 2018 Conference Paper

MTL Robustness for Path Planning with A*

• Sarra Alqahtani
• Ian Riley
• Samuel Taylor
• ROSE GAMBLE
• Roger Mailler

Maintaining the safety of an autonomous drone while it executes a mission is a primary concern in presence of fixed and mobile enemies. Path planning using A* fails to deliver a feasible, safe plan when a drone has resource limitations in such environments. Enhancing A* with constraint optimization techniques may improve outcomes, but significantly increases path determination time. We define Robust A* (RA*) that introduces the use of a safety margin to maximize the robustness of the drone to meet mission requirements while managing resource restrictions. We rely on a theory of robustness based on Metric Temporal Logic (MTL) as applied to offline verification and online control of hybrid systems. By satisfying the predefined MTL constraints, RA* dynamically defines a safety margin between the drone and an enemy, while constraining the margin size given the drone’s resources. The safety margin creates a robust neighborhood around the dynamically generated path. The robust neighborhood holds all valid trajectories within the current world state. When the world state changes, RA* first examines the robust neighborhood to find a valid trajectory before initiating the path re-planning. We evaluate RA* using the Rassim simulator. The results show that the algorithm generates faster and safer paths than the classical A* in the presence of moving enemies. 1.

JAAMAS Journal 2017 Journal Article

Dynamic, distributed constraint solving and thermodynamic theory

• Roger Mailler
• Huimin Zheng
• Anton Ridgway

Abstract There has been an increasing recognition that a number of key computational problems require distributed solution techniques. To facilitate the creation and advancement of these techniques, researchers have developed the distributed constraint satisfaction and optimization (DCSP/DCOP) formalisms with the understanding that many critical real-world problems can be represented using them. Subsequently, these formalisms have led to the creation of numerous protocols where most ignore a critical feature of the problems they are designed to solve: the problems change over time. Dynamic variations of the DCSP and DCOP formalisms were invented to address this deficiency, but these models have received inadequate attention from the research community. A key impediment to advancing this research area is the lack of a compelling theoretical underpinning to the analysis of these problems and the evaluation of the protocols used to solve them. This work creates a mapping of the DynDCSP and DynDCOP formalisms onto thermodynamic systems. Under this mapping, it shows that these problems obey the three laws of thermodynamics. Utilizing these laws, this work develops, for the first time, a method for characterizing the impact that dynamics has on a distributed problem as well as a technique for predicting the expected performance of distributed protocols under various levels of dynamics.

AAMAS Conference 2013 Conference Paper

Distributed Problem Solving in Geometrically-Structured Constraint Networks

• Roger Mailler
• Huimin Zheng

Distributed Constraint Satisfaction (DisCSP) is a popular formalism that is used for developing a wide variety of generalpurpose protocols. With very few exceptions, these protocol are tested using completely random instances with the understanding that this leads to better overall solutions. In many real-world situations, however, the variables in the problem represent objects that exist in n-dimensional space with constraints between them based on distance. In such instances, the constraint network forms a geometric graph and therefore is referred to as a Geometrically-Structured Constraint Satisfaction Problem (GS-CSP). This paper introduces the GS-CSP and evaluates the performance of two complete DisCSP protocols to demonstrate how the introduction of structure affects these general problem solving approaches. Our findings show that GS-CSPs possess unique characteristics particularly in the phase transition regions and these characteristics can have a dramatic impact on the performance of current DisCSP algorithms.

AAMAS Conference 2013 Conference Paper

Telescope Management for Satellite Tracking: A Decentralized Approach

• Feyza Merve Hafizoğlu
• Roger Mailler

The rate that the space debris is increasing has now outpaced our ability to build additional sites. Another solution is to use large numbers of low-cost optical sensors, which can be easily deployed at a fraction of the cost of a traditional tracking station. In this paper, we describe the satellite tracking problem, a complex coordination problem that is subject to time and position constraints that must be solved in a communication limited environment. We adopt scheduling by a central facility as an initial solution and compare central and distributed repair mechanisms in terms of tracks completed.

AAMAS Conference 2010 Conference Paper

Improving the Efficiency of the Distributed Stochastic Algorithm

• Melanie Smith
• Roger Mailler

The Distributed Stochastic Algorithm (DSA) is a distributedhill-climbing technique for solving large Distributed Constraint Optimization Problems (DCOPs) such as distributedscheduling, resource allocation, and distributed route planning. The best known version of DSA, DSA-B, works byhaving agents change their assignments with probability $p$when making that change will improve their solution (ahill-climbing move). To escape local minima, DSA-B performs a lateral escape move by switching to another equallygood value with the same probability $p$. It is unclear whyhill climbing and escape moves are chosen with the sameprobability. We investigate the performance effects of making these moves with different probabilities, $p_H$ and $p_L$. Through empirical evaluation, we discover that the efficiencyof DSA can not only be considerably improved, but canbe more specifically tuned to a particular domain or user'sneeds when these two move types are considered separately. Our work also shows that DSA can outperform both DBAand DPP when it is properly tuned.

AAMAS Conference 2009 Conference Paper

MABLE: A Framework for Learning from Natural Instruction

• Roger Mailler
• Daniel Bryce
• Jiaying Shen
• Ciaran O'Reilly

IJCAI Conference 2007 Conference Paper

• Adrian Petcu
• Boi Faltings
• Roger Mailler

Fully decentralized algorithms for distributed constraint optimization often require excessive amounts of communication when applied to complex problems. The OptAPO algorithm of Mailler and Lesser uses a strategy of partial centralization to mitigate this problem. We introduce PC-DPOP, a new partial centralization technique, based on the DPOP algorithm of Petcu and Faltings. PC-DPOP provides better control over what parts of the problem are centralized and allows this centralization to be optimal with respect to the chosen communication structure. Unlike OptAPO, PC-DPOP allows for a priory, exact predictions about privacy loss, communication, memory and computational requirements on all nodes and links in the network. Upper bounds on communication and memory requirements can be specified. We also report strong efficiency gains over OptAPO in experiments on three problem domains.

AAMAS Conference 2005 Conference Paper

Comparing Two Approaches to Dynamic, Distributed Constraint Satisfaction

• Roger Mailler

AAMAS Conference 2004 Conference Paper

Solving Distributed Constraint Optimization Problems Using Cooperative Mediation

• Roger Mailler
• Victor Lesser

AAMAS Conference 2004 Conference Paper

Using Cooperative Mediation to Solve Distributed Constraint Satisfaction Problems

• Roger Mailler
• Victor Lesser

AAMAS Conference 2003 Conference Paper

Cooperative Negotiation for Soft Real-Time Distributed Resource Allocation

• Roger Mailler
• Victor Lesser