CPS-Based Smart Warehouse for Industry 4.0: A Survey of the Underlying Technologies <s> Multi-Robot Task Scheduling <s> Auction and market-based mechanisms are among the most popular methods for distributed task allocation in multirobot systems. Most of these mechanisms were designed in a heuristic way and analysis of the quality of the resulting assignment solution is rare. This paper presents a new market-based multi-robot task allocation algorithm that produces optimal assignments. Rather than adopting a buyer’s “selfish” bidding perspective as in previous auction/market-based approaches, the proposed method approaches auctioning from a merchant’s point of view, producing a pricing policy that responds to cliques of customers. The algorithm uses price escalation to clear a market of all its goods, producing a state of equilibrium that satisfies both the merchant and customers. The proposed method can be used as a general assignment algorithm as it has a time complexity (O(nlgn)) close to the fastest state-of-the-art algorithms (O(n)) but is extremely easy to implement. As in previous research, the economic model reflects the distributed nature of markets inherently: in this paper it leads directly to a decentralized method ideally suited for distributed multi-robot systems. <s> BIB001 </s> CPS-Based Smart Warehouse for Industry 4.0: A Survey of the Underlying Technologies <s> Multi-Robot Task Scheduling <s> National Science Foundation (U.S.). Graduate Research Fellowship Program (grant number 2388357) <s> BIB002 </s> CPS-Based Smart Warehouse for Industry 4.0: A Survey of the Underlying Technologies <s> Multi-Robot Task Scheduling <s> Task allocation is an important topic in multiagent and multi-robot teams. In recent years, there has been much research on the use of auction-based methods to provide a distributed approach to task allocation. Team members bid on tasks based on local information, and the allocation is based on these bids. The focus of prior work has been on optimal allocations and has established that auction-based methods perform well in comparison with optimal methods, with the advantage of scaling better. Here we take a different approach, comparing auction-based methods not on the optimality of the allocation, but on the efficient execution of the allocated tasks. This approach factors in aspects such as the utilisation of the team members and the degree to which they interfere with each others' progress, giving a fuller picture of the practical use of auction-based methods. <s> BIB003 </s> CPS-Based Smart Warehouse for Industry 4.0: A Survey of the Underlying Technologies <s> Multi-Robot Task Scheduling <s> We present a study of self-organized multi-robot task-allocation, examining performance under local and centralized communication strategies. The results extend our current understanding of the effects of communication by providing evidence that local strategies can improve system performance over centralized strategies, in terms of total task throughput as well as reduced communication overheads. The framework employed is the attractive field model, a generic model of self-organized division of labour derived from observations of ant, human and robot social systems. The framework provides sufficient abstraction to accommodate both communication strategies. Each of the studies used 16 e-puck robots in a simplified manufacturing environment where sensing and communication was realized using camera-based overhead tracking and centralized communication. In terms of task throughput, communication overhead and energy efficiency, the experimental results show that systems with restricted access to information perform better than systems with free flow of information. This suggests a potential paradigm shift where, for self-organizing systems, diminishing access to information renders a system more efficient. <s> BIB004 </s> CPS-Based Smart Warehouse for Industry 4.0: A Survey of the Underlying Technologies <s> Multi-Robot Task Scheduling <s> In this paper, we address coordination within a team of cooperative autonomous robots that need to accomplish a common goal. Our survey of the vast literature on the subject highlights two directions to further improve the performance of a multi-robot team. In particular, in a dynamic environment, coordination needs to be adapted to the different situations at hand (for example, when there is a dramatic loss of performance due to unreliable communication network). To this end, we contribute a novel approach for coordinating robots. Such an approach allows a robotic team to exploit environmental knowledge to adapt to various circumstances encountered, enhancing its overall performance. This result is achieved by dynamically adapting the underlying task assignment and distributed world representation, based on the current state of the environment. We demonstrate the effectiveness of our coordination system by applying it to the problem of locating a moving, non-adversarial target. In particular, we report on experiments carried out with a team of humanoid robots in a soccer scenario and a team of mobile bases in an office environment. <s> BIB005 </s> CPS-Based Smart Warehouse for Industry 4.0: A Survey of the Underlying Technologies <s> Multi-Robot Task Scheduling <s> Intending to mimic the operating mechanism of biological neural systems, a self organizing map-based approach to task assignment of a swarm of robots in 3-D dynamic environments is proposed in this paper. This approach integrates the advantages and characteristics of biological neural systems. It is capable of dynamically planning the paths of a swarm of robots in 3-D environments under uncertain situations, such as when some robots are presented in or broken down or when more than one robot is needed for some special task locations. A Bezier path optimizing algorithm and a parameter adjusting algorithm are integrated in this paper. It is capable of reducing the complexity of the robot navigation control and limiting the number of convergence iterations. The simulation results with different environments demonstrate the effectiveness of the proposed approach. <s> BIB006 </s> CPS-Based Smart Warehouse for Industry 4.0: A Survey of the Underlying Technologies <s> Multi-Robot Task Scheduling <s> Multi-robot patrolling is a key feature for various applications related to surveillance and security, and it has been studied from several different perspectives, ranging from techniques that devise optimal off-line strategies to implemented systems. However, still few approaches consider on-line decision techniques that can cope with uncertainty and non-determinism in robot behaviors. In this article we address on-line coordination, by casting the multi-robot patrolling problem as a task assignment problem and proposing two solution techniques: DTA-Greedy, which is a baseline greedy approach, and DTAP, which is based on sequential single-item auctions. We evaluate the performance of our system in a realistic simulation environment (built with ROS and stage) as well as on real robotic platforms. In particular, in the simulated environment we compare our task assignment approaches with previous off-line and on-line methods. Our results confirm that on-line coordination approaches improve the performance of the multi-robot patrolling system in real environments, and that coordination approaches that employ more informed coordination protocols (e.g., DTAP) achieve better performances with respect to state-of-the-art online approaches (e.g., SEBS) in scenarios where interferences among robots are likely to occur. Moreover, the deployment on real platforms (three Turtlebots in an office environment) shows that our on-line approaches can successfully coordinate the robots achieving good patrolling behaviors when facing typical uncertainty and noise (e.g., localization and navigation errors) associated to real platforms. <s> BIB007 </s> CPS-Based Smart Warehouse for Industry 4.0: A Survey of the Underlying Technologies <s> Multi-Robot Task Scheduling <s> Multi-/many-core systems are envisioned to satisfy the ever-increasing performance requirements of complex applications in various domains such as embedded and high-performance computing. Such systems need to cater to increasingly dynamic workloads, requiring efficient dynamic resource allocation strategies to satisfy hard or soft real-time constraints. This article provides an extensive survey of hard and soft real-time dynamic resource allocation strategies proposed since the mid-1990s and highlights the emerging trends for multi-/many-core systems. The survey covers a taxonomy of the resource allocation strategies and considers their various optimization objectives, which have been used to provide comprehensive comparison. The strategies employ various principles, such as market and biological concepts, to perform the optimizations. The trend followed by the resource allocation strategies, open research challenges, and likely emerging research directions have also been provided. <s> BIB008 </s> CPS-Based Smart Warehouse for Industry 4.0: A Survey of the Underlying Technologies <s> Multi-Robot Task Scheduling <s> We propose a method for real-time trajectory generation with applications in aerial videography. Taking framing objectives, such as position of targets in the image plane, as input, our method solves for robot trajectories and gimbal controls automatically and adapts plans in real time due to changes in the environment. We contribute a real-time receding horizon planner that autonomously records scenes with moving targets, while optimizing for visibility under occlusion and ensuring collision-free trajectories. A modular cost function, based on the reprojection error of targets, is proposed that allows for flexibility and artistic freedom and is well behaved under numerical optimization. We formulate the minimization problem under constraints as a finite horizon optimal control problem that fulfills aesthetic objectives, adheres to nonlinear model constraints of the filming robot and collision constraints with static and dynamic obstacles and can be solved in real time. We demonstrate the robustness and efficiency of the method with a number of challenging shots filmed in dynamic environments including those with moving obstacles and shots with multiple targets to be filmed simultaneously. <s> BIB009
Many multi-robot tasks involve multiple jobs executed on different robots with specified end-to-end deadline requirements. These tasks may be deployed to an MRS at any time and on any robot during run-time. For example, a new package delivery task may be deployed on an MRS while a persistent monitoring task is in process. As a result, resource competitions among these tasks can happen on any robot and is unpredictable. Furthermore, an individual robot often does not have full information about the working status of the other robots since the robots form a distributed system. Therefore, scheduling decisions made by individual robots about their local job execution orders may not be optimal for the tasks to which the jobs belong concerning meeting the tasks' end-to-end deadlines. Task scheduling in distributed systems has been proven to be NP-hard (non-deterministic polynomial-time hard)  , and the research community has been developing various heuristic strategies to schedule tasks for MRS. We categorize the existing approaches according to three metrics, namely criticality, resource management, and technique as shown in Figure 2 . The dimension of "scheduler" represents the member who carries out scheduling. The scheduling can be performed in a centralized, semi-distributed, or fully-distributed way. The scheduling is performed in a "centralized" fashion if a central platform decomposes the task into multiple subtasks and allocate the subtasks to the robots. In this approach, the robots are only responsible for receiving the result subtasks from the central platform and performs them. "Fully-distributed" scheduler means the robots themselves serve as the scheduler. In this fashion, all the robots negotiate with each other and play equal roles. The "semi-distributed" scheduling approach combines the centralized and fully-distributed approaches. The whole MRS is divided into several clusters. Each cluster of robots schedule its tasks independently, and a central platform is responsible for assigning tasks to the clusters. Concerning criticality, different multi-robot applications have a different degree of criticality. According to the criticality of the applications, multi-robot task scheduling can be divided into soft real-time (SRT) task scheduling and hard real-time (HRT) task scheduling. For those safety-critical applications, e.g., human-assisted robotic manipulation and operating medical equipment, HRT is required since human beings are involved, and safety issues pop up. For other applications, such as package delivery, missing deadlines can be tolerated, and soft real-time (SRT) is preferred. SRT task scheduling is performed in a best-effort way. There are various techniques for multi-robot task scheduling such as market-based BIB001 BIB003 , bio-inspired BIB006 BIB004 , and hybrid approaches BIB002 . In the market-based approach, the task is divided into a set of subtasks and the robots bid to carry out these subtasks. Since the robots are assigned limited amounts of money, they have to negotiate with each other to maximize their self-interests. The market-based approach is widely used for multi-robot searching BIB005 and patrolling BIB007 . Bio-inspired task scheduling approaches apply the observed rules from nature to solving scheduling problems. For example, mimicking the birds flock for multi-robot pattern formation has been a success story  . Generally speaking, market-based and bio-inspired approaches are used for SRT multi-robot task scheduling. When it comes to HRT task scheduling, hybrid methods are always employed. The hybrid approaches utilize design-time computations to identify a timing constraint satisfying allocation at runtime BIB008 BIB009 .