Approaching flexible production with planning methods

The Planning and Dispatching layers implements a centralized control strategy for multi-agent system in a dynamic domain. It is based on three main components: (1) a Goal Reasoner (GR), (2) a Planner (P), and (3) a Dispatching and Monitoring Module (DM). In Fig. 2, the interaction between the components is shown. The Dispatching and Monitoring module plays the role of the main controller that invokes GR and and P as well as executes the obtained plan. The plan execution is constantly monitored for issues that may require a regeneration of goals or plans, e.g. failed actions or deadline violations.

The planner is responsible for finding a plan for the goals selected by GR while minimizing its makespawn. Planning is performed using the temporal planner TFD [3] that offers numerous PDDL 2.1 features [4]. We chose temporal planning for its ability to handle temporal deadlines and coordinate multiple agents. The downside is the high planning costs. In order to address this issue for the RCLL domain, we abstracted the domain model and introduced an online goal selection. The domain is modeled in PDDL by representing the two main interactions with a station as abstract action: \(\mathit{get}\) and \(\mathit{delivery}\) only. The former retrieves a workpiece from a station after processing, while the latter delivers the workpiece to a station for processing. In the RCLL robots can not carry more than one piece at a time, so every \(\mathit{get}\circ\mathit{delivery}\) action is interleaved with a \(\mathit{move}\) action. For this reason, both \(\mathit{get}\) and \(\mathit{delivered}\) already include costs and constraints related to the previous \(\mathit{move}\) action: a \(\mathit{get}\) action actually models a \(\mathit{move}\_\mathit{and}\_\mathit{get}\) macro-action. This significally speed-up the planning process. The result of planning is a temporal plan, which is represented by the schedule \(\sigma\), formed by triples \(\langle a,t_{a},d_{a}\rangle\), where \(a\) is an action, \(t_{a}\) is the time when the action \(a\) needs to be started, and \(d_{a}\) is the duration of the action. Table 1 shows a temporal plan to build and deliver a simple product in the RCLL.

This representation poorly supports action dispatching, since it is not easy to determine how delays in the execution of an action, affect the other triples of the plan. To address this, we represent the plan as a temporal graph (Simple Temporal Network), which encodes the temporal dependencies and the partial order of actions, without constraining the start of actions to specific time points. An accurate estimation of action durations is crucial for appropriate planning and monitoring plan execution. The interaction time of a robot with a station has been estimated empirically. Regarding the traveling time, we precompute a matrix containing all the estimated costs for traveling between each pair of locations. Since the same path finding algorithm is used as in the robot’s navigation skill, the estimated times are close to the real ones. To make the estimation even more precise, we are also considering orientation costs at the start and at the end of each movement action. By adopting this procedure we achieve an accurate estimation of actions duration that is incorporated into the PDDL domain.

As we are interested in dynamic domains, planning needs to be fast, to be able to react to changes and new opportunities in the environment in time. For this reason, GR selects the most rewarding set of goals P the planner may be able to obtain a plan for with a given time budget (e.g., 1 min). For RCLL a single goal is an individual order. In general, planning for all received orders is not possible within a reasonable time window. Thus, we follow the idea of partial satisfactory planning [11]. GR solves a relaxed version of the domain, assuming that each goal can be achieved by a single agent individually, ignoring cooperation or resource management. Giving this setting, the goals selection is formulated as a simple task allocation problem with an overall deadline. We employ the ASP solver CLINGO [5] to compute this optimization task, which consists of finding a subset of goals such that the awarded points are maximized within the given constraints. A drawback of the goal selection heuristic is that the solution of the relaxed problem may be too optimistic. Thus, the planner may not able to find a plan achieving all selected goals while respecting the given deadlines. To mitigate this we exploit parallel planning over multiple sets of goals. The sets are the original set plus sets obtained by either dropping goals or replacing goals with less complex ones. For each of this set, a planning thread is ran for 1 minute. The rational behind this approach is that in general it is more likely to find a feasible plan for simplified goal sets with a bounded time budget. Among the returned feasible plans, we select and dispatch the one with the highest reward.

The Dispatching and Monitoring module dispatches the actions of the obtained plan in time, monitors proper execution (in terms of state and time), and initiates replanning if necessary. These three events may trigger replanning: (1) failed skill execution, (2) successful execution of the actual plan, (3) impossibility to achieve a goal in time.

In this work, we use a dedicated approach to check the temporal constraint of the temporal network reprenting the plan, in order to allow an earlier detection of deadline violations. We use two types of edges: (1) action duration edges \([d_{a},d_{a}]\) between start and end of the action \(a\), and (2) partial order edges \([0,+\infty)\) between the end of an action and the start of the following one. Nodes corresponding to start actions are dispatched by sending the action to the robot for execution, while end nodes are dispatched when a feedback for the successful execution of the corresponding action is received. The partial order encoded through the edges is ensured by the dispatching. Unfortunately, it can not be expected that the execution in the real world perfectly respects the temporal constraint \([d_{a},d_{a}]\) (interval between min and max time). The approach presented in [1] propagates the detected delay by fixing the execution times of already executed actions and updating the remaining deadlines using constraint propagation. In our approach, violations of such edges are tolerated, since our early deadline detection strategy immediately recognizes if such delays will cause a deadline violation in the future. Thus, we use the opposite approach, propagating back the deadlines from the goal nodes to the rest of the network, labeling each node with a relative deadline \(\mathit{rdl}(x)\). This represents the latest time point we can dispatch that node without violating the deadline \(x\). Starting from the \(\mathit{goal}\) vertices, we calculate the relative deadlines \(\mathit{rdl}\) of each vertex by traversing the edges in the opposite direction, subtracting the lower bound of the edge at each step. If there are more paths from a normal vertex to a \(\mathit{goal}\) vertex, we keep the more restrictive relative deadline. Every time a node is dispatched, we check if all its relative deadlines are respected, otherwise we trigger replanning. In Fig. 3 a partial result of this approach applied to a temporal graph is shown.

In order to ensure reliable execution of tasks, a modification was made to the middle layer, which now utilizes Behavior Trees [2] for action execution. Each dispatched action is divided into smaller, atomic low-level skills, such as moving the gripper or placing an object on a station. This allows for the decomposition of each action into executable skills. The execution of routines is represented as a tree structure composed of different types of nodes. Control nodes are used to alter the program flow, while execution nodes initiate actions. These nodes exchange data through blackboards implemented by the Behavior Tree library. ROS action clients are used to trigger action on the PLC, the robot platform or to gather sensing information. The high-level receives notifications about the execution outcomes. If a tree fails to execute, control is returned to the high-level, and the robot waits for the next action to be assigned. The key advantage of this approach is the user-friendly nature of behavior trees, while still enabling the encoding of complex behaviors.

One notable improvement over the previous system is the introduction of on-the-fly alignment for the robot’s interaction with machines. In the previous system, the robot would first navigate towards the closest zone on the correct side of the machine, followed by a separate alignment step with the conveyor. In contrast, the updated system enables the robots to initiate alignment immediately upon detecting the presence of a machine while moving towards the designated zone. For its implementation, a multiplexer-based mechanism is employed, which switches between the velocity provided by the navigation planner to the robot platform and a feedback controller utilized for precise alignments. A proportional controller was chosen as control algorithm. We can reach reference tracking and a low settling time due to the high gain of the controller and a velocity constraint. The velocity constraint is calculated based on the maximum acceptable error divergence (2 cm) and the acceleration of the move base (3 m/s²). The error calculation for the controller determines the signal for selecting the multiplexer values. Once a threshold is reached, indicating that the robot can safely align with the machine, the multiplexer switches from the move base velocity to the alignment velocity. This on-the-fly alignment approach significantly reduces skill transition delays by minimizing network interactions and tree initializations.