Decentralized control of networked discrete event systems with communication delays

In many practical systems, supervisory control is not performed by one centralized supervisor, but by multiple local supervisors. When communication networks are used in such a system as the medium of information transmission, the communication channels between local supervisors and the system to be controlled will unavoidably result in communication delays. This paper investigates how to use these local supervisors to control the system in order to satisfy given specifications even under communication delays. The specifications are described by two languages: a minimal required language which specifies the minimal required performance that the supervised system must have and a maximal admissible language which specifies the maximal boundary that the supervised system must be in. The results show that if the control problem is solvable, then there exists the minimal control policy which can be calculated based on state estimates. Furthermore, we derive algorithms to check whether the control problem is solvable or not.     

A comparison of three information gathering strategies in DAI systems under noisy conditions

This paper investigates a problem of task allocation in Distributed Artificial Intelligence (DAI) systems, where a coordinator allocates tasks among multiple agents in an optimal manner. In making the task allocation, the coordinator needs to understand the preference orders of the agents for the different task bundles. The coordinator does this by adopting an information acquisition strategy that leads to an optimal system welfare. Three different information acquisition strategies are investigated here. The strategies are compared in a noisy environment for the quality of information they provide in terms of the deviation from optimal system welfare. Copyright 1996 Elsevier Science Ltd     

Reliable decentralized supervisory control of discrete eventsystems

We consider a discrete event system controlled by a decentralized supervisor consisting of n local supervisors, and formulate a new decentralized supervisory control problem, called a reliable decentralized supervisory control problem. A decentralized supervisor is said to be k-reliable (1相似文献   

面向协同任务的多UCAV分布式任务分配与协调技术

对多架无人作战飞机 (Unmanned combat aerial vehicle, UCAV) 分布式控制中的任务分配与任务协调问题开展研究. 采用合同网实现任务执行过程中的任务分配. 通过对合同网进行扩展, 使 UCAV 能够在招标和竞标的同时处理任务间的时间约束. 设计了一种新的部分全局规划协商机制, 能够更有效地对执行相关任务的 UCAV 的任务计划进行协调. 通过 Petri 网建模方法, 将两种协商机制模型化为 Petri 网并分析了协商过程的正确性与协商结果的可行性. 仿真实验验证了方法的有效性.     

Supervisory control synthesis of discrete-event systems using a coordination scheme

Supervisory control of distributed DES with a global specification and local supervisors is a difficult problem. For global specifications, the equivalent conditions for local control synthesis to equal global control synthesis may not be met. This paper formulates and solves a control synthesis problem for a generator with a global specification and with a combination of a coordinator and local controllers. Conditional controllability is proven to be an equivalent condition for the existence of such a coordinated controller. A procedure to compute the least restrictive solution within our coordination control architecture is provided and conditions under which the result coincides with the supremal controllable sublanguage are stated.     

Model Predictive Control for Stochastic Resource Allocation

In this paper, we consider a class of stochastic resource allocation problems where resources assigned to a task may fail probabilistically to complete assigned tasks. Failures to complete a task are observed before new resource allocations are selected. The resulting temporal resource allocation problem is a stochastic control problem, with a discrete state space and control space that grow in cardinality exponentially with the number of tasks. We modify this optimal control problem by expanding the admissible control space, and show that the resulting control problem can be solved exactly by efficient algorithms in time that grows nearly linear with the number of tasks. The approximate control problem also provides a bound on the achievable performance for the original control problem. The approximation is used as part of a model predictive control (MPC) algorithm to generate resource allocations over time in response to information on task completion status. We show in computational experiments that, for single resource class problems, the resulting MPC algorithm achieves nearly the same performance as the optimal dynamic programming algorithm while reducing computation time by over four orders of magnitude. In multiple resource class experiments involving 1000 tasks, the model predictive control performance is within 4% of the performance bound obtained by the solution of the expanded control space problem.     

Automatic singularity avoidance using joint variations in robottask modification

The research community has addressed the need to improve the flexibility of robot systems. Two particular concepts that have resulted from this research are off-line programming and modular tooling. These concepts are directed at allowing the robot system to be used to perform a variety of tasks with minimal setup time and to allow easy replication of an application. Both of these concepts require that the robot system have the ability to measure the position and orientation of features in the workspace. These measurements can then be used to perform coordinate transformations on each of the task data points. These modified task data points then, theoretically, facilitate the performance of the task by the robot system without human intervention     

Development of a reduced human user input task allocation method for multiple robots

Task allocation mechanisms are employed by multi-robot systems to efficiently distribute tasks between different robots. Currently, many task allocation methods rely on detailed expert knowledge to coordinate robots. However, it may not be feasible to dedicate an expert human user to a multi-robot system. Hence, a non-expert user may have to specify tasks to a team of robots in some situations. This paper presents a novel reduced human user input multi-robot task allocation technique that utilises Fuzzy Inference Systems (FISs). A two-stage primary and secondary task allocation process is employed to select a team of robots comprising manager and worker robots. A multi-robot mapping and exploration task is utilised as a model task to evaluate the task allocation process. Experiments show that primary task allocation is able to successfully identify and select manager robots. Similarly, secondary task allocation successfully identifies and selects worker robots. Both task allocation processes are also robust to parameter variation permitting intuitive selection of parameter values.     

Complex Task Allocation in Mobile Surveillance Systems

In mobile surveillance systems, complex task allocation addresses how to optimally assign a set of surveillance tasks to a set of mobile sensing agents to maximize overall expected performance, taking into account the priorities of the tasks and the skill ratings of the mobile sensors. This paper presents a market-based approach to complex task allocation. Complex tasks are the tasks that can be decomposed into subtasks. Both centralized and hierarchical allocations are investigated as winner determination strategies for different levels of allocation and for static and dynamic search tree structures. The objective comparison results show that hierarchical dynamic tree task allocation outperforms all the other techniques especially in complex surveillance operations where large number of robots is used to scan large number of areas.     

Two-level hierarchical control in a large-scale stochastic dynamic system

In this paper a two-level hierarchical control for a resource allocation problem is considered. It is assumed that a coordinator on the upper level and local controllers on the lower level have different information. Soft constraints on control and state variables are taken into account. For a dynamic scalar system and a quadratic performance index, two strategies for the local controllers are proposed.     

Multiagent task allocation in social networks

This paper proposes a new variant of the task allocation problem, where the agents are connected in a social network and tasks arrive at the agents distributed over the network. We show that the complexity of this problem remains NP-complete. Moreover, it is not approximable within some factor. In contrast to this, we develop an efficient greedy algorithm for this problem. Our algorithm is completely distributed, and it assumes that agents have only local knowledge about tasks and resources. We conduct a broad set of experiments to evaluate the performance and scalability of the proposed algorithm in terms of solution quality and computation time. Three different types of networks, namely small-world, random and scale-free networks, are used to represent various social relationships among agents in realistic applications. The results demonstrate that our algorithm works well and also that it scales well to large-scale applications. In addition we consider the same problem in a setting where the agents holding the resources are self-interested. For this, we show how the optimal algorithm can be used to incentivize these agents to be truthful. However, the efficient greedy algorithm cannot be used in a truthful mechanism, therefore an alternative, cluster-based algorithm is proposed and evaluated.     

偏好匹配满意度最大化的众包任务分配

众包任务分配机制对众包任务完成质量起着至关重要的作用,然而现有的分配方法未在稳定性条件下考虑众包用户双边偏好,分配结果的准确性有待提高,并且存在众包用户因不满意当前分配对象而导致众包任务完成质量较低的问题。为此提出一种基于偏好匹配的众包任务分配方法,该方法首先考虑众包任务与工人的双边偏好,根据偏好序计算任务与工人的满意度,生成满意度矩阵;其次,该方法借鉴稳定匹配思想在考虑分配主体偏好的基础上,使分配主体对当前分配对象尽可能满意,以保障分配结果的稳定性;然后,将众包任务分配问题建模为稳定匹配规则下寻找任务最大满意度的优化问题;最后,使用贪心算法对该问题进行求解,得到众包任务分配方案。通过实验验证了该方法的有效性,实验结果表明,该方法提高了分配方案的准确性,并有效减少了无效分配的数量,从而提高了众包任务完成质量。     

基于对策论的团队计算机生成角色任务分配方法

针对带有时间约束的、可以动态加入到环境中的复杂任务,建立了一种基于对策论的任务分配模型,并给出了一种任务分配方法。该方法中计算机生成角色(CGA)根据自身掌握的局部信息进行行为选择,并使用虚拟行动方法确保CGA快速学习到一个严格纯策略Nash平衡。仿真实验结果表明该方法是合理的,能够有效地解决动态任务的分配问题。     

Wasp-like Agents for Distributed Factory Coordination

Agent-based approaches to manufacturing scheduling and control have gained increasing attention in recent years. Such approaches are attractive because they offer increased robustness against the unpredictability of factory operations. But the specification of local coordination policies that give rise to efficient global performance and effectively adapt to changing circumstances remains an interesting challenge. In this paper, we present a new approach to this coordination problem, drawing on various aspects of a computational model of how wasp colonies coordinate individual activities and allocate tasks to meet the collective needs of the nest.We focus specifically on the problem of configuring parallel multi-purpose machines in a factory to best satisfy product demands over time. Wasp-like computational agents that we call routing wasps act as overall machine proxies. These agents use a model of wasp task allocation behavior, coupled with a model of wasp dominance hierarchy formation, to determine which new jobs should be accepted into the machine's queue. If you view our system from a market-oriented perspective, the policies that the routing wasps independently adapt for their respective machines can be likened to policies for deciding when to bid and when not to bid for arriving jobs.We benchmark the performance of our system on the real-world problem of assigning trucks to paint booths in a simulated vehicle paintshop. The objective of this problem is to minimize the number of paint color changes accrued by the system, assuming no a priori knowledge of the color sequence or color distribution of trucks arriving in the system. We demonstrate that our system outperforms the bidding mechanism originally implemented for the problem as well as another related adaptive bidding mechanism.     

Modular nonblocking state feedback control of discrete event systems and its application to dynamic oligopolistic markets

This article addresses a modular state feedback supervisory control problem where two local controllers should achieve a common control objective against another local controller. Each local controller has its own control objective described as a predicate. This article also addresses a nonblocking modular control problem in which a discrete event system controlled by three local controllers tends to reach the common marked states of two local controllers that are, however, prohibited by the third local controller. For a case study, we apply the proposed theory to an oligopolistic market composed of two firms and one government. Two oligopolistic firms have a common objective to maximise their total profit through collusion. However, the government prevents them from engaging in collusion. We show that the modular supervisory control theory presented in this article can be used to solve the problem of ‘how can the firms maximise their total profit against the intervention of government’?     

考虑用户时空行为的众包任务推荐方法

当前的时空众包任务推荐方法大都是针对有奖励约束、全职做众包任务的众包工人,忽略了有兴趣偏好、不受奖励约束完成任务的兴趣型众包工人,如何将众包任务推荐给这些兴趣型工人,是亟待解决的问题。针对此情况,提出考虑兴趣型时空众包工人的时空行为规律和兴趣偏好的推荐方法。引入基尼系数,在数据中筛选出兴趣型时空众包工人的数据,利用地理-社会关系模型的聚类方法对众包任务进行聚类,用高斯分析的马尔可夫模型预测众包工人在下一转移时间点可能到达各个地点的概率,把位于众包工人可能到达地点的任务按概率降序推荐给兴趣型工人。实验结果表明,所提方法有效提高了兴趣型时空众包任务的完成率。     

Integration of task networks and cognitive user models using coloured Petri nets and its application to job design for safety and productivity

Changes of task demands due to unforeseen events and technological changes can cause variations in job design such as modifications to job procedures and task allocation. Failure to adapt to job design variations can lead to human errors that may have severe consequences for system safety. Existing techniques for task modelling cannot adequately model how task networks can be adapted to changing work conditions and task demands. Therefore, there is a need to integrate task networks with cognitive user models that indicate how operators process information, make decisions, or cope with suspended tasks and errors. The work described here presents a tool for integrating task and cognitive models using coloured Petri nets. The cognitive user model comprises two modules of attention management (selective and divided attention), a module of memory management of suspended tasks and a module of work organization. Performance Shaping Factors (e.g., workload, fatigue and mental-tracking load) are calculated at any point in time to take into account the context of work (e.g., competing activities, errors and suspended tasks). Different types of human error can be modelled for rule-based behaviours required in proceduralized work environments. Simulation analysis and formal analysis techniques can be applied to process control tasks to verify job procedures, workload management strategies and task allocation schemes in response to technological changes and unfamiliar events.     

Task allocation for maximizing reliability of distributed computing systems using honeybee mating optimization

This paper deals with the problem of task allocation (i.e., to which processor should each task of an application be assigned) in heterogeneous distributed computing systems with the goal of maximizing the system reliability. The problem of finding an optimal task allocation is known to be NP-hard in the strong sense. We propose a new swarm intelligence technique based on the honeybee mating optimization (HBMO) algorithm for this problem. The HBMO based approach combines the power of simulated annealing, genetic algorithms with a fast problem specific local search heuristic to find the best possible solution within a reasonable computation time. We study the performance of the algorithm over a wide range of parameters such as the number of tasks, the number of processors, the ratio of average communication time to average computation time, and task interaction density of applications. The effectiveness and efficiency of our algorithm are demonstrated by comparing it with recently proposed task allocation algorithms for maximizing system reliability available in the literature.     

Effects of task characteristics on unimanual and bimanual movement times

Fitts' law cannot be used to predict movement times (MTs) of bimanual tasks since no empirical relationships associating task difficulty and bimanual MT have been demonstrated yet. Development of a ‘bimanual task difficulty index’ has been challenged by the complex patterns of coordination involved in simultaneously performing two tasks, one with each hand, under a control system with limited visual and attentional resources. To address this fundamental issue in human motor performance, bimanual object transfers with the left and right hands to targets of various precision requirements and separated by different distances were studied in six healthy subjects. Visual resource allocation during task performance was used to identify ‘primary’ and ‘secondary’ hand movements in bimanual tasks. While the primary movement was similar to a unimanual movement, the secondary MT varied with its own, as well as the contralateral hand's task constraints. These results, which were stable and consistent across six subjects, provide preliminary evidence that visual behaviour, indicating closed-loop control, can be used to systematically derive bimanual MTs.

Practitioner summary: A simple extension of Fitts' law cannot be used to predict movement times (MTs) of bimanual tasks since there is no consensus on the definition of a ‘bimanual task difficulty index’ in the literature. In this paper, we have approached this problem by using visual resource allocation patterns to systematically derive bimanual MTs.     

Optimized Stochastic Policies for Task Allocation in Swarms of Robots

We present a scalable approach to dynamically allocating a swarm of homogeneous robots to multiple tasks, which are to be performed in parallel, following a desired distribution. We employ a decentralized strategy that requires no communication among robots. It is based on the development of a continuous abstraction of the swarm obtained by modeling population fractions and defining the task allocation problem as the selection of rates of robot ingress and egress to and from each task. These rates are used to determine probabilities that define stochastic control policies for individual robots, which, in turn, produce the desired collective behavior. We address the problem of computing rates to achieve fast redistribution of the swarm subject to constraint(s) on switching between tasks at equilibrium. We present several formulations of this optimization problem that vary in the precedence constraints between tasks and in their dependence on the initial robot distribution. We use each formulation to optimize the rates for a scenario with four tasks and compare the resulting control policies using a simulation in which 250 robots redistribute themselves among four buildings to survey the perimeters.