PIECEWISE CONTROL

TECHNICAL FIELD

The present disclosure generally relates to system control and in particular to methods utilising piecewise control strategies.

BACKGROUND

For state and disturbance estimation in control of fast dynamic devices and/or systems, two popular techniques have been presented, namely Kalman filter and Moving Horizon Estimation (MHE) techniques. While the use of Kalman filter can provide offset-free tracking for time-varying and uncertain loads, in practice, tuning the covariance matrices of the filter can be rather difficult. Moreover, the Kalman filter does not allow for constraints on the system's states and/or disturbances to be taken into account, thus limiting the ability of the closed-loop system to operate within the required range. On the other hand, MHE overcomes the limitations of the Kalman filter by employing an extended dynamic model and statistical information about the states and inputs, while incorporating the system's constraints in the estimation. Another method to control constrained multivariable systems is Model predictive control (MPC), which generally is computationally demanding online.

Both MPC and MHE strategies require the solution of an optimization problem at each sampling instant. A predictive controller determines the next control action by solving an optimal control problem using the current state of the system as initial state during a future sliding-window. A moving horizon estimator estimates the current state by using information about the previous states, and solving an estimation problem during a past sliding- window.

The successful implementation of both MPC and MHE depends on fast and reliable algorithms which can compute a solution on-line within the required sampling instant. For the control and state estimation in for example DC-DC converters, a very short sampling rate is required, requiring a solution vsithin the micro-seconds range. The optimization problem arising from MPC and MHE admit solutions that are piecewise affine and that can be computed off- line, i.e. explicitly. The derived control/estimation laws are obtained by formulating the control and estimation problem as multi-parametric programs and then solving the corresponding problem by means of multi- parametric programming and other methods. The solutions of such problems provide a partitioning of the state space into critical regions, each associated with a state feedback control or state estimation law. These policies can then be implemented by simply evaluating the pre-computed solutions using a 'look-up table', thus reducing the computational demand and allowing fast sampling instances. EMPC/EMHEseeks to derive an optimal

control/estimation law or control law at each sampling instant by identifying the region in which the current state lies. The main considerations when dealing with EMPC/EMHE is the ability to identify the appropriate region within the required sampling time while taking into consideration memory requirements needed to store a large number of regions. The point location problem can be summarized as follows: Given the current state x and a collection of possibly overlapping subsets {R _I ,...,RR}, determine any integer i such that Ri contains x. The optimiser of the associated optimization problem is then given by u(x) = μί(χ), where the function μί(χ) describes the optimiser in region Ri, i.e. the optimal control or estimation law in Ri that has been precomputed off-line. For many optimization problem classes such as quadratic programs, the regions Ri are polyhedral sets, i.e. polytopes, and the functions μί(χ) are affine: li := {x 6 R ⁿ : Gi ≤ #i } and Despite the advantages previously described, one of the major limitations of the above-mentioned techniques is that the complexity of the pre-computed control/estimation law grows exponentially with the number of states, control inputs and control/estimation horizon length. Accordingly, for the control and estimation of fast dynamic processes only very short control and estimation horizons and/or low dimensional problems. . For longer horizons and more complex models, the computational demand required for the controller/estimator to find the solution through a large number of regions thus outweighs the benefits of having a pre-computed solution rendering the above techniques inefficient.

SUMMARY

In view of the above, a general object of the present disclosure is to provide faster computation online in piecewise control, in particular for EMPC and EMHE.

Hence according to a first aspect of the present disclosure there is provided a method of controlling a system by means of an explicit model predictive control, EMPC, or explicit moving horizon estimator, EMHE, control strategy, wherein the system is associated with a state space describing states that the system can obtain and which state space is composed of a plurality of regions, each region being defined by a set of points in state space which fulfil a region-specific relation, and each region being associated with an index, wherein each index is associated with a control law, wherein the method comprises: a) determining a current state of the system, the current state

corresponding to a point in state space, b) determining an index of that region which comprises the current state by determining a region-specific relation that is fulfilled with respect to the current state, wherein the determining of the index is performed in a parallel manner such that the current state is evaluated with respect to at least two different region-specific relations in parallel, c) determining a control law associated with the index, and d) controlling the system based on the control law.

By means of parallel evaluation of the current state in view of region-specific relations, online computation time may be reduced. Thereby fast dynamic systems/processes may be controlled in a satisfying manner utilising less processing resources.

According to one embodiment the regions are evenly distributed between the number of parallel processes performed in the step of determining of the index. According to one embodiment the regions are defined by means of

hyperplanes, wherein each hyperplane is defined by a hyperplane relation, and wherein the hyperplanes are associated with nodes of a tree structure that comprises a plurality of nodes, each node being associated with a plurality of regions, the tree structure thereby forming a truncated tree structure, wherein the method comprises, prior to the step b) of determining, a') determining a leaf node associated with the region in which the current state is contained, wherein the step b) of determining is performed for regions associated with the leaf node.

According to one embodiment the step a') of determining the leaf node comprises determining at each node leading to the leaf node whether the current state is contained in a first portion of the state space or in a second portion of the state space with respect to a respective hyperplane associated with each node leading to the leaf node.

According to one embodiment each hyperplane is defined by a hyperplane relation, and wherein in each node the step a') of determining comprises evaluating the current state with respect to respective hyperplane relations.

According to one embodiment about 10-30% of the hyperplanes are orthogonal hyperplanes and the remaining hyperplanes are region-defining hyperplanes, a region-defining hyperplane being a hyperplane which together with other region-defining hyperplanes forms a region.

According to a second aspect of the present disclosure there is provided a method of controlling a system by means of an explicit model predictive control, EMPC, or explicit moving horizon estimator, EMHE, control strategy, wherein the system is associated with a state space describing states that the system can obtain and which state space is composed of a plurality of regions, each region being defined by a set of points in state space which fulfil a relation, and each region being associated with an index, wherein each index is associated with a control law, wherein the method comprises:

A) determining a current state of the system, the current state

corresponding to a point in state space,

B) selecting a plurality of seed points in state space,

C) tracing a respective ray from each seed point to the current state

wherein the tracing comprises determining respective indexes associated with regions that are traversed by the respective ray, wherein the tracing of the rays is performed in a parallel manner, and wherein the tracing is performed until an index associated with that region which contains the current state is determined,

D) determining a control law associated with the index associated with the region containing the current state

E) controlling the system based on the control law.

According to one embodiment the step B) of selecting a plurality of seed points comprises selecting a seed point to be located in the region in which the last previous current state was located.

According to a third aspect of the present disclosure there is provided a method of controlling a system by means of an explicit model predictive control, EMPC, or explicit moving horizon estimator, EMHE, control strategy, wherein the system is associated with a state space describing states that the system can obtain and which state space is composed of a plurality of regions defined by hyperplanes, each region being associated with an index, wherein each index is associated with a control law, and wherein the hyperplanes are associated with nodes of at least one tree structure that comprises a plurality of nodes, wherein the method comprises:

I) determining a current state of the system, the current state corresponding to a point in state space,

II) i) computing a first area in which the current state is contained in the state space, wherein the first area is defined by at least two hyperplanes associated with a common node, or ii) computing a respective first area in which the current state is contained for each of at least two hyperplanes associated with a respective node of at least two tree structures, wherein the step of computing in case of each of i) and ii) is performed in parallel, and in case the first area does not correspond to a region to thereby obtain the index of that region, a. computing a second area within each first area in which the current state is contained in state space with respect to at least one hyperplane associated with a subnode of the node in case of i) or nodes in case of ii), and moving through further subnodes of the tree structure, for each further subnode computing a subarea of all previous areas utilising at least one hyperplane associated with the further subnode until an index of the that region which comprises the current state is determined,

III) determining a control law associated with the index, and controlling the system based on the control law. According to one embodiment each hyperplane is defined by a hyperplane relation, and wherein in each node any of step II) and Ila) of computing comprises evaluating the current state with respect to respective hyperplane relations. One embodiment comprises at least two tree structures, wherein each of the at least two tree structures is associated with all regions.

One embodiment comprises at least two tree structures, wherein each of the at least two tree structures is different such that each region is only associated with one tree structure According to one embodiment a tree structure of the at least one tree structures comprises a node having 2 ^N branches, N being a number corresponding to the number of hyperplanes associated with the node, wherein the step II) of computing comprises evaluating all hyperplanes associated with the node in parallel. According to one embodiment steps II) and Ila) of computing are performed in parallel.

The methods presented herein are advantageously implemented as a computer program. Thus, according to a fourth aspect there is provided a computer program comprising computer-executable components for causing a control system to perform the steps recited in any one of aspects one to three when the computer-executable components are run on a plurality of computation units included in the control system.

The computer program may beneficially be provided on a computer-readable medium. Thus in a fifth aspect of the present disclosure there is provided a computer program product comprising a computer-readable medium on which the computer program according to the fourth aspect presented herein is stored.

According to a sixth aspect there is provided a control system comprising a plurality of computation units which when performing functions in parallel are arranged to cause the control system to perform the method according to any of aspects one to three.

Generally, all terms used in the claims are to be interpreted according to their ordinary meaning in the technical field, unless explicitly defined otherwise herein. All references to "a/an/the element, apparatus, component, means, etc. are to be interpreted openly as referring to at least one instance of the element, apparatus, component, means, etc., unless explicitly stated otherwise. Moreover, any step in a method need not necessarily have to be carried out in the presented order, unless explicitly stated otherwise. BRIEF DESCRIPTION OF THE DRAWINGS

The specific embodiments of the inventive concept will now be described, by way of example, with reference to the accompanying drawings, in which:

Fig. l is a schematic block diagram of a control system for controlling a system by means of EMPC or EMHE; Fig .2 is a flowchart of an example of a method of controlling a system by means of EMPC or EMHE;

Fig. 3a is a flowchart depicting another example of a method of controlling a system by means of EMPC or EMHE;

Fig. 3b schematically depicts an example of a state space subdivided into regions, illustrating the method in Fig. 3a;

Figs 4a-b are flowcharts depicting another example of a method of

controlling a system by means of EMPC or EMHE;

Figs 5a-b show an example of a state space subdivision and a corresponding parallel binary tree; and Figs 6a-b show an example of a state space subdivision and a corresponding parallel binary tree. DETAILED DESCRIPTION

The present inventive concept relates to a plurality of control methods utilising parallel piecewise control laws on polytopes or polyhedra. Various examples illustrating these methods will be presented in the following. The methods may advantageously be utilised for controlling systems and processes which exhibit fast dynamics in the sense that it is essential to obtain a control output for controlling the system or process within a short duration of time. The methods presented herein may for example be utilised for controlling a power converter such as a DC-DC converter, an AC-AC converter, or an inverter. Furthermore, the methods may be used for controlling a process such as an industrial process, for example in fields such as pulp and paper, oil and gas, heat and power generation, metals and mining, and the chemical industry.

Control of a system or process may be seen as a problem of finding the optimal control law at each instance in order to control the current state to thereby minimize one or more overall process parameters. A state space contains the values which the process or system can attain and hence describes all states which the system or process can obtain. The current state of the system or process is thus an element in state space, i.e. it represents a point having a plurality of coordinates in state space. In EMPC/EMHE, the state space is composed of a plurality of regions, which may or may not overlap. These regions are generally polyhedral and may be defined by hyperplanes. For the purpose of online operation, i.e. for controlling a system or process in real-time, the regions have been predefined in an offline mode. Each region comprises points which fulfil a region-specific relation. This region-specific relation is formed by a system of equations where each equation defines a hyperplane. Each such equation will in the following be referred to as a hyperplane relation.

Each region has in the offline mode been associated with a control law for controlling the associated system or process. At each control instance, when the current state has been determined by means of measurement data obtained from the system or process or by means of estimation or a combination thereof, the region which contains the current state is

determined. The piecewise control methods presented herein, which form a single general inventive concept by means of reducing online computation times by utilising parallel processing, aims at finding that region in state space which contains the current state of the system or process. In particular, the search for region may be performed via parallel direct search where region-specific relations sequentially are evaluated with respect to the current state in a parallel manner, by means of a plurality of parallel tree structure algorithms or by means of parallel subdivision walk. These methods will be described in the following.

Fig. l depicts a schematic block diagram of an example of a control system l arranged to control a system S. As mentioned above, such a system may for example be a power converter, but could likewise be another type of device or a plurality of devices of for example an industrial process. The control system 1 may be a controller or it may comprise several controllers. The control system 1 comprises a computation system 3 comprising a plurality of computation units 3a, 3b,..., 3η. With a plurality of computation units is herein meant two or more computation units. The computation units may be comprised in a single computer or in several computers, each computer containing a single core or a multicore, communicating via a wired or wireless network. Each computation unit may be a processor, such as a central processing unit (CPU), graphics processing unit (GPU) or a digital signal processor (DSP). Alternatively, each computational unit maybe implemented in hardware utilising application specific integrated circuits (ASIC), field programmable gate arrays (FPGA), discrete logical components etc. Furthermore, according to one variation, the computational system may comprise a combination of dedicated hardware units and processors.

The control system 1 may optionally further comprise a memory 5 arranged to communicate with the computation system 3. The memory 5 comprises computer-executable components which when run on the computation system 3 causes the control system 1 to execute one of the methods presented herein. In particular, the computer executable-components may relate to any one of the methods described herein.

Since current state determination by means of measurements received from sensors associated with the system S and/or by means of estimation are well- known in the art, and since any means for determining the current state may be utilised for the purpose of the methods presented herein, these aspects will not be discussed any further in this disclosure. Similarly, the step of controlling the system S based on a determined control law is also well- known and will not be discussed in any detail herein. With reference to Figs 2-6b, examples of control methods implementable by a control system for controlling a system or a process by means of parallel piecewise strategies such as EMPC or EMHE will now be described in more detail. In each example the system which is to be controlled is associated with a state space describing states that the system can obtain. As previously mentioned, the state space is composed of a plurality of regions, each region being defined by a set of points in state space which fulfil a region-specific relation. Regions are in particular defined by means of hyperplanes also referred to as region-defining hyperplanes. As explained previously, a plurality of hyperplanes or hyperplane relations define each region-defining relation. Furthermore, each region is associated with an index and each index is associated with a control law. The control law may for example be a piecewise affine function, and may have the following form:

The task is to determine the index i or corresponding region in order to obtain the control law to be applied to the system in the next instance of control.

According to the first example parallel sequential direct search is

contemplated. Regular sequential direct search involves sequentially evaluating all regions in a linear search until the region in which the current state is contained can be determined. The evaluation is obtained by utilising the current state in the region-specific relations to determine whether the relation is fulfilled by means of the current state. Regions may for example be defined by the following region-specific relations:

#i : = {x E R ⁿ : GiX≤ gt ) where Gi is an m*n matrix and gi is a m*i vector, and where the matrix elements in each row of Gi define coefficients of a hyperplane relation, i.e. an equation describing a hyperplane. According to one variation of the parallel sequential direct search a subset of regions are assigned to the different threads in off-line mode, i.e. a subset of regions is assigned to each

computation unit 3a,...,3η. Each thread proceeds with a direct search among the regions that it has been assigned to in online mode. Given n computation units and N regions, in the parallel algorithm each computation unit 3a,...,3η will have N/n regions assigned leading to a linear speed up. The approach is very attractive if executed on a graphics processing unit (GPU) where n is in the range of several hundreds and graphics memory access is fast. The method according to the described example is illustrated in Fig. 2 and steps thereof as performed by a computation system comprising a plurality of computation units will shortly be described herebelow. In a step a) a current state of the system is determined. The current state corresponds to a point in state space. The current state can for example be determined by means of measurement data received from one or more sensors and/ or by estimation.

In a step b) an index of that region which comprises the current state by determining a region-specific relation that is fulfilled with respect to the current state is determined. Step b) of determining of the index is performed in a parallel manner by means of a plurality of computation units such that the current state is evaluated with respect to at least two different region- specific relations in parallel.

When the index has been determined, a control law associated with the index is determined in a step c). This may for example be performed by comparing the index with a corresponding control law in a look-up table. In a step d) the control law is applied for controlling the system. The algorithm may be iterated in each sampling instance.

According to one variation the regions are evenly distributed between the number of parallel processes performed in the step of determining of the index. Thus, each computation unit may be arranged to perform sequential direct search on a specific computation unit-assigned set of regions.

According to one variation of the parallel direct search method as described above, the parallel direct search is combined with a truncated tree search, e.g. a truncated binary tree search. Such a truncated tree comprises a root node and a plurality of subnodes, of which some are leaf nodes, thereby forming a tree structure. Each node is associated with a plurality of regions. Leaf nodes, i.e. nodes without children nodes or subnodes, are also associated with a plurality of regions. According to this variation, evaluation of the current state determined in step a) is performed with respect to each hyperplane associated with a respective node until reaching a leaf node. Direct parallel search, i.e. step b), is thereafter performed. In particular, in a step a') a leaf node associated with the region in which the current state is contained is determined, wherein the step b) of determining is performed on regions associated with the leaf node. The step a') of determining may comprise determining at each node leading to the leaf node whether the current state is contained in a first portion of the state space or in a second portion of the state space with respect to a respective hyperplane associated with each node leading to the leaf node. This may in particular be performed by evaluating the current state with respect to respective hyperplane relations. According to one variation of the truncated tree variation, about 10-30% of the hyperplanes may be orthogonal hyperplanes and the remaining

hyperplanes are region-defining hyperplanes. As mentioned previously, a region-defining hyperplane is a hyperplane which together with other region- defining hyperplanes forms a region. Region fragmentation is one of the main sources of the heavy, often-impractical, off-line computation needed for tree creation. Truncated tree search, by using region-defining hyper-planes, is less prone to region fragmentation when compared to orthogonal truncated binary tree search (OTBST); however, computing on which side a region resides with respect to a region-defining hyperplane is more time-consuming than for OTBST. Oppositely, OTBST causes more region fragmentation, but region evaluations with respect to hyperplanes is more light-weight than truncated BST. With region fragmentation is meant a situation in which an individual region ends up to be split in several sub-regions, each belonging to different leaves of the tree. By utilising both orthogonal and region-defining hyperplanes these two worlds are united by using only a small fraction of defining hyperplanes that are often sufficient to mitigate the region fragmentation problem while not causing a significant overhead in the pre- computation.

Since the number of hyperspaces forming regions is not constant for all regions, i.e. the number of equations making up the inequalities defining the regions, a speed-up of the method can be achieved by distributing the regions using the number of inequalities as a measure for the average time needed to test whether the query point belongs to a region. Optimal or nearly optimal distribution schedules can then be derived by solving associated makespan minimization problems. With reference to Figs 3a and 3b, another example of a control method implementable by a control system for controlling a system or a process by means of parallel piecewise strategies will be described. This example concerns a parallel subdivision walk strategy. Parallel subdivision walk proceeds by selecting a plurality of seed points x _S i, x _S 2, x _S 3,...Xsn, as illustrated in Fig. 3b, one for each thread and thus one for each computation unit

3a,...3η, in the state space 7 from where all the queries start. Given a current state reading x, the solution traces a respective ray in the state space from the seed point x _S i, x _S 2, x _S 3,.--¾n to x and checks sequentially all the regions that are intersected by the ray. Thus, according to the example in Fig. 3b, regions R ₅ and RN are the regions that are evaluated. An easy and effective way of exploiting parallelization is thus to scatter a set of seed points in state space. Each seed point is assigned to a computation unit that proceeds with the subdivision walking algorithm independently from the other computation units. Since multiple seed points can cover the state space in a more effective way than a single seed point, the path from the query point and its nearest seed point will be significantly shorter. The example may be described by means of the flowchart in Fig 3a. In a step A) a current state of the system is determined. As already mentioned above, the determining of the current state may be made based on measurement data and/or estimation.

In a step B) a plurality of seed points Xsi> Xs2j s3v sn 2U"6 selected in state space 7. Each seed point Xsi, Xs2, Xs3,...Xsn is associated with a respective computation unit of the control system which implements the method.

In a step C) a respective ray 9a, 9b, 9c, 9d is traced from each seed point x _sl , Xs2, Xs3,.--Xsn to the current state x. The tracing comprises determining respective indexes associated with regions that are traversed by the respective ray 9a, 9b, 9c, 9d and determining which index is associated with that region which contains the current state. The tracing of the rays is performed in a parallel manner. The tracing is performed until an index associated with that region which contains the current state is determined. .

In a step D) a control law associated with the index associated with that region which contains the current state is determined. In a step E) the system is controlled based on the control law.

According to one variation of the parallel subdivision walking, step B) of selecting a plurality of seed points comprises selecting at least one seed point to be located in the region in which the last previous current state was located. One seed point may for example be set to the previous current state. According to one variation all the seed points may change at each time step of the control operations. The seed points may for example be statistically chosen based on previous current states. The seed points may alternatively be selected statistically off-line, in which case they would not change in online mode. With reference to Figs 4a-6b an example of a control method implementable by a control system for controlling a system or a process by means of parallel piecewise strategies will be described in detail. In general, the example and its variations are based on one or more tree structures, for example binary tree structures. Each tree comprises a plurality of nodes of which one node is a root node wherein the remaining nodes are subnodes. Some of the nodes are leaf nodes, i.e. nodes which have no children. The example has three main variations briefly summarised in this paragraph, and further elaborated below. In a first variation current state evaluation with respect to several tree structures is performed in parallel. All tree structures may be associated with all regions, whereas in another variation thereof each tree structure has associated therewith a unique set of regions. In a second variation several nodes at different node levels in the same tree structure are evaluated in parallel. In the first two variations, each node is associated with only one hyperplane. In the third variation, at least some nodes are associated with several hyperplanes, wherein parallel evaluation is carried with respect to each hyperplane associated with a node.

Generally the method comprises a step I of determining a current state of the system. As already mentioned above, the determining of the current state may be made based on measurement data and/ or estimation.

In a step II one or more first area(s) in which the current state is contained in the state space is/are computed. In step II either i) a first area is computed wherein the first area is defined by at least two hyperplanes associated with a common node of a tree structure, or ii) a respective first area in which the current state is contained for each of at least two hyperplanes associated with a respective node of at least two tree structures is computed. In each case i) and ii) the step II of computing is performed in parallel. In case the first area does not correspond to a region to thereby obtain the index of that region, a step Ila of computing a second area is performed. The second area is contained within each first area in which the current state is contained in state space with respect to at least one hyperplane associated with a subnode of the node in case of i) or nodes in case of ii). In step Ila of computing, the algorithm moves through further subnodes of the tree structure in case the second area does not correspond to a region. For each further subnode a subarea of all previous areas is computed utilising at least one hyperplane associated with the further subnode until an index of the that region which comprises the current state is determined, as shown in Fig. 4b.

In Fig. 5a an example of a state space 8 subdivided into regions R1-R4 is depicted. The state space 8 is subdivided into the four regions R1-R4 by means of region-defining hyperplanes hi-h3. Fig. 5b shows a tree structure of binary type. For a given current state x, the portion of state space 8 in which the current state x lies is determined by hyperplane relation evaluation in step II and step Ila in case the region cannot be determined in step II. Thus in the example in Fig. 5b given the depicted offline mode determined tree structure the current state x is evaluated with respect to hyperplane hi and the hyperplane relation by which it is defined. The first area in the present example is defined by regions R2 and R4, i.e. to the right of hyperplane h2 when studying Fig. 5a. Since the first area does not correspond to the region in which the current state x is contained, i.e. region R2, the algorithm continues in step Ila. In this case the current state x is evaluated with respect to hyperplane h2 and the hyperplane relation which it is defined by. It can be concluded that the region in which the current state lies is region R2 which is above the hyperplane h2 as seen in Fig. 5a.

When the index associated with the region in which the current state lies, a control law associated with the index is determined in a step III. In a step IV the system is controlled based on the control law. The method is typically repeated in each sampling instance.

As noted above, one variation utilises at least two tree structures. In this case each of the at least two tree structures is associated with all regions. In case the tree structures are truncated trees, the regions resulting from the parallel tree search from each tree may be intersected by means of a mathematical or logical intersection operation. Thereby, the number of regions in which the current state may be contained can be reduced before e.g. a direct search or parallel direct search is carried out on the remaining regions. Alternatively, each structure may be associated with its own unique set of regions.

One of the main drawbacks of the tree-based methods of the first type mentioned in the paragraph above is the heavy overhead spent in the creation of (multiple) tree(s). The root cause resides in the region fragmentation caused by the use of hyperplanes that do not define regions, for example orthogonal hyperplanes. The following method may be utilised in an offline mode for creating N binary tree structures:

1. Create the i-th (orthogonal) binary search tree (BST) by: a. Choosing a hyperplane H and compute the set of regions belonging to one side of the hyperplane H+, the other side H- or both. b. Regions that are fragmented, i.e. that belong to both sides H+ and H-, are discarded for the creation of the current tree structure so to minimize fragmentation. c. Iterating the steps la and lb as in traditional (orthogonal) BST creation, which is well-known and will not be elaborated any further herein.

2. Discarded regions are re-considered for the i+i-th binary tree structure.

3. If after N trees there are still some discarded regions pending, each one is processed as follows: a. For each remaining discarded region Ri , evaluate the number of subregions that it gets fragmented to in each of the N trees. b. Place region Ri in the tree in which the region gets the least fragmentation. The multiple trees thus created can then be evaluated in parallel. It should be noted that oppositely to the parallel multiple tree approach in which all trees are associated with all regions, here each region belongs to one and only one tree. Therefore, any truncated leaf of the different trees should be direct- searched or parallel direct searched to return the sought-after region, i.e. the region in which the current state resides.

Steps II) and Ila) of computing may according to one variation be performed in parallel. Thus, several levels of nodes may be evaluated in parallel. For example by utilising three computation units each of the nodes in levels Li and L2 in the tree structure in Fig. 5b may be evaluated in parallel.

According to one variation, a tree structure comprises a node having 2 ^N branches, N being a number corresponding to the number of hyperplanes associated with the node. The number N also corresponds to the number of computation units utilised for parallel evaluation of the current state with respect to the N hyperplanes. Thus, step II of computing comprises

evaluating all hyperplanes associated with the node in parallel. An example of this variation is depicted in Figs 6a and b. According to the example the current state is evaluated with respect to two hyperplanes, hyperplane hi and hyperplane h2, in the node. This way, regions Ri, and R3-4 can immediately be determined, while further evaluation would be necessary in case the current state is in an area which is further subdivided. In the example in Figs 6a-b, the first area would correspond to the upper right corner area

comprising regions R.2 and a portion of region R4, and a second area corresponds to region R.2. In the example, the algorithm does not have to continue after the second step.

The inventive concept has mainly been described above with reference to a few examples. 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 inventive concept, as defined by the appended claims. It should be noted that in many cases the examples provided herein may be combined. Parallel direct search may for example be provided in any example which comprises leaf nodes associated with a plurality of regions. Moreover, parallel subdivision walking may be utilised for region search for truncated trees. Thus, when a leaf node of a truncated tree has been determined, parallel subdivision walking as disclosed herein may be performed to determine the region in which the current state is located.