开源AGV调度系统OpenTCS中的任务分派器(dispatcher)详解

OpenTCS中的任务分派器dispatcher详解

1. 引言
2. 任务分派器(dispatcher)
- 2.1 默认的停车位置选择
- 2.2 可选停车位置属性
- 2.3 默认的充电位置选择
- 2.4 即时运输订单分配
3. 默认任务分派器的配置项
4. 参考资料与源码

1. 引言

openTCS是一项著名的开源运输控制系统，我在之前的一篇文章
开源AGV调度系统 OpenTCS 5.4 开发环境配置与编译运行中对该系统也做了初步介绍，该项研究工作丢了快三年了，由于发现还有不少感兴趣的读者，因此，我想继续撰写系列文章对该系统进行详解。
在这里插入图片描述

2. 任务分派器(dispatcher)

openTCS中默认的任务分派器（Default dispatcher）是openTCS内置的重要策略模块，当然也是允许用户自定义和替换的。
任务分派器(dispatcher)的职能为：当订单或者车辆处于可用状态，默认分派器决定该订单或者车辆下一步的工作如何进行。并且，默认分派器在执行此操作时需遵循以下步骤：

在这里插入图片描述

将新的运输订单准备就绪。需要包括检查一般可达性和未完成的依赖项。
对当前正在进行的进程进行更新。一般包括:

撤销运输订单
成功完成的运输订单
给正在执行序列订单的车辆分配后续的运输订单；

将当前闲置的车辆分配给可执行的订单。此时需要考虑到一些准则：

车辆：
- 该车辆在行驶路线上的位置必须已知；
- 该车辆没有被分配给运输订单或分配的任务不是必要的（比如电量充足的情况下执行充电任务或或前往停车点）；
- 该车电量尚不影响使用；
订单：
- 该订单是一般可调度的；
- 该订单不是已被某车辆执行的序列订单的一部分；
分配机制：
- 如果可处理的运输订单大于未占用的车辆，则车辆按照可配置的标准进行排序，然后，默认分派器迭代排序后的列表，对于每辆车，查找其可执行的所有订单，计算所需的路线，根据可配置的标准对候选车辆进行排序，并分配第一个任务；
- 如果可处理的运输订单少于未占用的车辆，则运输订单按照可配置的标准进行排序，然后默认分派器对列表进行迭代，为每个运输订单找到所有可执行它的车辆，然后计算所需路径，并安排好第一个任务；

将仍闲置的车辆送往充电站。需要考虑的标准为：

该车辆在行驶路线上的位置必须处于已知状态；
该车辆的电量水平降低了。

将仍闲置的车辆送往充电站。需要考虑的标准为：

该车辆在行驶路线上的位置必须处于已知状态；
该车辆不能已经在停车点位置了。

2.1 默认的停车位置选择

当一辆小车被派往停车点时，默认选择最接近（依据路由）且未被占用的停车点。可以通过设置以下关键属性来给车辆分配固定的位置。

tcs:preferredParkingPosition:模型中的点名。如果此停车点已被占用，则车辆选择附近距离最近的停车点代替。
tcs:assignedParkingPosition:模型中的点名。如果此停车点已被占用，则车辆不会前往到其他停车点，而是保持原地不动。
assignedParkingPosition优先级高于preferredParkingPosition。

2.2 可选停车位置属性

停车位置的优先级是可以明确的，车辆也可以按照一种新的停车序列进行重新停车操作。例如将车辆停放在运输订单频繁的第一目的地附近的位置。
要给停车点设置一个优先级，可以用tcs:parkingPositionPriority键设置一个属性在点上。该属性的值应为十进制整数，值越小，则会导致停车位的优先级更高。
1.3. Default recharging location selection

2.3 默认的充电位置选择

当车辆被派往充电位置时，默认选择最接近（依据路由）且未被占用的充电位置。也可通过为以下键设置属性来给车辆分配固定位置：

preferredRechargeLocation：如果此充电位置已被占用，则选择附近距离最近的充电位置。
assignedRechargeLocation：如果此充电位置已被选择，则车辆不会被派往到其他充电位置。
assignedRechargeLocation优先级高于preferredRechargeLocation。

2.4 即时运输订单分配

系统除了根据默认的流程和规则分配运输订单外，还可以显式分配运输订单(即时)。运输订单的即时分配支持具有预期车辆的运输订单。在这样的情况下，运输订单及其预期车辆通常处于可能进行分配的状态，但在常规调度程序流中被某些过滤条件阻止，因此采取这种方法将会很有用。

Although the immediate assignment of transport orders bypasses some of the filter criteria in the regular dispatcher flow, it works only in specific situations. Regarding the transport order’s state:

尽管传输订单的即时分配绕过了常规调度流程中的一些过滤条件，但它只在特定情况下起作用。考虑运输订单的状态:

运输订单的状态必须是可指派的（DISPATCHABLE）。
运输订单不能是订单序列的一部分。
必须设置运输订单的预定车辆。

至于(预定)车辆的状态:

车辆的处理状态必须为IDLE。
车辆状态必须为IDLE或CHARGING。
车辆的集成级别必须是TO_BE_UTILIZED。
车辆必须被报告在已知位置。
车辆不得处理订单序列。

除了运输订单和预定车辆的各自状态之外，分派器可能还有其他特定的原因来拒绝即时分配。

3. 默认任务分派器的配置项

默认任务分派器提供以下配置项实现可配置.
defaultdispatcher.orderCandidatePriorities

Type: Comma-separated list of strings
Trigger for changes to be applied: on application start
Description: Keys by which to prioritize transport order candidates for assignment.
Possible values:
BY_AGE: Sort by transport order age, oldest first.
BY_DEADLINE: Sort by transport order deadline, most urgent first.
DEADLINE_AT_RISK_FIRST: Sort orders with deadlines at risk first.
BY_COMPLETE_ROUTING_COSTS: Sort by complete routing costs, lowest first.
BY_INITIAL_ROUTING_COSTS: Sort by routing costs for the first destination.
BY_ORDER_NAME: Sort by transport order name, lexicographically.

defaultdispatcher.orderPriorities

Type: Comma-separated list of strings
Trigger for changes to be applied: on application start
Description: Keys by which to prioritize transport orders for assignment.
Possible values:
BY_AGE: Sort by age, oldest first.
BY_DEADLINE: Sort by deadline, most urgent first.
DEADLINE_AT_RISK_FIRST: Sort orders with deadlines at risk first.
BY_NAME: Sort by name, lexicographically.

defaultdispatcher.vehicleCandidatePriorities

Type: Comma-separated list of strings
Trigger for changes to be applied: on application start
Description: Keys by which to prioritize vehicle candidates for assignment.
Possible values:
BY_ENERGY_LEVEL: Sort by energy level of the vehicle, highest first.
IDLE_FIRST: Sort vehicles with state IDLE first.
BY_COMPLETE_ROUTING_COSTS: Sort by complete routing costs, lowest first.
BY_INITIAL_ROUTING_COSTS: Sort by routing costs for the first destination.
BY_VEHICLE_NAME: Sort by vehicle name, lexicographically.

defaultdispatcher.vehiclePriorities

Type: Comma-separated list of strings
Trigger for changes to be applied: on application start
Description: Keys by which to prioritize vehicles for assignment.
Possible values:
BY_ENERGY_LEVEL: Sort by energy level, highest first.
IDLE_FIRST: Sort vehicles with state IDLE first.
BY_NAME: Sort by name, lexicographically.

defaultdispatcher.deadlineAtRiskPeriod
Type: Integer
Trigger for changes to be applied: on application start
Description: The time window (in ms) before its deadline in which an order becomes urgent.

defaultdispatcher.assignRedundantOrders

Type: Boolean
Trigger for changes to be applied: instantly
Description: Whether orders to the current position with no operation should be assigned.

defaultdispatcher.dismissUnroutableTransportOrders

Type: Boolean
Trigger for changes to be applied: instantly
Description: Whether unroutable incoming transport orders should be marked as UNROUTABLE.

defaultdispatcher.reroutingImpossibleStrategy

Type: String
Trigger for changes to be applied: instantly
Description: The strategy to use when rerouting of a vehicle results in no route at all.
The vehicle then continues to use the previous route in the configured way.
Possible values:
IGNORE_PATH_LOCKS: Stick to the previous route, ignoring path locks.
PAUSE_IMMEDIATELY: Do not send further orders to the vehicle; wait for another rerouting opportunity.
PAUSE_AT_PATH_LOCK: Send further orders to the vehicle only until it reaches a locked path; then wait for another rerouting opportunity.

defaultdispatcher.parkIdleVehicles

Type: Boolean
Trigger for changes to be applied: instantly
Description: Whether to automatically create parking orders for idle vehicles.

defaultdispatcher.considerParkingPositionPriorities

Type: Boolean
Trigger for changes to be applied: instantly
Description: Whether to consider parking position priorities when creating parking orders.

defaultdispatcher.reparkVehiclesToHigherPriorityPositions

Type: Boolean
Trigger for changes to be applied: instantly
Description: Whether to repark vehicles to parking positions with higher priorities.

defaultdispatcher.rechargeIdleVehicles

Type: Boolean
Trigger for changes to be applied: instantly
Description: Whether to automatically create recharge orders for idle vehicles.

defaultdispatcher.keepRechargingUntilFullyCharged

Type: Boolean
Trigger for changes to be applied: instantly
Description: Whether vehicles must be recharged until they are fully charged.
If false, vehicle must only be recharged until sufficiently charged.

defaultdispatcher.idleVehicleRedispatchingInterval

Type: Integer
Trigger for changes to be applied: when/after plant model is loaded
Description: The interval between redispatching of vehicles.

4. 参考资料与源码

本文内容参考:官方文档

该模块源码位于:
openTCS-Strategies-Default/src/main/java/org/opentcs/strategies/basic/dispatching/DefaultDispatcher.java,代码如下:

 public DefaultDispatcher(OrderReservationPool orderReservationPool,
                           TransportOrderUtil transportOrderUtil,
                           InternalVehicleService vehicleService,
                           @ApplicationEventBus EventSource eventSource,
                           @KernelExecutor ScheduledExecutorService kernelExecutor,
                           FullDispatchTask fullDispatchTask,
                           Provider<PeriodicVehicleRedispatchingTask> periodicDispatchTaskProvider,
                           DefaultDispatcherConfiguration configuration,
                           RerouteUtil rerouteUtil,
                           OrderAssigner orderAssigner,
                           TransportOrderAssignmentChecker transportOrderAssignmentChecker) {
    this.orderReservationPool = requireNonNull(orderReservationPool, "orderReservationPool");
    this.transportOrderUtil = requireNonNull(transportOrderUtil, "transportOrderUtil");
    this.vehicleService = requireNonNull(vehicleService, "vehicleService");
    this.eventSource = requireNonNull(eventSource, "eventSource");
    this.kernelExecutor = requireNonNull(kernelExecutor, "kernelExecutor");
    this.fullDispatchTask = requireNonNull(fullDispatchTask, "fullDispatchTask");
    this.periodicDispatchTaskProvider = requireNonNull(periodicDispatchTaskProvider,
                                                       "periodicDispatchTaskProvider");
    this.configuration = requireNonNull(configuration, "configuration");
    this.rerouteUtil = requireNonNull(rerouteUtil, "rerouteUtil");
    this.orderAssigner = requireNonNull(orderAssigner, "orderAssigner");
    this.transportOrderAssignmentChecker = requireNonNull(transportOrderAssignmentChecker,
                                                          "transportOrderAssignmentChecker");
  }

  @Override
  public void initialize() {
    if (isInitialized()) {
      return;
    }

    LOG.debug("Initializing...");

    transportOrderUtil.initialize();
    orderReservationPool.clear();

    fullDispatchTask.initialize();

    implicitDispatchTrigger = new ImplicitDispatchTrigger(this);
    eventSource.subscribe(implicitDispatchTrigger);

    LOG.debug("Scheduling periodic dispatch task with interval of {} ms...",
              configuration.idleVehicleRedispatchingInterval());
    periodicDispatchTaskFuture = kernelExecutor.scheduleAtFixedRate(
        periodicDispatchTaskProvider.get(),
        configuration.idleVehicleRedispatchingInterval(),
        configuration.idleVehicleRedispatchingInterval(),
        TimeUnit.MILLISECONDS
    );

    initialized = true;
  }

  @Override
  public void terminate() {
    if (!isInitialized()) {
      return;
    }

    LOG.debug("Terminating...");

    periodicDispatchTaskFuture.cancel(false);
    periodicDispatchTaskFuture = null;

    eventSource.unsubscribe(implicitDispatchTrigger);
    implicitDispatchTrigger = null;

    fullDispatchTask.terminate();

    initialized = false;
  }

  @Override
  public boolean isInitialized() {
    return initialized;
  }

  @Override
  public void dispatch() {
    LOG.debug("Scheduling dispatch task...");
    // Schedule this to be executed by the kernel executor.
    kernelExecutor.submit(fullDispatchTask);
  }

  @Override
  public void withdrawOrder(TransportOrder order, boolean immediateAbort) {
    requireNonNull(order, "order");
    checkState(isInitialized(), "Not initialized");

    // Schedule this to be executed by the kernel executor.
    kernelExecutor.submit(() -> {
      LOG.debug("Scheduling withdrawal for transport order '{}' (immediate={})...",
                order.getName(),
                immediateAbort);
      transportOrderUtil.abortOrder(order, immediateAbort);
    });
  }

  @Override
  public void withdrawOrder(Vehicle vehicle, boolean immediateAbort) {
    requireNonNull(vehicle, "vehicle");
    checkState(isInitialized(), "Not initialized");

    // Schedule this to be executed by the kernel executor.
    kernelExecutor.submit(() -> {
      LOG.debug("Scheduling withdrawal for vehicle '{}' (immediate={})...",
                vehicle.getName(),
                immediateAbort);
      transportOrderUtil.abortOrder(vehicle, immediateAbort);
    });
  }

  @Override
  public void topologyChanged() {
    if (configuration.rerouteOnTopologyChanges()) {
      LOG.debug("Scheduling reroute task...");
      kernelExecutor.submit(() -> {
        LOG.info("Rerouting all vehicles due to topology change...");
        rerouteUtil.reroute(vehicleService.fetchObjects(Vehicle.class), ReroutingType.REGULAR);
      });
    }
  }

  @Override
  public void reroute(Vehicle vehicle, ReroutingType reroutingType) {
    LOG.debug("Scheduling reroute task...");
    kernelExecutor.submit(() -> {
      LOG.info(
          "Rerouting vehicle due to explicit request: {} ({}, current position {})...",
          vehicle.getName(),
          reroutingType,
          vehicle.getCurrentPosition() == null ? null : vehicle.getCurrentPosition().getName()
      );
      rerouteUtil.reroute(vehicle, reroutingType);
    });
  }

  @Override
  public void assignNow(TransportOrder transportOrder)
      throws TransportOrderAssignmentException {
    requireNonNull(transportOrder, "transportOrder");

    TransportOrderAssignmentVeto assignmentVeto
        = transportOrderAssignmentChecker.checkTransportOrderAssignment(transportOrder);

    if (assignmentVeto != TransportOrderAssignmentVeto.NO_VETO) {
      throw new TransportOrderAssignmentException(
          transportOrder.getReference(),
          transportOrder.getIntendedVehicle(),
          assignmentVeto
      );
    }

    orderAssigner.tryAssignments(
        List.of(vehicleService.fetchObject(Vehicle.class, transportOrder.getIntendedVehicle())),
        List.of(transportOrder)
    );
  }
}