JP7622760B2 - Movement prediction method and program - Google Patents

Description

This disclosure relates to technology that uses map data to predict the movement of objects.

Patent Document 1 discloses a mobile robot system that includes historical map data in which the positions and speed information of objects that have moved within a specified period of time are recorded on map data showing the robot's movement space, reads from the historical map data speed information recorded in positions near a moving object appearance point where a moving object may appear, and determines the shape of a collision danger area according to the read speed information. Patent Document 1 also discloses setting a base ellipse that contains all the speed vectors recorded in the historical map data at a position directly below the moving object appearance point as the collision danger area.

Other documents that demonstrate the technical level of this technical field include the following Patent Documents 2 and 3.

International Publication No. 2015/072002 JP 2021-098492 A JP 2016-052835 A

In recent years, technology that allows vehicles and robots to operate autonomously has been attracting attention. These technologies require accurate prediction of the movement of objects recognized by external sensors. As a result, technology that predicts object movement using map data has been developed.

By the way, how an object will move in the future is thought to be greatly influenced by how the object has moved in the past. For example, a pedestrian who has been moving straight forward up until now is likely to continue moving straight, but is unlikely to start moving backwards.

By applying the technology disclosed in Patent Document 1, it is possible to predict the range of movement of an object using a base ellipse centered on the object's position. However, because the base ellipse is generated from speed information recorded in map data (historical map data) for the position directly below the object, it is not possible to take into account how the object has moved in the past. For this reason, there is a risk that the base ellipse will be excessively wide compared to the range in which the object actually moves. In addition, there is a risk that the prediction of object movement using the base ellipse cannot be performed with sufficient accuracy when targeting an object that does not move in a straight line.

In view of the above problems, one objective of the present disclosure is to propose a technology that improves the accuracy of predictions regarding a technology for predicting the movement of an object using map data.

The first aspect of the present disclosure relates to a movement prediction method that predicts the movement of a target object using map data.

In the movement prediction method according to the first aspect, map data is divided into a plurality of regions, and the movement history of one or more moving objects is recorded for each of the plurality of regions, and the movement history includes the history of the movement direction of one or more moving objects classified by the direction of arrival. The movement prediction method according to the first aspect includes: calculating the presence probability that the target object is located inside each of a plurality of neighboring regions in the vicinity of the target object among the plurality of regions at a predetermined time step; and calculating the movement prediction distribution of the target object during a predetermined period based on the distribution of the plurality of neighboring regions in which the presence probability is not zero, and the calculating the presence probability includes: acquiring the transition probability of moving from the first region to the second region based on the relative direction of the second region among the plurality of neighboring regions to the first region among the plurality of neighboring regions and the history of the movement direction recorded in the first region, in each time step; and calculating the presence probability of the second region in the current time step based on the presence probability calculated for the first region in the previous time step and the transition probability acquired in the current time step.

The second aspect of the present disclosure relates to a movement prediction program that causes a computer to execute the movement prediction method according to the first aspect.

According to the present disclosure, the presence probability is calculated for each of multiple neighboring regions near the target object at a predetermined time step. Then, based on the distribution of regions with a non-zero presence probability at each time step, a predicted distribution of the movement of the target object over a predetermined period of time is calculated. This makes it possible to obtain the time evolution of the distribution and to take into account how the target object has moved at each time step. This in turn makes it possible to improve the accuracy of prediction of the target object.

FIG. 2 is a conceptual diagram for explaining map data according to the embodiment. FIG. 13 is a conceptual diagram showing some examples of the history of the moving direction. FIG. 13 is a conceptual diagram for explaining an example of calculation of the existence possibility. FIG. 11 is a conceptual diagram for explaining a movement prediction distribution. 1 is a block diagram showing a configuration of a processing device according to an embodiment of the present invention; 11 is a flowchart illustrating an example of a process executed by a processor.

The following describes the embodiment with reference to the drawings.

1. Map Data The movement prediction method according to this embodiment predicts the movement of an object (target object) using map data. In the movement prediction method according to this embodiment, the map data used is distinctive.

The map data according to this embodiment is divided into multiple regions, and the movement history of one or more moving objects (hereinafter simply referred to as "moving objects") is recorded for each of the multiple regions. Moving objects include, for example, pedestrians, bicycles, motorbikes, vehicles, etc.

An example of map data D10 is shown in FIG. 1A. FIG. 1A shows a portion of map data D10 divided by grid lines. In other words, in the map data D10 shown in FIG. 1A, the movement history of a moving object is recorded in each of a plurality of areas separated by grid lines. However, the division of the map data D10 may be applied in other formats (for example, division by a triangular mesh). Furthermore, the size of each of the plurality of areas may be suitably determined according to the environment in which this embodiment is applied. In the following, we will particularly consider map data D10 divided by grid lines. Furthermore, the areas divided by grid lines are called "cells."

In the map data D10 according to this embodiment, the movement history recorded in the cells includes at least the history of the movement direction of the moving object classified by the direction of arrival.

For example, the map data D10 can be configured to manage the history of travel directions classified by the direction of arrival for each of a number of cells in a histogram. In this case, an example of the history of travel directions will be described with reference to (B) and (C) of FIG. 1. In particular, (B) and (C) of FIG. 1 are examples in which the direction of arrival and travel directions are managed in four directions: north (N), south (S), east (E), and west (W).

As shown in FIG. 1B, assume that information has been obtained indicating that five mobile units 1a, 1b, 1c, 1d, and 1e have moved through one cell C10 on the map data D10. Mobile units 1a, 1b, and 1c arrived at cell C10 from the south and moved north from cell C10. Mobile units 1d and 1e arrived at cell C10 from the west and moved east from cell C10. Therefore, when managing the history of moving directions using a histogram, the map data D10 adds 3 to the frequency of the arrival direction being south and the moving direction being north for cell C10, and adds 2 to the frequency of the arrival direction being west and the moving direction being east for cell C10.

Figure 1 (C) shows an example of a history of movement directions managed by a histogram.

By recording the history of the movement direction for each of the multiple cells in this way, the map data D10 can manage the empirical movement direction tendencies of mobile objects moving through each point on the map. In particular, in this embodiment, the movement direction history is categorized by the direction of arrival. This allows the map data D10 to further manage the movement direction tendencies according to the direction of arrival.

For example, according to the movement direction history shown in Figure 1 (C), it can be seen that in this cell, moving bodies coming from the south tend to move north, and moving bodies coming from the west tend to move east. Furthermore, it can be seen that in this cell, there are almost no moving bodies coming from the north or east.

In the map data D10 according to this embodiment, the history of the moving direction may be further classified by the category of the moving object. This allows the map data D10 to further manage the tendency of the moving direction according to the category of the moving object. FIG. 2A shows an example of the history of the moving direction further classified by the category of the moving object. FIG. 2A shows an example of the case where the history of the moving direction is classified into three categories of the moving object, namely, pedestrians, vehicles, and motorcycles. According to the history of the moving direction shown in FIG. 2A, it can be seen that in this cell, pedestrians tend to arrive from the east and move to the west, and vehicles or motorcycles tend to arrive from the south and move to the north or west.

In the map data D10 according to this embodiment, the history of the moving direction may be further classified by the speed zone (passing speed zone) at which the moving object passes through the cell. This allows the map data D10 to further manage the tendency of the moving direction according to the speed of the moving object. FIG. 2B shows an example of the history of the moving direction classified by the passing speed zone of the moving object. FIG. 2B shows an example in which the history of the moving direction is classified by three passing speed zones of 0-10 km/h, 10-20 km/h, and 20-3 km/h. According to the history of the moving direction shown in FIG. 2B, it can be seen that in this cell, moving objects with a speed of 0-10 km/h or 10-20 km/h tend to arrive from the north and move to the south, and moving objects with a speed of 20-30 km/h tend to arrive from the south and move to the north.

The map data D10 according to this embodiment is configured as described above. However, the direction of arrival and the direction of movement may be in other formats. For example, the map data D10 may be configured to manage the direction of arrival and the direction of movement with an azimuth angle of 0-360 degrees. For example, the map data D10 may be configured to manage the direction of arrival and the direction of movement by identifying the cell before arrival and the cell to which the movement is to be made, respectively. For example, the map data D10 may be configured to manage the direction of movement according to the range of movement of the mobile object during a certain period of time after arrival at the cell. For example, the map data D10 can manage the history of the direction of movement with a two-dimensional histogram (heat map) as shown in FIG. 2C. The two-dimensional histogram shown in FIG. 2C is the history of the direction of movement recorded for the cell at the center position (star mark), and shows the frequency of the cells through which a mobile object arriving from the south passed during a certain period of time.

2. Movement Prediction Method Hereinafter, a movement prediction method according to this embodiment will be described.

In the movement prediction method according to this embodiment, first, for each of the multiple cells on the map data D10 that are in the vicinity of the target object (hereinafter simply referred to as "nearby cells"), the presence probability that the target object is located inside is calculated at a predetermined time step.

An example of calculating the existence probability is described below with reference to Figure 3.

Figure 3A is a conceptual diagram showing a neighboring cell C20 of the target object 2. Figure 3A shows the existence probability p[(i, j), t] for each cell (i, j) of the neighboring cell C20 when the time step is t. The range of the neighboring cell C20 may be, for example, a range that is predefined based on the position of the target object 2. In this case, the defined range may be different depending on the category of the target object 2. Alternatively, the range of the neighboring cell C20 may be a range that is determined depending on the state (e.g., speed) of the target object 2.

At each time step, first, for each cell (i, j) of the neighboring cells C20, the possibility of moving to another cell from the previous time step to the current time step (hereinafter simply referred to as "transition possibility") is obtained. When one of the neighboring cells C20 is the first cell and the other cell is the second cell, the transition possibility from the first cell to the second cell is obtained based on the relative direction of the second cell with respect to the first cell and the history of the movement direction recorded in the first cell.

For example, consider the case where a transition possibility for cell (2,3) is obtained at time step t. In particular, assume that the map data D10 manages the history of movement directions as described in FIG. 1. In this case, as shown in FIG. 3B, it is possible to obtain a transition possibility f to cell (2,3) and its adjacent cells (2,2), (1,3), (2,4), and (3,4). In this case, when focusing on the movement from cell (2,3) to cell (2,2), the relative direction of cell (2,2) with respect to cell (2,3) is west. Therefore, the transition possibility f[(2,3)→(2,2),t] from cell (2,3) to cell (2,2) is given by:
The frequency of moving from cell (2, 3) to the west can be obtained from the history of the moving direction recorded in cell (2, 3) as shown in FIG. 1C. The transition probability f to each of cell (1, 3), cell (2, 4), and cell (3, 4) can be obtained in the same manner.

Here, the relative direction may be specified according to the format of the direction of arrival and the direction of movement in the map data D10. For example, if the map data D10 manages the direction of arrival and the direction of movement with an azimuth angle of 0-360 degrees, the relative direction may be specified with an azimuth angle of 0-360 degrees. The transition possibility may be expanded to include movement to non-adjacent cells. Furthermore, the transition possibility may be obtained for movement to the same cell (not to another cell). However, it is desirable that the transition possibility f obtained for a certain cell (i, j) satisfies the following formula. Here, x is a variable that moves through all cells (which may include cell (i, j)) that are expected to be the destination of cell (i, j) from the previous time step t-1 to the current time step t.

Then, at each time step, for each of the neighboring cells C20, the presence probability at the current time step is calculated based on the presence probability calculated at the previous time step and the transition probability obtained at the current time step.

For example, consider the case where the existence probability of cell (2, 2) is calculated at time step t. Here, for each cell (i, j) of the neighboring cell C20, the transition probability f to the adjacent cell is acquired as described in FIG. 3B. In this case, the existence probability p[(2, 2), t] of cell (2, 2) at the current time step t is calculated based on the existence probability p calculated at the previous time step t-1 for each of the adjacent cells (2, 1), (1, 2), (2, 3), and (3, 2) and the transition probability f to cell (2, 2) acquired at the current time step t, as shown in FIG. 3C. For example, for each of the adjacent cells (2, 1), (1, 2), (2, 3), and (3, 2), the product of the existence probability p calculated at the previous time step t-1 and the transition probability f to cell (2, 2) acquired at the current time step t is calculated, and the sum of the products calculated for each can be set as the existence probability p[(2, 2), t].

Generalizing, for each cell (i, j) in the neighboring cell C20, the probability of existence p[(i, j), t] when the time step is t can be calculated using the following formula. Here, y is a variable that moves through all cells (which may include cell (i, j)) that are expected to arrive at cell (i, j) from the previous time step t-1 to the current time step t.

The product p[y→(i,j),t] of f[y→(i,j),t] and p[y,t-1] can be considered as the possibility of arrival from y to cell (i,j) from the previous time step t-1 to the current time step t (hereafter referred to as "arrival possibility"). In other words, in the above formula, the existence possibility p[(i,j),t] is the sum of multiple arrival possibilities p[y→(i,j),t]. Furthermore, when calculating the existence possibility p[(i,j),t] in this way, the existence possibility p[(i,j),t] can be classified into multiple arrival possibilities p[y→(i,j),t].

When categorizing the existence probability p[(i,j),t] into multiple arrival probabilities p[y→(i,j),t], the magnitude of each of the multiple arrival probabilities p[y→(i,j),t] is an index showing the direction from which the target object 2 is likely to have arrived when the target object 2 is located inside the cell (i,j). In other words, it is considered to contain information about how the target object 2 has moved.

Then, the transition probability from the first cell to the second cell may be obtained based on the magnitude of each of the multiple arrival probabilities calculated for the first cell in the previous time step.

For example, consider the case where a transition possibility is obtained for cell (2, 3) at time step t. In this case, as explained in FIG. 3B, the transition possibility f[(2, 3) → (2, 2), t] from cell (2, 3) to cell (2, 2) can be expressed as the frequency of moving westward from cell (2, 3). Here, since the history of the moving direction recorded in cell (2, 3) is classified by the direction of arrival, the frequency of moving westward from cell (2, 3) can be obtained for each direction of arrival to cell (2, 3). Therefore, the transition possibility f[(2, 3) → (2, 2), t] can be expressed as a weighted average of the frequencies obtained for each direction of arrival, with the magnitude of each of the multiple arrival possibilities calculated for cell (2, 3) at the previous time step t-1 being used as the weight. Alternatively, the transition possibility f[(2,3)→(2,2),t] may include multiple transition possibilities, each of which corresponds to a multiple arrival possibility and is expressed by the frequency obtained for each arrival direction.

In the map data D10, when the history of the moving direction is further classified by the category of the moving object, the possibility of transition from the first cell to the second cell may be obtained based on the category of the target object 2. For example, when the category of the target object 2 is pedestrian, the possibility of transition is obtained by referring to the history of the moving direction in the category of pedestrian. In the map data D10, when the history of the moving direction is further classified by the passing speed zone of the moving object, the possibility of transition from the first cell to the second cell may be obtained based on the speed of the target object 2. For example, when the speed of the target object 2 is 25 km/h, the possibility of transition is obtained by referring to the history of the moving direction in the passing speed zone of 20-30 km/h.

By obtaining the transition possibility from the first cell to the second cell in this manner, it is possible to obtain an appropriate transition possibility according to the state of the target object 2. In turn, it is possible to improve the accuracy of predicting the movement of the target object 2.

As described above, in the movement prediction method according to this embodiment, the presence probability is calculated for each cell (i, j) of the neighboring cell C20 at a predetermined time step. FIG. 4A is a conceptual diagram showing an example of the presence probability calculated at each time step. In FIG. 4A, t=0 is the current time when the target object 2 is detected. As shown in FIG. 4A, the movement prediction method according to this embodiment makes it possible to obtain the time evolution of the distribution of cells related to the presence probability.

The movement prediction method according to this embodiment calculates a movement prediction distribution of the target object 2 during a predetermined period based on the distribution of cells with a non-zero probability of existence in each time step. In particular, the distribution of cells with a non-zero probability of existence may be calculated as the movement prediction distribution of the target object 2 using each time step as time information.

The movement prediction distribution calculated in this way makes it possible to obtain the time evolution of the distribution of cells related to the possibility of existence, so it is possible to take into account how the target object 2 has moved at each time step. This in turn makes it possible to improve the accuracy of prediction of the target object 2.

(B) and (C) of FIG. 4 are conceptual diagrams showing an example of the movement prediction distribution 5. (B) and (C) of FIG. 4 show a case where an autonomous vehicle 3 traveling on a road on which a guardrail 4 is arranged predicts the movement of a recognized target object 2 (pedestrian). In addition, in (B) and (C) of FIG. 4, the movement prediction distribution 5 shows a simplified range of cells whose existence probability is not zero during a predetermined period. According to the movement prediction distribution 5 shown in (B) of FIG. 4, it can be seen that there is no possibility that the target object 2 will move over the guardrail 4 and move to the road side. On the other hand, according to the movement prediction distribution 5 shown in (C) of FIG. 4, it can be seen that the target object 2 may move to the road side from the point where the guardrail 4 ends. This is, for example, a case where there are many records in the history of the movement direction that a pedestrian has moved to the road side from the point where the guardrail 4 ends. In this way, according to this embodiment, it is also possible to predict realistic and complex movements of the target object 2.

3. Configuration The movement prediction method according to the present embodiment can be realized by processing executed by a computer.

Figure 5 is a block diagram showing the configuration of a processing device 100 that realizes the movement prediction method according to this embodiment. The processing device 100 is communicatively connected to a data server 200 and an external sensor 300.

The data server 200 acquires movement history by communicating with the mobile object, and manages the acquired movement history in the movement history database D20.

The external sensor 300 is provided in an autonomous vehicle or robot and detects the surrounding environment of the autonomous vehicle or robot. In particular, the external sensor 300 recognizes surrounding objects. Examples of the external sensor 300 include a camera, a radar, and a LiDAR.

The processing device 100 is a computer including a processor 110 and a storage device 120. The processing device 100 may be, for example, a device that executes processes related to the control of an autonomous vehicle or a robot.

The processor 110 executes various processes. The processor 110 may be configured, for example, as a CPU (Central Processing Unit) including an arithmetic unit, registers, etc. The storage device 120 is coupled to the processor 110 and stores various information necessary for the processor 110 to execute its processes. The storage device 120 may be configured, for example, as a recording medium such as a ROM (Read Only Memory), a RAM (Random Access Memory), a HDD (Hard Disk Drive), or a SSD (Solid State Drive).

The storage device 120 stores a computer program 121, map data D10, and detection information D11.

The computer program 121 is composed of a plurality of instructions 122 and is stored in a computer-readable recording medium. The processor 110 operates in accordance with the plurality of instructions 122, thereby realizing the execution of various processes by the processor 110.

The map data D10 may be updated by processing executed by the processor 110. For example, the processor 110 may be configured to periodically access the movement history database D20 to update the map data D10 based on the movement history database D20.

The detection information D11 is information detected by the external sensor 300. The detection information D11 is acquired from the external sensor 300. The detection information D11 may include information such as the position, speed, and category of the target object 2 on the map.

4. Processing Fig. 6 is a flowchart showing an example of processing executed by the processor 110. The flowchart shown in Fig. 6 starts, for example, when the external sensor 300 recognizes an object (target object 2).

In step S100, the processor 110 acquires various information necessary to execute the process. For example, the processor 110 acquires the detection information D11 and the history of the movement direction related to the neighboring cell C20 of the target object 2.

In step S200, the processor 110 initializes the time step (t = 0). Then, at t = 0, the processor 110 sets the probability of existence of the cell in which the target object 2 is located among the neighboring cells C20 to 1 (step S300).

In step S400, the processor 110 increments the time step (t = t + 1).

In step S500, the processor 110 obtains the transition possibility for each of the neighboring cells C20 based on the history of the movement direction.

In step S600, the processor 110 calculates the presence probability for each of the neighboring cells C20 in the current time step based on the presence probability calculated in the previous time step t-1 and the transition probability obtained in the current time step t.

In step S700, it is determined whether the current time step t is smaller than a predetermined value T. The predetermined value T corresponds to the period for which the movement of the target object 2 is predicted, and may be suitably set.

If the current time step t is smaller than the predetermined value T (step S700; Yes), the processor 110 increments the time step (step S400) and repeats steps S500 and S600 again.

If the current time step t exceeds the predetermined value T (step S700; No), the processor 110 extracts cells whose probability of existence at each time step is not zero.

In step S900, the processor 110 calculates a predicted movement distribution of the target object 2 based on the cells extracted in step S800.

After step S900, the process ends.

As described above, the movement prediction method according to this embodiment is realized by the processing executed by the processor 110. Furthermore, by configuring the computer program 121 in this manner to cause the processor 110 to execute the processing, the movement prediction program according to this embodiment is realized.

2 target object, 5 movement prediction distribution, 100 processing device, 110 processor, 120 storage device, 121 computer program, D10 map data

Claims (5)

A movement prediction method for predicting movement of a target object using map data, comprising:
The map data is divided into a plurality of areas, and a movement history of one or a plurality of moving objects is recorded for each of the plurality of areas;
The movement history includes a history of a movement direction of the one or more moving objects categorized by a direction of arrival,
The movement prediction method includes:
Calculating a presence probability that the target object is located inside each of a plurality of neighboring regions among the plurality of regions, the plurality of neighboring regions being located near the target object, at a predetermined time step;
calculating a predicted distribution of movement of the target object during a predetermined period based on a distribution of the areas among the plurality of neighboring areas where the possibility of the object being present is not zero;
Including,
Calculating the presence probability
At each time step, acquiring a transition possibility of moving from the first region to the second region based on a relative direction of a second region among the plurality of neighboring regions with respect to a first region among the plurality of neighboring regions and a history of the moving direction recorded in the first region;
Calculating the presence probability for the second region in a current time step based on the presence probability calculated for the first region in a previous time step and the transition probability acquired in a current time step;
A movement prediction method comprising: The movement prediction method according to claim 1 ,
The presence probability is a sum of a plurality of arrival probabilities classified by the arrival direction,
The movement prediction method, characterized in that obtaining the transition probability further includes obtaining the transition probability based on a magnitude of each of the plurality of arrival probabilities calculated for the first region in a previous time step. The movement prediction method according to claim 1 or 2,
The history of the moving direction is further categorized by the category of the one or more moving objects;
The movement prediction method, wherein obtaining the transition possibility further includes obtaining the transition possibility based on a category of the target object. The movement prediction method according to claim 1 or 2,
The history of the moving direction is further classified by a passing speed band of the one or more moving objects,
The movement prediction method, wherein obtaining the transition possibility further includes obtaining the transition possibility based on a speed of the target object. A movement prediction program for causing a computer to execute a process of predicting movement of a target object using map data,
The map data is divided into a plurality of areas, and a movement history of one or a plurality of moving objects is recorded for each of the plurality of areas;
The movement history includes a history of a movement direction of the one or more moving objects categorized by a direction of arrival,
The movement prediction program includes:
A process of calculating a presence possibility that the target object is located inside each of a plurality of neighboring regions in the vicinity of the target object among the plurality of regions at a predetermined time step;
A process of calculating a movement prediction distribution of the target object during a predetermined period based on a distribution of the areas among the plurality of neighboring areas where the existence probability is not zero;
The method is configured to cause the computer to execute
Calculating the presence probability
At each time step, acquiring a transition possibility of moving from the first region to the second region based on a relative direction of a second region among the plurality of neighboring regions with respect to a first region among the plurality of neighboring regions and a history of the moving direction recorded in the first region;
Calculating the presence probability for the second region in a current time step based on the presence probability calculated for the first region in a previous time step and the transition probability acquired in a current time step;
A movement prediction program comprising:

Images