METHOD AND SYSTEM FOR CONTROLLING A PLURALITY OF VEHICLES, IN PARTICULAR AUTONOMOUS VEHICLES

Abstract

A traffic planning method for controlling a plurality of vehicles is disclosed, wherein each vehicle occupies one node in a shared set of planning nodes and is movable to other nodes along predefined edges between pairs of the nodes in accordance with a finite set of motion commands. The method comprises: obtaining initial node occupancies of the vehicles; from said finite set of motion commands, determining a mean number of feasible motion commands in a neighborhood of the initial node occupancies; determining a search depth d which makes optimal use of a predefined computational budget; and determining a suitable sequence of motion commands by means of an optimization process which considers the search depth d.

Claims

1. A traffic planning method for controlling a plurality of vehicles, wherein each vehicle occupies one node in a shared set of planning nodes and is movable to other nodes along predefined edges between pairs of the nodes in accordance with a finite set of motion commands, the method comprising: obtaining initial node occupancies of the vehicles; and determining a sequence of motion commands by means of an optimization process which considers a search depth, wherein the search depth is variable and determined by the following preceding steps: from said finite set of motion commands, determining a mean number of feasible motion commands in a neighborhood of the initial node occupancies; and determining said search depth d which makes optimal use of a predefined computational budget.

2. The method of claim 1, wherein: the computational budget is a maximum number of leaves in a search tree; and the search depth is calculated by applying the mean number of feasible motion commands as a mean branching factor of the search tree.

3. The method of claim 1, wherein the neighborhood of the initial node occupancies corresponds to a predefined search depth.

4. The method of claim 1, wherein the predefined search depth is significantly less than typical values of the search depth.

5. The method of claim 1, wherein said determining comprises processing the initial node occupancies to identify vehicles which are temporarily non-movable.

6. The method of claim 1, wherein said determining includes comparing the initial node occupancies with a set of deadlock patterns.

7. The method of claim 1, further comprising feeding the sequence of motion commands to said plurality of vehicles.

8. The method of claim 1, wherein the vehicles are autonomous vehicles.

9. The method of claim 1, wherein the motion commands correspond to tactical decision-making.

10. A device configured to control a plurality of vehicles, wherein each vehicle occupies one node in a shared set of planning nodes and is movable to other nodes along predefined edges between pairs of the nodes in accordance with a finite set of motion commands, the device comprising: a first interface configured to receive initial node occupancies of the vehicles; a second interface configured to feed motion commands selected from said finite set to said plurality of vehicles; and processing circuitry configured to perform the method of claim 1.

11. A computer program comprising instructions which, when the program is executed by a computer, cause the computer to carry out the method of claim 1.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0023] Aspects and embodiments are now described, by way of example, with reference to the accompanying drawings, on which:

[0024] FIG. 1 is a flowchart of a traffic planning method;

[0025] FIG. 2 shows a device suitable for controlling a plurality of vehicles;

[0026] FIG. 3 is a schematical representation of a road network with numbered waypoints;

[0027] FIG. 4 shows example vehicles that can be controlled centrally using embodiments of the invention;

[0028] FIG. 5 is a search tree representing possible sequences of commands to the vehicles; and

[0029] FIG. 6 are outlines in semilogarithmic scale of two example search trees illustrating the significance of the notation d, d.sub.0.

DETAILED DESCRIPTION

[0030] The aspects of the present disclosure will now be described more fully hereinafter with reference to the accompanying drawings, in which certain embodiments of the invention are shown. These aspects may, however, be embodied in many different forms and should not be construed as limiting; rather, these embodiments are provided by way of example so that this disclosure will be thorough and complete, and to fully convey the scope of all aspects of the invention to those skilled in the art. Like numbers refer to like elements throughout the description.

[0031] FIG. 3 is a schematic representation of a road network. Waypoints are defined at the road junctions wp1, wp3 and additionally at some intermediate locations wp2, wp4, wp5, . . . , wp8. Some of the intermediate locations may correspond to so-called absorption nodes, where a visiting vehicle is required to dwell for a predetermined or variable time, for purposes of loading, unloading, maintenance etc. The arrangement of the waypoints is not essential to the present invention, rather their location and number may be chosen as deemed necessary in each use case to achieve smooth and efficient traffic control. The waypoints are treated as planning nodes which are shared by a plurality of vehicles v1, v2, v3, v4. Abstractly, a planning node may be understood as a logical entity which is either free or occupied by exactly one vehicle at a time. An occupied node is not consumed but can be released for use by the same or another vehicle. Planning nodes may represent physical space for transport or parking, a communication channel, maintenance machinery, additional equipment for optional temporary use, such as tools or trailers.

[0032] Each vehicle (see FIG. 4) is controllable by an individual control signal, which may indicate a command from a finite set of predetermined commands. It is understood that individual control signals may be multiplexed onto a common carrier. A predetermined command may represent an action to be taken at the next waypoint (e.g., continue straight, continue right, continue left, stop), a next destination, a speed adjustment, a loading operation or the like. Implicit signaling is possible, in that a command has a different meaning depending on its current state (e.g., toggle between an electric engine and a combustion engine, toggle between high and low speed, drive/wait at the next waypoint). A vehicle which receives no control signal or a neutrally-valued control signal may be configured to continue the previously instructed action or to halt. The predetermined commands preferably relate to tactical decision-making, which corresponds to a time scale typically shorter than strategic decision-making and typically longer than operational (or machine-level) decision-making. Different vehicles may have different sets of commands. In the method 100 to be described below, the finite set of motion commands may correspond to these predetermined commands.

[0033] One aim of the present disclosure is to enable efficient centralized control of the vehicles v1, v2, v3, v4. The vehicles v1, v2, v3, v4 are to be controlled as a group, with mutual coordination. The mutual coordination may entail that any planning node utilization conflicts that could arise between vehicles are deferred to a planning algorithm and resolved at the planning stage. The planning may aim to maximize productivity, such as the total quantity of useful transport system work or the percentage of on-schedule deliveries of goods. The planning may additionally aim to minimize cost, including fuel consumption, battery wear, mechanical component wear or the like.

[0034] Regarding the planning node utilization conflicts that may arise, it may initially be noted that no vehicle blocks any other vehicle for the node occupancies (start state) shown in FIG. 3, that is

[00001]$O\left(\begin{array}{c}v1\\ v2\\ v3\\ v4\end{array}\right)=\left(\begin{array}{c}\mathrm{wp}1\\ \mathrm{wp}4\\ \mathrm{wp}6\\ \mathrm{wp}8\end{array}\right).$

It can also be seen that these node occupancies provide each vehicle with a next waypoint to which it can move in a next epoch. The choice is not arbitrary, however, as both vehicles v1 and v4 may theoretically move to waypoint wp3, but this conflict can be avoided by routing vehicle v1 to waypoint wp2 instead. If the system is evolved in this manner, that is

[00002]$O\left(\begin{array}{c}v1\\ v2\\ v3\\ v4\end{array}\right)=\left(\begin{array}{c}\mathrm{wp}2\\ \mathrm{wp}5\\ \mathrm{wp}7\\ \mathrm{wp}3\end{array}\right),$

then vehicle v4 will block vehicle v1 from moving. This blocking state temporarily reduces the vehicle system's productivity but will be resolved once vehicle v4 continues to waypoint wp4.

[0035] It is easy to realize that the difficulty of the blocking states (as measured, say, by the number of vehicle movements needed to reach a non-blocking state) in a given waypoint topology will increase with the number of vehicles present. The efficiency gain of deploying many vehicles may therefore be offset by the increased risk of conflicts. A waypoint topology populated with many vehicles may also include deadlock states, where no vehicle movement is possible. This may correspond to a real-life scenario where the controlled vehicles need external help to resume operation, such as operator intervention, towing etc.

[0036] The following description is made under an assumption of discrete time, that is, the traffic system evolves in evenly spaced epochs. The length of an epoch may be of the order of 0.1 s, 1 s, 10 s or longer. At each epoch, either a command a1, a2 is given to one of the vehicles v1, v2, v3, v4, a command is given to a predefined group of vehicles, or no command is given. Quasi-simultaneous commands v1.a1, v2.a1 to two vehicles v1, v2 or two vehicle groups can be distributed over two consecutive epochs. To allow approximate simultaneity, the epoch length may be configured shorter than the typical time scale of the tactical decision-making for one vehicle.

[0037] With this setup, the space of possible planning outcomes corresponds to the set of all command sequences of length d, where d is the planning horizon (or lookahead horizon). Equivalently, if the planning process is represented as a search tree of the type shown in FIG. 5, the possible planning outcomes are in a one-to-one relationship with the leaves; the corresponding command sequence is the path from the root to this leaf. The search tree covers seven epochs t1, t2, . . . , t7. The planning horizon is seven times the duration of an epoch. For each epoch, there are five possibilities: no command is given (0), command a1 is given to vehicle v1 (v1.a1), command a2 is given to vehicle v1 (v1.a2), command a1 is given to vehicle v2 (v2.a1) or command a2 is given to vehicle v2 (v2.a2).

[0038] Within the scope of the present disclosure, a multitude of planning algorithms can be used. A straightforward possible planning approach may be to assign a rule-based score to each possible planning outcome (i.e., sequence of commands) and select the most beneficial one. The score may be assigned on the basis of simulating the movement of the vehicles which will result from applying that sequence of commands, e.g., to find their positions at the planning horizon. Other approaches may include heuristics to accelerate the search for an acceptable solution. The heuristics may help identify on an early stage such sequences of commands that are less promising and exclude them from a full evaluation. As mentioned above, an example heuristic is to remove vehicles from potentially blocking positions without delay. Machine-learning techniques may be useful. The machine-learning agent (e.g., an artificial neural network) may be trained to propose the most suitable action (i.e., command sequence) for a given state. Regardless of the choice of planning algorithm, the computational effort generally has a high sensitivity to a change in the number of leaves, which means that the necessary resource allocation varies significantly with the search depth considered in each execution.

[0039] It is initially assumed that all five possibilities remain available in the next epoch, whichever possibility is chosen in the present epoch, so that the branching factor (or fan-out) of the search tree is 5 everywhere. An outcome of the planning is a 7-element sequence, like (v1.a1, v2.a2, v2.a2, v2.a2, v2.a2, v2.a2, 0), as suggested in FIG. 5, or (0, 0, 0, 0, 0, 0, 0). Due to the limited drawing space in FIG. 5, repeating parts of the search tree are represented by elliptic dots ( . . . ) or altogether omitted. The leaves of the tree are the tree nodes at the last epoch t7. Their number is 5.sup.7=78125.

[0040] The use of a greater planning horizon usually promotes overall more economical vehicle movements, as it helps avoid blocking or near-blocking states, or other consequences of overly ‘short-sighted’ planning. This however comes at a computational cost: The number of leaves grows exponentially with the planning depth d. When a further vehicle v3 is added, the number of leaves grows as a power of the planning depth d=7. If the addition implies that one more command v3.a1 can be given at each epoch, there will be 6.sup.d leaves; if the addition implies that two more commands v3.a1, v3.a2 per epoch are available, there will be 7.sup.d leaves, and so forth. There is clearly a dependence on the number of commands as well. In a hypothetic case where each one of N vehicles is controllable by exactly one command each (e.g., drive/wait), the search tree has (N+1).sup.d leaves. In the general case, if the n.sup.th vehicle accepts k.sub.n≥1 commands, the number of leaves for planning depth d is

[00003]${\left(1+\underset{n=1}{\overset{N}{.Math.}}{k}_n\right)}^d.$

[0041] As announced, the search space size is proportional to the d.sup.th power of a number which grows at least linearly with the number N of vehicles. For example, if d=10, N=2 and k.sub.1=k.sub.2=2, then the search space size (number of leaves) is about 10.sup.7, which may or may be computationally tractable, depending on the available processing power. If instead d=10, N=10 and k.sub.1=k.sub.2= . . . =k.sub.10=2, the search space size of the order of 10.sup.13, which would be extremely costly to process. The search space size may be independent of the number of planning nodes.

[0042] It is now assumed, instead, that some epochs allow less than all five possibilities. The present invention can achieve a potential efficiency gain in cases where the branching factor drops below the theoretical maximum for some epochs. Such drops may result when it is not possible or meaningful to control some of the vehicles. For example, the initial node occupancies may render some of the commands infeasible, e.g., since one vehicle is temporarily not mobile. Further, it may turn out that some of the commands that are a priori available in one epoch may in fact evolve the vehicle system into a deadlock pattern, and that command is to be treated as infeasible too. For these and similar reasons, the branching factor may vary across different epochs and it may be less than 5 in some epochs. As a result, and notably since the epochs with a branching factor below 5 may restrain the exponential growth of the tree significantly, the number of leaves in a seven-epoch tree may be much below 78125. The number of leaves can be computed as

[00004]$\underset{\ell =1}{\overset{d}{.Math.}}{b}_{\ell }$

[0043] In FIG. 5, the search depth d=7 and the local branching factors <5.

[0044] To illustrate, FIG. 6 shows outlines of two example search trees 601, 602. The horizontal length scale is logarithmic, in the sense that the local width of the tree corresponds to the logarithm of the number of states in that epoch, whereas the vertical length scale is linear with respect to the number of epochs. The first search tree 601 grows weakly: the feasible commands are fewer than the theoretical maximum branching factor in at least some epochs. The second search tree 602 grows with the theoretical maximum branching factor in every epoch, and therefore reaches a number of leaves equal to that of the first search tree 601 already for a smaller search depth d. The inventor has realized that the branching factor has a limited variation with respect to successive epochs. This is why the mean branching factor of the search tree can be estimated on the basis of the mean number of feasible motion commands for a neighborhood of the initial node occupancies. The neighborhood may comprise the first d.sub.0 epochs of the actual search tree. Although the pre-defined search depth d.sub.0 may be significantly less than typical values of the search depth d, it may provide enough guidance towards the true mean branching factor, as an indicator of whether the search tree has weak or strong growth.

[0045] The usefulness of the invention is confirmed by numerical data for two example waypoint topologies.

[0046] Example 1: First waypoint topology (not shown); eight deployed vehicles; each vehicle is controllable by the commands “drive” and “wait”. Initially, all vehicles are freely movable; none occupies an absorption node. For a search depth of 3 epochs, the search tree has 158 leaves.

[0047] Example 2: First waypoint topology; eight deployed vehicles; each vehicle is controllable by the commands “drive” and “wait”. Initially, one of the vehicles occupies an absorption node (unloading). For a search depth (planning horizon) of 3 epochs, the search tree has 69 leaves.

[0048] A comparison of the above data sets suggests that a processor which solves the planning problem of example 1 in acceptable time runs with excess capacity when handling example 2. The excess capacity could be spent on increasing the search depth by one or more epochs. With reference to FIG. 6, examples 1 and 2 may be likened to the respective outlined search trees 602 and 601, where the weaker growing tree 601 allows a greater planning depth d without exceeding the tractable number of leaves.

[0049] Example 3: Second waypoint topology; two deployed vehicles; each vehicle is controllable by the commands “drive” and “wait”. Initially, all vehicles are freely movable. For a search depth of 5 epochs, the search tree has 262 leaves.

[0050] Example 4: Second waypoint topology; two deployed vehicles; each vehicle is controllable by the commands “drive” and “wait”. Initially, one of the vehicles is in a single-lane two-way section of the road network, where the command “wait” is blocked according to preprogrammed control logic. For a search depth of 5 epochs, the search tree has 63 leaves.

[0051] Again, it appears that the available computational resources would suffice even if the search depth in example 4 was increased to 6, 7 or more. This may promote more prudent vehicle control and, as a consequence, smoother and more economical operation.

[0052] With reference now to FIG. 1, a traffic planning method 100 according to one embodiment will be described. The method 100 may be implemented by a general-purpose programmable computer, such as the device 200 shown in FIG. 2 to be described below.

[0053] In a first step 110 of the method 100, the initial node occupancies of the vehicles are obtained. The node occupancies may be represented as a data structure associating each vehicle with a planning node, like the 0 function above.

[0054] In a second step 112, a mean number of feasible motion commands in a neighborhood of the initial node occupancies is determined. Reference is made to the above definition of feasible motion commands, and it is recalled that this number is equal to the local branching factor. The neighborhood may correspond to a smaller search tree with the initial node occupancies as its root and having a predefined search depth d.sub.0, wherein the predefined search depth d.sub.0 is typically significantly less than typical values of the search depth d. The second step 112 may be described metaphorically as ‘scouting’ the branching factor, i.e., generating the first d.sub.0 levels of the search tree, sampling the branching factor for these levels, and using this number to approximate b, the mean branching factor for the full tree. The approximation is well justified as it has been found that, in traffic-planning applications, the branching factor has a limited variation with respect to successive epochs.

[0055] The mean branching factor in the neighborhood may be computed as the arithmetic mean of the local branching factors:

[00005]$\stackrel{\_}{b}\approx \frac{b_1+b_2+.Math.+b_{d_0}}{d_0},$

where is the branching factor on the .sup.th level of the search tree. Alternatively, the number of leaves L at the d.sub.0.sup.th level is determined and the mean value branching factor is computed as the d.sub.0.sup.th root, i.e., b≈L.sup.1/d.sup.0.

[0056] In specific implementations, the second step 112 may include a substep of processing 112.1 the initial node occupancies to identify vehicles which are temporarily non-movable. Alternatively or additionally, the second step 112 includes a substep of comparing 112.2 the initial node occupancies with a set of deadlock patterns, to thereby assess which motion commands cannot be used.

[0057] In a third step 114 of the method 100, a search depth d which makes optimal use of a predefined computational budget is computed on the basis of the approximate mean branching factor b, i.e., the mean number of feasible motion commands in the neighborhood of the initial node occupancies. If the computational budget is expressed as a maximum number of leaves in a search tree, L.sub.max, then one may set d to the greatest integer satisfying b.sup.d≤L.sub.max, or d=└log L.sub.max/log b┘.

[0058] In a fourth step 116 of the method 100, a suitable sequence of motion commands is determined by means of an optimization process which considers a search depth of d. The optimization process may include executing a planning algorithm of any of the types discussed above. It is noted that the optimization process may be allowed to execute until a converge criterion is met, until an optimality criterion is fulfilled and/or until a predefined time has elapsed. Actually reaching optimality is no necessary condition under the present invention.

[0059] In an optional fifth step 118, the thus determined sequence of motion commands is fed to said plurality of vehicles for execution.

[0060] FIG. 2 shows, in accordance with a further embodiment, a device 200 for controlling a plurality of vehicles 299 sharing a set of planning nodes. The device 200 has a first interface 210 configured to receive initial node occupancies of the vehicles 299. Optionally, it may further receive, for each vehicle, information representing a set of motion commands v1.a1, v1.a2, v2.a1, v2.a2, which can be fed to the respective vehicles, and/or a mission (utility task) to be carried out may by the vehicles 299. The initial node occupancies may be obtained from a traffic control entity communicating with the vehicles 299, from sensors detecting the positions of the vehicles 299, or from a reply to a self-positioning query issued to the vehicles 299. The optional information may be entered into the first interface 210 by an operator or provided as configuration data once it is known which vehicles 299 will form the fleet.

[0061] The device 200 further has a second interface 220 configured to feed commands selected from said motion commands to said plurality of vehicles, as well as processing circuitry 230 configured to perform the method 100 described above. FIG. 2 shows direct wireless links from the second interface 220 to the vehicles 299. In other embodiments, as explained above, the second interface 220 may instead feed sequences of the motion commands to the traffic control entity, which takes care of the delivery of the commands to the vehicles 299.

[0062] FIG. 4 shows a truck 400, a bus 402 and a construction equipment vehicle 404. A fleet of vehicles of one or more of these types, whether they are autonomous or conventional, can be controlled in a centralized fashion using the method 100 or the device 200 described above.

[0063] The aspects of the present disclosure have mainly been described above with reference to a few embodiments. However, as is readily appreciated by a person skilled in the art, other embodiments than the ones disclosed above are equally possible within the scope of the invention, as defined by the appended patent claims.