Problem decomposition in distributed problem-solving systems

Distributed Problem Solving (DPS) is defined as the cooperative solution of problems by a decentralized and loosely coupled collection of problem solvers (agents), each of them knowing how to execute only some of the necessary tasks. This approach considers the problem-solving process as occurring in three phases: problem decomposition, subproblem solution, and answer synthesis. In the problem decomposition phase, one has to determine which tasks will be executed by each agent and when. One of the key research questions in the problem decomposition process is how to decompose a problem in order to minimize the cost of resources needed for its solution. In this article, we construct mathematical programming models in order to describe the decomposition process under the above criterion, study its complexity, and present exact and heuristic algorithms for its solution. Our work was motivated by the operation of an actual system that can be considered as a distributed problem solver for the assessment of irrigation projects design.     

Actors: A unifying model for parallel and distributed computing

Parallel computing and distributed computing have traditionally evolved as two separate research disciplines. Parallel computing has addressed problems of communication-intensive computation on tightly-coupled processors while distributed computing has been concerned with coordination, availability, timeliness, etc., of more loosely coupled computations. Current trends, such as parallel computing on networks of conventional processors and Internet computing, suggest the advantages of unifying these two disciplines. Actors provide a flexible model of computation which supports both parallel and distributed computing. One may evaluate the utility of a programming paradigm in terms of four criteria: expressiveness, portability, efficiency, and performance predictability. We discuss how the Actor model and programming methods based on it support these goals. In particular, we provide an overview of the state of the art in Actor languages and their implementation. Finally, we place this work in the context of recent developments in middleware, the Java language, and agents.     

The election problem in asynchronous distributed systems with bounded faulty processes

Determining the “weakest” failure detectors is a central topic in solving many agreement problems such as Consensus, Non-Blocking Atomic Commit and Election in asynchronous distributed systems. So far, this has been studied extensively for several such fundamental problems. It is stated that Perfect Failure Detector P is the weakest failure detector to solve the Election problem with any number of faulty processes. In this paper, we introduce Modal failure detector M and show that to solve Election, M is the weakest failure detector to solve election when the number of faulty processes is less than ⌈n/2⌉. We also show that it is strictly weaker than P.

A survey on distributed online optimization and online games

Distributed online optimization and online games have been increasingly researched in the last decade, mostly motivated by their wide applications in sensor networks, robotics (e.g., distributed target tracking and formation control), smart grids, deep learning, and so forth. In these problems, there is a network of agents which interact with each other in a collaborative manner (i.e., distributed online optimization) or noncooperative manner (i.e., online games) through local information exchanges. And the local cost function of each agent is time-varying in dynamic and adversarial environments. At each time, a decision must be made by each agent based on historical information at hand without knowing its future cost functions. For these problems, a comprehensive survey is still lacking. This paper aims to provide a thorough overview of distributed online optimization and online games from the perspective of problem settings, algorithms, communication and computation requirements, and performances. In addition, some potential future directions are also discussed.     

Dynamic hierarchical control for distributed problem solving

Distributed problem solving (DPS) has become one of the central topics in AI. Much research has been concerned with finding an appropriate distributed control regime. We propose the concept of dynamic, hierarchical control (DHC) for distributed problem solving.

In many domains, DPS has a natural hierarchy or a subproblem hierarchy can be imposed by utilizing appropriate decomposition techniques. DHC aims at exploiting the power inherent in the hierarchical approach. It also enables the control of the problem solving process to fit the structure of a domain. This results in well-coordinated cooperation and coherent negotiation among distributed controllers.

We have used the DHC to perform plant combine production planning (PCPP). This task involves the activity of a network of production units, each with possibly different characteristics, collaborating to produce various items under dynamically changing conditions. We also describe the general structure of a single controller which adopts a blackboard and a knowledge source (KS) scheduling mechanism to carry out dynamic process execution.

The paper describes the results of our first solution to this problem. Finally, we discuss on-going research that aims at handling additional problems.     

Using cooperative mobile agents to monitor distributed and dynamic environments

Monitoring the changes in data values obtained from the environment (e.g., locations of moving objects) is a primary concern in many fields, as for example in the pervasive computing environment. The monitoring task is challenging from a double perspective. First and foremost, the environment can be highly dynamic in terms of the rate of data changes. Second, the monitored data are often not available from a single computer/device but are distributed; moreover, the set of data providers can change along the course of time. Therefore, obtaining a global snapshot of the environment and keeping it up-to-date is not easy, especially if the conditions (e.g., network delays) change.In this article, a decentralized, loose, and fault-tolerant monitoring approach based on the use of mobile agents is described. Mobile agents allow easy tracking of the involved computers, carrying the monitoring tasks to wherever they are needed. A deadline-based mechanism is used to coordinate the cooperative agents, which strive to perform their continuous tasks in time while considering data as recent as possible, constantly adapting themselves to new environmental conditions (changing communication and processing delays). This approach has been successfully used in a real environment and experiments were carried out to prove its feasibility and benefits.     

Efficient distributed snapshots in an anonymous asynchronous message-passing system

We present a global snapshot algorithm with concurrent initiators, with termination detection in an anonymous asynchronous distributed message-passing system having FIFO channels. In anonymous systems, process identifiers are not available and an algorithm cannot use process identifiers in its operation. Such systems arise in several domains due to a variety of reasons. In the proposed snapshot algorithm for anonymous systems, each instance of algorithm initiation is identified by a random number (nonce); however, this is not used as an address in any form of communication. In the algorithm, each process can determine an instant when the local snapshot recordings at all the processes have terminated. This is a challenging problem when an algorithm cannot use process identifiers and a process does not know the number of processes in the system or the diameter of the network and cannot use a predefined topology overlay on the network, because there is no easy way to identify the global termination condition. The message complexity of our algorithm is (cn²)$\left(c{n}^2\right)$, where c$c$ is the number of concurrent initiators and n$n$ is the number of processes in the system, which is much better than that of the algorithm by Chalopin et al. (2012) [6]. Further, the algorithm by Chalopin et al. also requires knowledge of the network diameter.     

Training individuals for distributed teams: problem solving assessment for distributed mission research

In this paper we describe an effort investigating the feasibility and utility of cognitively diagnostic assessment of problem solving when training for distributed team tasks. We utilized computer-based knowledge elicitation methods to assess both relational problem solving, requiring the semantic integration of concepts, and dynamic problem solving, requiring the ability to integrate and apply these concepts. Additionally, we addressed how metacognitive processes interact with learning outcomes when training for complex synthetic task environments. We find first, that multiple methods of assessing problem solving performance are diagnostic of knowledge acquisition for a complex synthetic team task, and second, that general metacomprehension predisposition is related to metacomprehension accuracy in synthetic task environments.     

分布式求解平行结构类问题中重选区域的研究

本文以平行结构类问题的形式化描述为基础,详细讨论了分布式求解平行结构类问题系统中相邻结点间重迭区域的作用,定义了最小重迭区域的概念,并提出一种新的设立重迭区域方法——“可变法”,最后在分布式运输调度系统上进行了试验研究,结果表明:〈1〉设置重迭区域是必要的;〈2〉最小重迭区域的定义是有意义的;〈3〉与美国麻省大学采用的“固定法”相比,“可变法”保证了求解质量,减少了冗余的计算与通信开销。     

Team-optimal distributed MMSE estimation in general and tree networks

We construct team-optimal estimation algorithms over distributed networks for state estimation in the finite-horizon mean-square error (MSE) sense. Here, we have a distributed collection of agents with processing and cooperation capabilities. These agents observe noisy samples of a desired state through a linear model and seek to learn this state by interacting with each other. Although this problem has attracted significant attention and been studied extensively in fields including machine learning and signal processing, all the well-known strategies do not achieve team-optimal learning performance in the finite-horizon MSE sense. To this end, we formulate the finite-horizon distributed minimum MSE (MMSE) when there is no restriction on the size of the disclosed information, i.e., oracle performance, over an arbitrary network topology. Subsequently, we show that exchange of local estimates is sufficient to achieve the oracle performance only over certain network topologies. By inspecting these network structures, we propose recursive algorithms achieving the oracle performance through the disclosure of local estimates. For practical implementations we also provide approaches to reduce the complexity of the algorithms through the time-windowing of the observations. Finally, in the numerical examples, we demonstrate the superior performance of the introduced algorithms in the finite-horizon MSE sense due to optimal estimation.     

Optimal control of distributed bilinear systems

The optimal control problem for a bilinear distributed parameter system subject to a quadratic cost functional is solved. It is shown that the optimal control is given by a convergent power series in the state with tensor coefficients.     

An object-oriented cooperative distributed problem solving shell with groupware management ability

In this paper, an Object-Oriented Cooperative Distributed Problem Solving Shell (OOCDPSS) with groupware management ability is designed. The groupware management facilities, which satisfy the needs of development and execution of the cooperative distributed problem solving activities, can reinforce concurrency and parallelism, accommodation and integration of heterogeneous, uncoordinated problem solvers cooperating on one common goal. This OOCDPSS system constructs the non-embedded groupware architecture by a hierarchy of leader agents. The leader agent that adopts a distributed blackboard control mechanism can assist the cooperating problem solvers with all the cooperative and coordinative activities at run time through a democratic, contract-net protocol. In this blackboard control mechanism, the system control unit and domain control unit are explicitly separated and put side-by-side in a simple control loop to simplify the control mechanism design. The event messages drive the above control units with the programmable heuristic knowledge, including the static knowledge, procedural knowledge, and strategic, situation-action behavior knowledge. In this OOCDPSS, a completely transparent environment and a programmable distributed blackboard control mechanism are provided. This environment automatically assists and supervises the progress of cooperative problem solving activities at run time, thereby raising the effective level of use among the preexisting problem solvers. In addition, by using the programmable heuristic knowledge, our approach can be efficiently implemented on the cooperative problem solving plans with a range of configurations. ©1997 John Wiley & Sons, Ltd.     

分布式问题求解过程控制的动态层次分布

本文提出过程控制的动态层次分布概念,旨在于分布式问题求解(DPS)领域内开发动态和层次处理方法的功能.为了实现分布的处理器之间紧凑而协调的合作,层次控制是一种有效的方式,但必须动态地加以组织,才能适用于变化的问题求解环境.此外,启发式知识应加以开发去指导控制的动态层次分布.     

Modeling interaction strategies using POS: An application to soccer robots

As seen earlier POS is a general agent conversation protocol engineering formalism that has proved efficient when used in communities of software information agents. The aim of this paper is to show how much POS is simple, easy to use, and very appropriate for implementing interaction protocols in a collaborative agent setting. In order to exemplify our approach we focus on an application domain with real time constraints such as soccer robots and show how an inherently symbolic abstract system like POS can be neatly integrated with agents whose internal architecture is reactive and relies on bottom-up behavior-based techniques. First, we shortly discuss aspects of heterogeneity with respect to soccer robots and present the RoboCup experimental setting. Then we sketch the difficulties that arise when trying to coordinate an heterogeneous team with conventional methods. In response, we introduce some elements of the POS (Protocol Operational Semantics) model. The following sections examine several basic behaviors of the JavaSoccer simulation environment as it is later used along with TeamBots to highlight POS’ capabilities, demonstrate how POS is a suited theoretical tool and leads to extremely compact and modular code due to its high expressive power, and discuss the obtained results. Finally we conclude the article with a comparison to related works as well as some perspectives about the engineering of interaction protocols.     

A Web-based process planning optimization system for distributed design

In this paper, a process planning module, which can optimize the selection of machining resources, determination of set-up plans and sequencing of machining operations to achieve optimized process plans, has been wrapped as services and deployed in the Internet to support distributed design and manufacturing analysis. The module includes four intelligent approaches, and a Tabu search-based approach is explained in this paper to illustrate the optimization process. A Web-based prototype system has been setup for users to carry out visualization-based manipulations and process planning of design models by invoking the services remotely. The Web-based system has been integrated with a distributed feature-based design system, and the latter can generate design models and re-represent them in an XML representation based on VRML and attributes of features to provide the input of the former. Through effective utilization of the Web and Java technologies, this system is independent of the operating system, scalable and service-oriented, and can be used by a geographically distributed design team to organize concurrent engineering design activities effectively.     

Performing work with asynchronous processors: Message-delay-sensitive bounds

This paper considers the problem of performing tasks in asynchronous distributed settings. This problem, called Do-All, has been substantially studied in synchronous models, but there is a dearth of efficient algorithms for asynchronous message-passing processors. Do-All can be trivially solved without any communication by an algorithm where each processor performs all tasks. Assuming p processors and t tasks, this requires work Θ (p · t). Thus, it is important to develop subquadratic solutions (when p and t are comparable) by trading computation for communication. Following the observation that it is not possible to obtain subquadratic work when the message delay d is substantial, e.g., d = Θ (t), this work pursues a message-delay-sensitive approach. Here, the upper bounds on work and communication are given as functions of p, t, and d, the upper bound on message delays, however, algorithms have no knowledge of d and they cannot rely on the existence of an upper bound on d. This paper presents two families of asynchronous algorithms achieving, for the first time, subquadratic work as long as d = o (t). The first family uses as its basis a shared-memory algorithm without having to emulate atomic registers assumed by that algorithm. These deterministic algorithms have work O (tp^ε + pdt/d^ε) for any ε > 0. The second family uses specific permutations of tasks, with certain combinatorial properties, to sequence the work of the processors. These randomized (deterministic) algorithms have expected (worst-case) work O (t log p + pd log (2 + t/d)). Another important contribution in this work is the first delay-sensitive lower bound for this problem that helps explain the behavior of our algorithms: any randomized (deterministic) algorithm has expected (worst-case) work of Ω (t + pd log_d+1t).     

Towards a generic distributed and collaborative digital manufacturing

A framework for distributed manufacturing is proposed to facilitate collaborative product development and production among geographically distributed functional agents using digitalized information. Considering the complexity of products created in a distributed manufacturing scenario, it often requires close collaborations among a number of facilities. In this research work, various functional agents, such as the manufacturability evaluation agent (MEA), manufacturing resource agent (MRA), process-planning agent (PPA), manufacturing scheduling agent (MSA), shop floor agent (SFA), fault diagnosis agent (FDA), etc., can interact coherently for distributed manufacturing. With specific agents having unique functionalities, a manufacturing managing agent (MMA) acts as the centre of this distributed manufacturing system. The MMA agent assists the specific agents’ to work seamlessly and also to collaborate closely with the participating agents. In this way, the production cycle of a part can be optimized from product design to final manufacturing since all the production procedures are considered logically and every procedure is correlated. The agent language based on the knowledge query manipulation language (KQML) includes many pre-defined performatives that ease the participating agents to carry out their tasks intelligently by interpreting commands from one another. Additionally, to ensure the adaptiveness and upgradeability of the system, the internal structure of each functional agent that is based on JATLite is modularized into several components, including a communication interface, central work engine, knowledge base pool, and input/output modifier for possible future methodology enhancements.     

Parallel extremal optimization in processor load balancing for distributed applications

The paper concerns parallel methods for extremal optimization (EO) applied in processor load balancing in execution of distributed programs. In these methods EO algorithms detect an optimized strategy of tasks migration leading to reduction of program execution time. We use an improved EO algorithm with guided state changes (EO-GS) that provides parallel search for next solution state during solution improvement based on some knowledge of the problem. The search is based on two-step stochastic selection using two fitness functions which account for computation and communication assessment of migration targets. Based on the improved EO-GS approach we propose and evaluate several versions of the parallelization methods of EO algorithms in the context of processor load balancing. Some of them use the crossover operation known in genetic algorithms. The quality of the proposed algorithms is evaluated by experiments with simulated load balancing in execution of distributed programs represented as macro data flow graphs. Load balancing based on so parallelized improved EO provides better convergence of the algorithm, smaller number of task migrations to be done and reduced execution time of applications.     

Parameter optimization of distributed hydrological model with a modified dynamically dimensioned search algorithm

A modified version of the dynamically dimensioned search (MDDS) is introduced for automatic calibration of watershed simulation models. The distinguishing feature of the MDDS is that the algorithm makes full use of sensitivity information in the optimization procedure. The Latin hypercube one-factor-at-a-time (LH-OAT) technique is used to calculate the sensitivity information of every parameter in the model. The performance of the MDDS is compared to that of the dynamically dimensioned search (DDS), the DDS identifying only the most sensitive parameters, and the shuffled complex evolution (SCE) method, respectively, for calibration of the easy distributed hydrological model (EasyDHM). The comparisons range from 500 to 5000 model evaluations per optimization trial. The results show the following: the MDDS algorithm outperforms the DDS algorithm, the DDS algorithm identifying the most sensitive parameters, and the SCE algorithm within a specified maximum number of function evaluations (fewer than 5000); the MDDS algorithm shows robustness compared with the DDS algorithm when the maximum number of model evaluations is less than 2500; the advantages of the MDDS algorithm are more obvious for a high-dimensional distributed hydrological model, such as the EasyDHM model; and the optimization results from the MDDS algorithm are not very sensitive to either the variance (between 0.3 and 1) for randn′ used in the MDDS algorithm or the number of strata used in the Latin hypercube (LH) sampling.     

A distributed platform for personalized advertising in digital interactive TV environments

Advertising plays an important role in modern free markets. Furthermore, advertising is moving towards the establishment of one-to-one marketing relationships. Thus, personalized advertisement is currently considered as a hot topic in product promotion as it can be proved beneficial for all the key players, such as the advertisers, the advertised companies, as well as the consumers. Interactive TV and WWW can provide the means for personalized advertising. But of course, special systems and platforms for personalization must be first developed. This paper proposes a prototype system which efficiently achieves the personalization of the advertisements in the environment of digital interactive TV. Thus, the environment for the exploitation of the proposed system are examined, the details in design and implementation are given, while extensive operation testing and evaluation are provided proving its high applicability in real business environments.