Narrow Results

A distributed computing system (DCS) provides a platform for concurrent execution of tasks consisting of various modules. The problem of task allocation becomes quite difficult to solve when the precedence constraint is considered along with other constraints such as memory, network topology, etc. Various solutions have been proposed, considering one or the other constraint, in the literature. The present work discusses a comprehensive task allocation policy that can promise to provide an optimal solution to the problem. An algorithm, considering the precedence relation among the modules of a task, is proposed for allocation. The algorithm is used to show the allocation for some interconnection topologies and task graphs.

In this paper, we propose a randomized scheduling algorithm on a fully connected homogeneous multiprocessor environment. This is a randomized version of our earlier algorithm in which we used priority of modules that was dependent on the computation and the communication times associated with the modules. First we propose a generalization of our earlier scheduling algorithm with restricted number of clusters to reduce the time complexity. Then we apply randomization to the generalized algorithm and demonstrate its superiority over our previous work. We show the complexity of our proposed algorithm as O(ab |V| (|V|+|E|) log (|V|+|E|)). Here a is the number of randomization steps, and b is a limit on the number of clusters formed. If we use a and b as constants, then this gives a better complexity in comparison with the complexity of our previous algorithm that was O(|V|²(|V|+|E|) log (|V|+|E|)). In comparison with our previous work we get a performance improvement of up to 6.63% and a performance improvement of up to 12.56% when compared with Sarkar's Edge Zeroing algorithm.

The LOCAL(A, B) randomized task scheduling algorithm is proposed for fully connected multiprocessors. It combines two given task scheduling algorithms (A, and B) using local neighborhood search to give a hybrid of the two given algorithms. Objective is to show that such type of hybridization can give much better performance results in terms of parallel execution times. Two task scheduling algorithms are selected: DSC (Dominant Sequence Clustering as algorithm A), and CPPS (Cluster Pair Priority Scheduling as algorithm B) and a hybrid is created (the LOCAL(DSC, CPPS) or simply the LOCAL task scheduling algorithm). The LOCAL task scheduling algorithm has time complexity O(|V||E|(|V |+|E|)), where V is the set of vertices, and E is the set of edges in the task graph. The LOCAL task scheduling algorithm is compared with six other algorithms: CPPS, DCCL (Dynamic Computation Communication Load), DSC, EZ (Edge Zeroing), LC (Linear Clustering), and RDCC (Randomized Dynamic Computation Communication). Performance evaluation of the LOCAL task scheduling algorithm shows that it gives up to 80.47 % improvement of NSL (Normalized Schedule Length) over other algorithms.

In this paper we derive a lower bound for the total communication volume when mapping arbitrary task graphs onto a distributed processor system. For a K processor system this lower bound can be computed with only the K (possibly) largest eigen values of the adjacency matrix of the task graph and the eigen values of the adjacency matrix of the processor graph. We also derive the eigen values of the adjacency matrix of the processor graph for a hypercube multiprocessor and illustrate the concept with a simple example for the two processor case.

A mobile community can be composed of multiple mobile devices through D2D (Device-to-Device) network. In many cases, these mobile devices cannot conveniently connect to the Internet, for various reasons. To overcome this obstacle, one solution is to let the mobile devices cooperate with each other through a D2D-enabled network, forming a mobile community that, as a whole, may be able to autonomously execute the tasks requested by its members. To maximize the overall benefits of mobile communities, this paper proposes a novel task allocation approach, EDTG (Energy-aware and Deadline-constrained Task allocation using Game theory). In mobile communities, energy consumption is responsible for the largest part of the cost. Energy management can lead to performance degradation and even be perceived as a bottleneck, while load balancing between devices can improve service performance and resource utilization to the largest extent. EDTG has considered both the inevitable performance constraints at each device and a method based on the connectivity of graph theory, in order to narrow down the search scope of optimal target mobile devices where requested tasks can be executed. The “Bargaining Game” method is designed and exploited to obtain the final task allocation solution. Final experimental results demonstrate that compared to existing approaches, EDTG ensures high-performance task execution and reaches the goal of maximizing the overall benefits to some extent, by achieving better energy savings and exploiting load balancing between devices.

Automated guided vehicle (AGV) is an important transportation equipment, which is widely used in warehouses and factories. In the scenarios of multi-AGVs application, an efficient AGVs task assignment strategy is beneficial for transportation costs, balance of workload and increasing distribution efficiency. The traditional method usually depends on a powerful scheduling system, which solves the task assignment problem in a regular way. In this paper, we present a decentralized framework of multi-task allocation with attention (MTAA) in deep reinforcement learning, which combines with the methods of task assignment in balance and path planning in cooperation for distribution application. As for task assignment balance, we adopt DNN network to achieve task assignment equilibrium. In multi-AGVs path planning, methods of A3C are embedded in MTAA framework, which are instrumental in improving the stationarity and performance in deep reinforcement learning application. In experiments, we designed two different scenarios under different obstacles to verify the performance of MTAA-A3C and MTAA-DQN methods. The experiments show that the proposed approach has feasibility and effectiveness used in multi-AGVs application.

Fast growing technologies have made pervasive computing elements part of our routine life. These computing elements dissipate a lot of energy, and power optimization is one of the critical design aspects of such systems. In this work an intelligent laboratory automation and resource management system (iLARMS) is proposed, which incorporates power-aware strategies activated in software with hardware support. In the current work, investigations are carried out to observe the energy issues of the application and the processors used. Various software techniques for energy saving are incorporated in the application level and in the processor core level. The hardware implementation of the proposed resource management system is carried out using PIC16F877A and ARM7 LPC2148 microcontrollers and Intel Core 2 Duo processors. An average energy saving of the order of 48.78% was achieved with iLARMS when compared to a conventional resource management system.

Motivated by the study of social insects, we introduce a stochastic model based on interacting particle systems in order to understand the effect of communication on the division of labor. Members of the colony are located on the vertex set of a graph representing a communication network. They are characterized by one of two possible tasks, which they update at a rate equal to the cost of the task they are performing by either defecting by switching to the other task or cooperating by anti-imitating a random neighbor in order to balance the amount of energy spent in each task. We prove that, at least when the probability of defection is small, the division of labor is poor when there is no communication, better when the communication network consists of a complete graph, but optimal on bipartite graphs with bipartite sets of equal size, even when both tasks have very different costs. This shows a non-monotonic relationship between the number of connections in the communication network and how well individuals organize themselves to accomplish both tasks equally.

Emergency incidents increase the uncertainty of supply chain environment, and also make the supply chain vulnerability expose. Creating resilient supply chain is an effective way to overcome the supply chain vulnerability. The supply chain characteristics of self-adaptation and self-coordination are consistent with the self-organization feature of ant colony's labor division. In this paper, a generalized ant colony's labor division model with constraints is provided, which is used to construct the ant colony's labor division model with constraints of resilient supply chain to solve task allocation of resilient supply chains. The simulation principle and algorithm of resilient supply chain are provided based on the proposed model and task allocation of the supply chain is analyzed from the five aspects, that is, task allocation status, supply chain coordination, emergency incidents' impact to task allocation, task allocation rate and the influence of different incidents for task allocation. The simulation results show that, with the proposed model, it is effective to allocate resilient supply chain tasks and has excellent performance, such as faster response and robustness.

The division of labor (DOL) and task allocation (TA) among groups of ants living in a colony is thought to be highly efficient, and key to the robust survival of a colony. A great deal of experimental and theoretical work has been done toward gaining a clear understanding of the evolution of, and underlying mechanisms of these phenomena. Much of this research has utilized mathematical modeling. Here we continue this tradition by developing a mathematical model for a particular aspect of TA, known as age-related repertoire expansion, that has been observed in the minor workers of the ant species Pheidole dentata. In fact, we present a relatively broad mathematical modeling framework based on the dynamics of the frequency with which members of specific age groups carry out distinct tasks. We apply our modeling approach to a specific TA scenario, and compare our theoretical results with experimental data. It is observed that the model predicts perceived behavior, and provides a possible explanation for the aforementioned experimental results.

We develop an abstract model to explore specialization and generalization in task performance by individuals within biological populations. Individuals follow simple rules of increasing and decreasing task propensities that could, for example, be based on learning and forgetting. The model does not explore efficiency per se, but makes the prediction that where behavioural specialization occurs in nature, organisms, are likely to be reaping sufficient benefits from improved handling efficiency to offset the costs of increased search time. A second prediction is that among specialists, there will be a trade-off between stability and responsiveness. The model reveals potential similarities between a wide range of complex biological systems.

A multi-agent system (MAS) is a branch of distributed artificial intelligence, composed of a number of distributed and autonomous agents. In a MAS, effective coordination is essential for autonomous agents to achieve their goals. Any decision based on a foundation of knowledge and reasoning can lead agents into successful cooperation; to achieve the necessary degree of flexibility in coordination, an agent must decide when to coordinate and which coordination mechanism to use. The performance of any MAS depends directly on the decisions made by the agents. The agents must therefore be able to make correct decisions. This paper proposes a decision support module in a distributed MAS that is concerned with two main decisions: the decision needed to allocate a task to specific agent/s and the decision needed to select the appropriate coordination mechanism when agents must coordinate with other agent/s to accomplish a specific task. An algorithm for the task allocation decision maker (TADM) and the coordination mechanism selection decision maker (CMSDM) algorithm are proposed that are based on the granular rough model (GRM). Furthermore, a number of experiments were performed to validate the effectiveness of the proposed algorithms; the efficiency of the proposed algorithms is compared with recent works. The preliminary results demonstrate the efficiency of our algorithms.

In this paper, the cardinality constrained quadratic model for binary quadratic programming is used to model and solve the graph bisection problem as well as its generalization in the form of the task allocation problem with two processors (2-TAP). Balanced graph bisection is an NP-complete problem which partitions a set of nodes in the graph G = (N, E) into two sets with equal cardinality such that a minimal sum of edge weights exists between the nodes in the two separate sets. 2-TAP is graph bisection with the addition of node preference costs in the objective function. We transform the general linear k-TAP model to the cardinality constrained quadratic binary model so that it may be efficiently solved using tabu search with strategic oscillation. On a set of benchmark graph bisections, we improve the best known solution for several problems. Comparison results with the state-of-the-art graph partitioning program METIS, as well as Cplex and Gurobi are presented on a set of randomly generated graphs. This approach is shown to also work well with 2-TAP, comparing favorably to Cplex and Gurobi, providing better solutions in a much shorter time.

Optimal task allocation among the suitably formed robot groups is one of the key issues to be investigated for the smooth operations of multi-robot systems. Considering the complete execution of available tasks, the problem of assigning available resources (robot features) to the tasks is computationally complex, which may further increase if the number of tasks increases. Popularly this problem is known as multi-robot coalition formation (MRCF) problem. Genetic algorithms (GAs) have been found to be quite efficient in solving such complex computational problems. There are several GA-based approaches to solve MRCF problems but none of them have considered the dynamic GA variants. This paper considers immigrants-based GAs viz. random immigrants genetic algorithm (RIGA) and elitism based immigrants genetic algorithm (EIGA) for optimal task allocation in MRCF problem. Further, it reports a novel use of these algorithms making them adaptive with certain modifications in their traditional attributes by adaptively choosing the parameters of genetic operators and terms them as adaptive RIGA (aRIGA) and adaptive EIGA (aEIGA). Extensive simulation experiments are conducted for a comparative performance evaluation with respect to standard genetic algorithm (SGA) using three popular performance metrics. A statistical analysis with the analysis of variance has also been performed. It is demonstrated that RIGA and EIGA produce better solutions than SGA for both fixed and adaptive genetic operators. Among them, EIGA and aEIGA outperform RIGA and aRIGA, respectively.

In practice, we experience low efficiency of search and rescue (SAR) frequently in disaster relief. Here, we will optimize the SAR through agent-based simulation. In the kind of cases described here, rescue teams are characterized by different capabilities, and the tasks often require different capabilities to complete. To this end, a combinatorial auction-based task allocation scheme is used to develop a cooperative rescue plan for the heterogeneous rescue teams. Then, we illustrate the proposed cooperative rescue plan in different scenarios with the case of landslide disaster relief. The simulation results indicate that the combinatorial auction-based cooperative rescue plan would increase victims’ relative survival probability by 13.8–16.3%, increase the ratio of survivors getting rescued by 10.7–12.7%, and decrease the average elapsed time for one site getting rescued by 19.0–26.6%. The proposed rescue plan outperforms the rescue plan based on the F-Max-Sum a little bit. The robustness analysis shows that the proposed rescue plan is relatively reliable on condition that both the search radius and scope of cooperation are larger than thresholds. Furthermore, we have investigated how the number of rescue teams influences the rescue efficiency.

Unmanned Air Vehicle (UAV) teams are anticipated to provide surveillance support through algorithms, software, and automation. It is desirable to have algorithms that compute effective and efficient routes for multiple UAVs across a variety of missions. These algorithms must be realizable, practical, and account for uncertainties. In surveillance missions, UAVs act as mobile wireless communication nodes in a larger, underlying network consisting of targets where information is to be collected and base stations where information is to be delivered. The role of UAVs in these networks has primarily been to maintain or improve connectivity while undervaluing routing efficiency. Moreover, many current routing strategies for UAVs ignore communication constraints even though neglecting communication can lead to suboptimal tour designs. Generating algorithms for autonomous vehicles that work effectively despite these communication restrictions is key for the future of UAV surveillance missions. A solution is offered here based on a variation of the traditional vehicle routing problem and a simple communication model. In this work, the new routing formulation is defined, analyzed, and a heuristic approach is motivated and described. Simulation results show that the heuristic algorithm gives near-optimal results in real time, allowing it to be used for large problem sizes and extended to dynamic scenarios.

This paper proposes a distributed task allocation algorithm based on game theory to solve the complex task allocation optimization problem when UAV clusters carry heterogeneous resources and tasks have heterogeneous demands. Considering the heterogeneity of resources, two pre-processing methods are proposed: one is the grouping algorithm that combines greedy algorithm with simulated annealing algorithm, and the other is the improved K-medoids clustering algorithm based on heterogeneous resources. These pre-process methods, through grouping and clustering, can reduce the complexity of task allocation. The entropy weight method is utilized to prioritize tasks based on multiple metrics. Considering task demands, airborne resources and path cost, a coalition formation game model is established, which is proved to be a potential game. Then a distributed task allocation algorithm based on coalition formation game is designed to address the task allocation problem. Finally, the simulation involving 30 tasks with heterogeneous requirements assigned to 100 UAVs validates the effectiveness of the proposed algorithm, showing that it can achieve good task allocation results with great real-time performance.

Task execution in a multi-agent, multi-task environment often requires allocation of agents to different tasks and cooperation among agents. Agents usually have limited resources that cannot be regenerated, and are heterogeneous in capabilities and available resources. Agent coalition benefits the system because agents can complement each other by taking different functions and hence improve the performance of a task. Good task allocation decision in a dynamic and unpredictable environment must consider overall system optimization across tasks, and the sustainability of the agent society for the future tasks and usage of the resources. In this chapter we present an efficient scheme to solve the real time team/coalition formation problem. Our domain of applications is coalition formation of various Unmanned Aerial Vehicles (UAVs) for cooperative sensing and attack. In this scheme each agent bids the maximum affordable cost for each task. Based on the bidding information and the cost curves of the tasks, the agents are split into groups, one for each task, and cost division among the group members for each task is calculated. This cost sharing scheme provably guarantees the stability in cost division within each coalition in terms of the core in game theory, therefore achieves good sustainability of the agent society with balanced resource depletions across agents. Simulation results show that, under most conditions, our scheme greatly increases the total utility of the system compared with the traditional heuristics.

In this chapter a method for assigning unmanned aerial vehicle agents to targets through the use of preplanned vehicle tours is presented. Assignments are based on multi-target tours that consider the spread of the targets and the sensor capabilities of the vehicles. In this way, the individual agents and the team as a whole make better use of team resources and improve team cooperation. Planning and assignments are accomplished in reasonable computational time through the use of heuristics to reduce the problem size.