Social-welfare based task allocation for multi-robot systems with resource constraints

This paper aims to propose a distributed task allocation algorithm for a team of robots that have constraints on energy resources and operate in an unknown dynamic environment. The objective of the allocation is to maximize task completion ratio while minimizing resource usage. The approach we propose is inspired by the social welfare in economics that helps extend the combined operational lifetime of the team by balancing resource consumptions among robots. This social welfare based task allocation method positions a robot team appropriately in preparedness for dynamic future events and enables to achieve the objectives of the system flexibly depending on the application context. Our simulation-based experiments show that the proposed algorithm outperforms a typical market-based approach in various scenarios.     

Decentralized task allocation for surveillance systems with critical tasks

This paper considers the problem of assigning a set of tasks to a set of heterogeneous agents under the additional assumptions that some tasks must be necessarily allocated and therefore are critical for the assignment problem, and that each agent can execute a limited number of tasks. In order to solve this problem in a decentralized way (i.e., without any form of central supervision), we develop an extension of an algorithm proposed in the recent literature. After analyzing convergence and communication requirement of the algorithm, a set of numerical simulations is provided to confirm the effectiveness of the proposed approach.     

满足偏序约束的在线调度

具备偏序关系的实时调度要求调度算法产生的执行序列既要满足任务的实时约束,又要满足任务间执行的偏序约束。基于并行拓扑排序,提出一种新的在线调度算法,该算法通过同时考察任务间执行的串行性和并行性来进行优先级设置,能够处理释放时间任意的任务集。给出该算法的原理和设计,并通过示例分析和比较对算法进行验证。     

考虑时序约束的多智能体协同任务分配

研究多智能体系统的多目标多任务分配问题, 考虑任务之间的时序关系, 建立分布式任务分配模型. 扩展了一致性包算法(CBBA), 按优先级将目标任务归入不同层级, 各智能体在构建任务包和任务路径时, 只将分配过高阶段任务的目标添加至相应的任务包和任务路径中, 从而保证目标任务时序约束的同时, 保持了CBBA算法的特性. 与多任务分配问题经典算法的比对实验表明, 所提出的改进算法求解结果稳定可靠, 运行时间优于经典算法.

     

Dynamic multi-robot task allocation under uncertainty and temporal constraints

Autonomous Robots - We consider the problem of dynamically allocating tasks to multiple agents under time window constraints and task completion uncertainty. Our objective is to minimize the number...     

Online scheduling on batching machines to minimise the total weighted completion time of jobs with precedence constraints and identical processing times

This article studies online scheduling of equal length jobs with precedence constraints on m parallel batching machines. The jobs arrive over time. The objective is to minimise the total weighted completion time of jobs. Denote the size of each batch by b with b?=?∞ in the unbounded batching and b? m , where ρ _m is the positive solution of ρ ^m+1???ρ?=?1. The algorithm is also best possible when the jobs have identical weights. For the bounded batching version with identical weights of jobs, we provide an online algorithm with a competitive ratio of 2.     

Decentral task allocation for industrial AGV-systems with resource constraints

Automated Guided Vehicles (AGVs) form a large and important part of the logistics transportation systems in today's industry and are widely used, especially in Europe. Today's AGV-systems offered by global manufacturers almost all operate under some form of centralized control where a single central controller coordinates the entire fleet of AGVs. There is a trend towards decentralized control of these systems where AGVs make individual decisions that promote the flexibility, robustness and scalability of transport. However, its practical implementation seems to be in its infancy. In addition to the lack of practical implementation of decentralized control in industrial AGV-systems, we have observed a research gap in intelligent resource management of AGV-systems, which we have tried to address in previous work by proposing a more intelligent resource management approach. In this paper, we have addressed both the perceived lack of practical decentralized AGV control and the lack of intelligent resource management by proposing a decentralized task allocation algorithm based on sequential single-item auctions, taking into account resource constraints, and in which our intelligent resource management approach from previous work is introduced. We have benchmarked our new approach to a genetic algorithm-based task-allocation solver that uses “threshold-100”-charging as a resource management strategy. The result of the proposal is a decentralized task-allocation architecture under resource constraints that could be used in current AGV-systems to add more decentralized features to the fleet.     

具有优先链约束的网格作业多资源调度问题

网格计算是网络并行计算的发展新趋势,网格系统中的分布式资源管理和调度一直是研究的热点和难点。对于网格应用作业的多资源调度问题,一个网格作业往往要分成多步骤进行,每个步骤都需要占用多个资源。首先将该问题抽象为典型的多处理机任务调度模型P_m|fix,p=1,chain|C_max,即在m个处理机系统中调度n个多处理机任务,每个任务指派到所需一组处理机上不可剥夺地执行,而且每个任务都需要一个单位的处理时间,并根据优先关系形成链约束。该问题被证明为NP难问题。利用宽度优先技术和首次满足方法,构建了几个多项式时间近似算法,并通过模拟实验分析算法性能,实验结果显示算法是实用的。     

On a parallel machine scheduling problem with precedence constraints

We characterize a nontrivial special case with a polynomial-time algorithm for a well-known parallel machine scheduling problem with precedence constraints, with a fixed number of machines, and with tasks of unit length. The special case is related to instances with given maximum path length and maximum degree of the task precedence graph. The method is based on the observation that the number of tasks is either small and bounded by a constant depending on the maximum path length and maximum degree, or alternatively, the number of tasks is large, giving a “dense” schedule.     

时空特性约束下的数据挖掘隐私保护方法

在隐私保护数据挖掘的研究中,隐私数据的时间特性以及空间特性是历来研究中常常被忽视的。将数据的安全级与时间性、空间性相结合,引入了数据安全级的时效性及空效性,然后采用层次概化方法进行数据隐私保护处理,并提出了基于时空特性的隐私保护关联规则挖掘算法。最后通过实验对算法的信息损失度、执行时间、算法效能等性能进行了分析和验证。     

Dynamic task allocation for multi-robot search and retrieval tasks

Many application domains require search and retrieval, which is also known in the robotic domain as foraging. For example, in a search and rescue domain, a disaster area needs to be explored and transportation of survivors to a safe area needs to be arranged. Performing such a search and retrieval task by more than one robot increases performance if they are able to distribute their workload efficiently and evenly. In this work, we study the Multi-Robot Task Allocation (MRTA) problem in the search and retrieval domain, where a team of robots is required to cooperatively search for targets of interest in an environment and also retrieve them back to a home base. In comparison with typical foraging tasks, we look at a more general search and retrieval task in which the targets are distinguished with various types, and task allocation also requires taking into account temporal constraints on the team goal. As usual, robots have no prior knowledge about the location of targets in the environment but in addition they need to deliver targets to the home base in a specific order according to their types, which significantly increases the complexity of a foraging problem. We first use a graph-based model to analyse the search and retrieval problem and the dynamics of exploration and retrieval within a cooperative team. We then proceed to present an extended auction-based approach, as well as a prediction approach. The essential difference between these two approaches is that the task allocation and execution procedures in the auction approach are running in parallel, whereas a robot in the prediction approach only needs to choose a task to perform when it has no thing to do. The auction approach uses a winner determination mechanism to allocate tasks to each robot, whereas the robots in the prediction approach implicitly coordinate their activities by team reasoning that leads to consensuses about task allocation. We use the Blocks World for Teams (BW4T) simulator to evaluate the two approaches in our experimental study.     

Dynamic scheduling of real-time tasks under precedence constraints

While scheduling theory has been developed over a long period of time, it is important to note that most results concern problems with static characteristics. However, a real-time system is dynamic and requires on-line and adaptive scheduling strategies. So, an important aspect of real-time systems research is to devise methods flexible enough to react to a dynamic change of processor load and to attempt to schedule all the tasks judiciously.In this paper, we are particularly concerned with the problem of scheduling tasks which are of two kinds: periodic and sporadic, on a monoprocessor machine. Periodic tasks are independent, run cyclically and their characteristics are known in advance. In addition, we allow for the unpredictable occurrence of aperiodic task groups, with timing and precedence constraints. Clearly, the main problem is to devise a schedulability test that makes it possible to decide whether a new occurring group can be accepted, without upsetting the tight timing behavior requirements.We present an optimal acceptance test which returns a decision on the basis of the current state of processor load and by considering tasks to be scheduled according to the well known preemptive algorithm Earliest Deadline. The acceptance algorithm and a complexity analysis are presented.     

包含时间约束的作战任务建模与验证方法

制定作战计划时往往需要考虑作战任务的时间约束问题。目前对作战任务的时间约束分析方法都存在约束类型少、验证方法适用范围小等问题。为此提出基于业务流的作战任务时间约束建模方法,构建了作战任务流模型并用以描述作战任务的相对和绝对时间约束。提出了作战任务的时间约束形式化验证方法,设计了作战任务模型到NuSMV语言的转换算法,并基于时序逻辑给出了作战任务的基本时间约束描述方法。最后以登岛作战任务为例,验证了其相对约束和绝对约束的部分性质,并根据反馈结果对模型进行了修正。     

基于效用函数的多机器人系统任务分配

目前所采用的多机器人系统任务分配方法大多都忽略了任务分配的解质量问题。从定量的角度出发,提出了一种基于效用函数的多机器人系统任务分配策略,在机器人能力向量和子任务要求的能力向量基础上,建立了效用函数的数学模型,根据效用函数大小进行任务分配。仿真实验在足球机器人仿真比赛平台上进行,结果表明该任务分配算法对异构多机器人系统合作具有很好的通用性,且算法快速简单,能够实现任务到机器人的最优映射。     

On scheduling tasks with exponential service times and in-tree precedence constraints

Summary In this paper we extend the work of Chandy and Reynolds in which they considered the problem of scheduling tasks on two identical processors. The processing times of the tasks are independent, identically distributed exponential random variables. The tasks are subject to in-tree precedence constraints. Chandy and Reynolds have shown that the expected value of the makespan is minimized if and only if the scheduling policy is Highest-Level-First (HLF). We extend their result by showing that a policy maximizes the probability that all tasks finish by some time t0 if and only if the policy is HLF. Additionally, we show that a policy maximizes the probability that the sum of the finishing times of all the tasks is less than some value s0 if and only if the policy is HLF.This work has been partially supported by a Lady Davis Fellowship at the Technion, Haifa Israel; by the Research Institute for Advanced Computer Science at the NASA Ames Research Center, Moffett Field CA; and by NSF Grant MCS 80-04257.     

信息系统中业务规则与约束的时态化研究

在OCL和ECA规则的基础上,通过对业务对象与ECA规则的时态化关系的分析,提出了业务规则与约束的一种时态化扩展建模方法,该方法引入了时态化算子和时间区间等概念来实现对时态化对象和属性的历史信息的引用和时态化建模。     

A scheduling method for multi-robot assembly of aircraft structures with soft task precedence constraints

The use of multiple cooperating robotic manipulators to assemble large aircraft structures entails the scheduling of many discrete tasks such as drilling holes and installing fasteners. Since the tasks have different tool requirements, it is desirable to minimize tool changes that incur significant time costs. We approach this problem as a multi-robot task allocation problem with precedence constraints, where the constraints are loosely enforced in terms of prioritizing the tasks to avoid unnecessary tool changes. To avoid the computational burden of searching over all possible task prioritization options, our main contribution is to develop a two-step, data-driven approach to automatically select suitable precedence relations. The first step is to adapt an iterative auction-based method to encode the precedence relations using scheduling heuristics. The second step is to develop a robust machine learning method to generate policies for automatically selecting efficient scheduling heuristics based on the problem characteristics. Experimental results show that the top performing heuristics yield schedules that are more efficient than those of a baseline partition-based scheduler by almost 17%–19%, depending on the robot failure profiles. The learned policies are also able to select heuristics that perform better than greedy selection without incurring additional computational costs.     

多机器人系统任务分配的研究进展

多机器人系统任务分配是机器人研究领域一个关键的研究课题。从多机器人任务分配分类及问题描述、多机器人任务分配的研究动态等方面对多机器人任务分配进行了综述,并根据近期文献探讨了多机器人系统任务分配需要解决的若干重要问题。     

基于多目标全局约束的任务分配和调度算法

针对嵌入式系统中大多数任务执行算法不考虑目标成本问题,提出了一种基于多目标全局约束的任务分配和调度算法。算法使用约束逻辑编程来对任务执行资源如处理单元、通信设备以及代码和数据存储量的使用进行多目标全局约束。算法假设ROM和RAM分别用于代码存储和数据存储,算法还考虑数据在数据存储器中的位置。实验结果表明,尽管在多个约束条件下,提出的任务分配和调度算法无论在代码存储和数据存储量使用方面,还是在对任务有效求解方面都能取得比普遍采用的贪婪调度算法更好的结果。