# Human-Centered Dynamic Service Scheduling Approach in Multi-Agent Environments
## 2 Related Work  
Task scheduling is important for the effective service coordination of multiple service robots. So far, multi-agent task scheduling has been mainly studied in industrial robots, as multiple agents introduce parallel implementation into the workflow enabling tightly organized executions and thus promote efficiency and minimal cycle times (see, e.g., [7; 9; 11; 12]). Many studies on industrial robots have only considered the presence of homogeneous agents [11] because industrial robots operate in a specific setting (e.g., assembly lines [7; 8; 9; 13; 14] and warehouse operations) to maximize productivity and efficiency. However, service robots have diverse forms, functions, and abilities [4; 10]. Even if the same task is presented, the time and prerequisites required to complete the task vary depending on the type of robot responsible. The main purpose of a service robot is to satisfy service requests of a user. Therefore, it is important to properly incorporate agent heterogeneous variables, such as the ability of each agent and duration of task scheduling. To achieve this, first, a given task must be modeled to recognize how the entire task is performed in terms of task component relationships and agent dependencies. The task model describes resources, task sequences, and procedural knowledge of tasks [15]. With an appropriate task model, agent heterogeneity can be introduced by mapping agent variables to each task component. A variety of useful task-modeling tools are available for designing and modeling specific processes. Many scheduling methods utilize precedence relationships [16; 17; 18], temporal constraint networks [19], hierarchical task decompositions (such as AND/OR trees [7; 9; 20]), and Petri nets [9; 12], especially because they directly encode parallel implementations. Some studies considered individual agent capabilities and obtained the final schedule based on capability indicators which evaluate the extent to which an agent is suitable for a specific execution [13; 16]. The decision-making algorithms are often based on a multi-criteria approach using a cost function. Frequently used optimization methods for selecting the optimal schedule include tree search algorithms [7], genetic algorithms [17; 21], and mixed-integer linear programming [18]. Ref. [7] proposed a hierarchical framework and used an A* graph search algorithm to generate an optimal task sequence for agents in human-robot assembly. Ref. [18] found a final schedule using variants of mixed-integer linear programming in an optimization framework that generates task assignments and schedules for a human-robot team to improve both time and ergonomics. However, these studies do not consider system variability but primarily pursue optimization regarding ergonomics or cost-effectiveness. They lead to fixed schedules and do not allow flexibility for spontaneous decisions. Dynamic task allocation for heterogeneous agents makes it possible to cope with systemic inconsistencies better than a single fixed schedule. Various methods have been proposed to estimate the duration time of robots (e.g., methods-time measurement strategy [14; 22]). More recently, [8] used a directed acyclic graph to represent the dependency relationship between tasks and introduced a delay-predicting strategy that predicts human duration and adjusts the robots' schedules accordingly. Similarly, [PERSON]. [9; 20] applied an AND/OR tree to specify all asymmetric actions that an agent can perform in a single graph to enable just-in-time rescheduling of the assembly process according to agent volatility and robotic failures. [PERSON]. [20] suggested an online perception-simulation planning framework to dynamically allocate tasks to robots or humans by always monitoring the manufacturing process. Ref. [12] defined time Petri nets for specific actions or part transports to handle multiple executions. The proposed adaptive scheduling scheme predicts the future evolution of a system based on the agent's previous performance.