JP7206784B2 - Movement path estimation device, movement path estimation method, and program - Google Patents

Description

Application of Article 30, Paragraph 2 of the Patent Act May 22, 2018 https://www. ai-gakkai. or. jp/jsai2018/https://conf. atlas. jp/guide/event/jsai2018/tophttps://conf. atlas. jp/guide/event/jsai2018/subject/3J1-04/tables? cryptoId=https://conf. atlas. jp/guide/event-img/jsai2018/3J1-04/public/pdf? Published on type=in August 7, 2018 Published in a paper presented by the Network Emerging Intelligence Study Group + Network Ecology Group Joint Study Group (JWEIN + NetEco2018)

TECHNICAL FIELD The present invention relates to a movement route estimation device, a movement route estimation method, and a program, and in particular, estimates a movement route of an agent that matches observation based on the observed number of people at a certain point obtained for each time period. The present invention relates to a moving route estimation device, a moving route estimation method, and a program.

In order to cope with the congestion that can occur at large-scale events, etc., multi-agent simulators (MAS) are being used to grasp the flow of people and formulate control measures. High-precision simulations are necessary for a more accurate understanding of the flow of people and the formulation of effective control measures. For that purpose, it is essential to have a technique to determine parameters for reproducing the observed data based on the observed data.

としたときに、ある時刻

から時刻

までの時間帯

にある観測地点ｋで観測された通行人数

が得られる。 Observation data refers to aggregated data measured with a certain granularity in terms of time and space. Specifically, as shown in Fig. 9, the time span of observation is

at a certain time

time from

time to

The number of passers-by observed at observation point k in

is obtained.

を、全時間帯分つないだＩ×Ｊ次元ベクトル

である。 Also, as shown in FIG. 10, MAS is executed by designating the time of occurrence, starting point, destination, and route through each agent, and outputs the passing node and passing time of each agent. . A parameter is, as shown in FIG. 11, a vector in which the number of agents passing through a route R _i in a given time period T _j is arranged.

are connected for all time zones, and an I×J-dimensional vector

is.

と、実際の観測値

との誤差を最小化するという問題は、ブラックボックス関数最適化の問題と捉えることができ、最適化手法の従来技術としてベイズ最適化（非特許文献１）がある。 Observed values obtained by aggregating MAS outputs

and the actual observed value

The problem of minimizing the error with can be regarded as a problem of black-box function optimization, and there is Bayesian optimization (Non-Patent Document 1) as a prior art of optimization methods.

The optimization method is an approach in which a parameter to be searched and an objective function are set in advance, objective function values for the parameters are sequentially obtained, the objective function is approximated, and the parameter that gives the minimum value is searched.

For this problem, two naive settings can be considered depending on how the input parameters and the objective function are determined. Image diagrams of each are shown in FIGS. 12 and 13. FIG.

を要素とするＩ×Ｊ次元ベクトル

”、目的関数を“全時間帯、各観測地点ｋにおける観測誤差”と設定するものである。ここで、時間帯

から時間帯

までの誤差を下記式（１）であらわすとすると、設定１では下記式（２）の最適化問題を解くことでパラメータ

を求める。 The first naive setting (setting 1) shown in FIG.

An I×J dimensional vector whose elements are

”, and the objective function is set as “observation error at each observation point k for all time periods”.

time zone from

If the error up to is expressed by the following formula (1), in setting 1, the parameter can be obtained by solving the optimization problem of the following formula (2)

Ask for

を要素とするＩ次元ベクトル

”、目的関数を“一つの時間帯Ｔ_ｊ、各観測地点ｋにおける観測誤差”と設定するものである。 The second naive setting shown in FIG. 13 (hereinafter referred to as setting 2) sets the input parameter as “the number of agents passing through each route _Ri in one time period _Tj .

An I-dimensional vector whose elements are

”, and the objective function is set as “one time period T _j , observation error at each observation point k”.

を求める。 That is, in setting 2, the parameter

Ask for

J.Snoek, H.Larochelle, and R.P.Adams. Practical Bayesian optimization of machine learning algorithms. In Advances in Neural Information Processing Systems (NIPS), 2012. Nello Cristianini, John Shawa-Taylor, Tsuyoshi Ohkita (Translation): Pattern Analysis by Kernel Method (2010).

Setting 1 is a technique that performs Bayesian optimization by using the number of agents passing through all routes at all times as input values. However, in this formulation, the number of dimensions of the parameters becomes too large, and the approximation accuracy of the objective function deteriorates. Therefore, it becomes difficult to search for an efficient solution.

On the other hand, in setting 2, since the number of input dimensions is the number of movement paths, the problem of the number of dimensions does not occur. This setting is natural if the agent arrives at the observation point within the time period of occurrence. This is because arriving within the same time slot means that the agents generated at each time will only affect the observation error in the same time slot. An example of this is moving between booths in a small venue.

However, considering a large-scale event, it is not always possible to assume arrival within the same time zone as the time of occurrence. For example, as shown in FIG. 14, let us consider the case where the agent occurred at Departure 2 at 8:02 and heads for Destination 12 . At this time, if the observation interval is 5 minutes, the agent will be observed at the observation point (3) within the same time, but at the observation point (10), it will take some time from occurrence to observation, and it will be observed in the next time slot. end up As in this example, when the observation point is distant from the place of occurrence, there is a time lag between the agent's occurrence time zone and the observation time zone. In other words, it is necessary to consider that the observation error that the agent affects spans several time periods. In such a case, the conventional technology has a problem that it is difficult to adapt.

SUMMARY OF THE INVENTION The present invention has been made in view of the above points. An object is to provide an apparatus, a moving route estimation method, and a program.

A moving route estimation apparatus according to the present invention, for each of a plurality of routes in a real environment, based on an input parameter whose element is the number of agents passing through the route in an estimation target time zone, a plurality of of the agent moves, and from the results of the simulation, the agent is calculated for each observation point in a predetermined number of time periods including the time period to be estimated and the time period following the time period to be estimated. a simulator execution unit that calculates an objective function representing an observation error between a value and an observed value in a real environment; and a next input that determines the next input parameter based on the input parameters and the calculation result of the objective function. and an optimization control unit that repeats the execution by the simulator execution unit and the determination by the next input parameter determination unit until a predetermined repetition condition is satisfied, and obtains input parameters for optimizing the objective function. and

Further, in the movement route estimation method according to the present invention, the simulator execution unit, for each of a plurality of routes in the real environment, is based on an input parameter whose element is the number of agents passing through the route in the estimation target time period. a simulation in which a plurality of agents move in each time slot, and from the results of the simulation, in a predetermined number of time slots including the estimation target time slot and the time slot next to the estimation target time slot, the number of observation points a step of calculating an objective function representing an observation error between a calculated value for each of the agents and an observed value in a real environment; The step of determining the next input parameter based on the above; determining input parameters that optimize the objective function.

According to the movement route estimation device and movement route estimation method according to the present invention, the simulator execution unit regards each of a plurality of routes in the real environment as an element, the number of agents passing through the route in the estimation target time period. Based on the input parameters, a simulation is performed in which a plurality of agents move in each time period, and from the results of the simulation, a predetermined number of time periods including the estimated target time period and the time period next to the estimated target time period. , an objective function representing an observation error between the calculated value for the agent at each observation point and the observed value in the real environment is calculated.

Then, the next input parameter determination unit determines the next input parameter based on the input parameter and the calculation result of the objective function, and the simulator until the optimization control unit satisfies a predetermined repetition condition. The execution by the execution unit and the determination by the next input parameter determining unit are repeated to obtain input parameters that optimize the objective function.

In this way, from the simulation results, in a predetermined number of time periods including the time period to be estimated and the time period next to the time period to be estimated, the calculated values for the agent and the observed values in the real environment for each observation point and determining the next input parameter based on the input parameter and the calculation result of the objective function, and determining the input parameter that optimizes the objective function. As a result, it is possible to efficiently estimate an agent's course of action that reduces the observation error even under conditions where time delays occur.

Further, the moving path estimation apparatus according to the present invention further includes an iterative control unit that repeats obtaining the input parameters by the optimization control unit with each of all the time periods as the estimation target time period, The iterative control unit can cause the optimization control unit to repeatedly obtain the input parameter by using each of all the time periods as the estimation target time period until a predetermined repetition condition is satisfied. .

In this way, each of all time periods is set as an estimation target time period, and the input parameters are repeatedly obtained until a predetermined repetition condition is satisfied. By executing this method, it is possible to accurately estimate an agent's action path that reduces the observation error, even under conditions where time delays occur.

In addition, the simulator execution unit in the moving route estimation device according to the present invention includes, among all the time slots, a predetermined number of time slots before the estimation target time slot, the estimation target time slot, and the estimation target time slot. The simulation can be performed in which a plurality of agents move during a predetermined number of time periods, including the following time periods.

In this way, among all the time slots, a plurality of agents are used in a predetermined number of time slots including a predetermined number of time slots before the estimation target time slot, an estimation target time slot, and a time slot next to the estimation target time slot. By simulating the movement of the agent, it is possible to estimate the action path of the agent at high speed so as to reduce the observation error, even under conditions where time delay occurs.

A program according to the present invention is a program for functioning as each part of the moving route estimation device.

According to the movement path estimation device, movement path estimation method, and program of the present invention, it is possible to efficiently estimate an agent's action path so as to reduce observation errors even under conditions where time delays occur. can.

BRIEF DESCRIPTION OF THE DRAWINGS It is an image figure which shows the outline|summary of the 1st Embodiment of this invention. 1 is a block diagram showing the configuration of a moving route estimation device according to a first embodiment of the present invention; FIG. 4 is a flow chart showing a moving route estimation processing routine of the moving route estimation device according to the first embodiment of the present invention; 4 is a flow chart showing an optimization processing routine of the moving route estimation device according to the first embodiment of the present invention; It is an image figure which shows the outline|summary of the 2nd Embodiment of this invention. FIG. 2 is a block diagram showing the configuration of a moving route estimation device according to a second embodiment of the present invention; FIG. 9 is a flow chart showing a moving route estimation processing routine of the moving route estimation device according to the second embodiment of the present invention; It is an image figure which shows the outline|summary of the 3rd Embodiment of this invention. It is an example of a road network and observation data. It is an example of input and output of MAS. It is an example of an input parameter. This is an example of a conventional naive input/output setting (Setting 1). This is an example of a conventional naive input/output setting (setting 2). FIG. 4 is an image diagram of time delay;

BEST MODE FOR CARRYING OUT THE INVENTION Embodiments of the present invention will be described below with reference to the drawings.

<Overview of Moving Route Estimating Device According to First Embodiment of the Present Invention>
First, an outline of the first embodiment of the present invention will be described.

を要素とするＩ次元ベクトル

”とする。 In this embodiment, in order to prevent an increase in the number of input dimensions, the input parameter is set to "the number of agents passing through each route R _i in one time period T _j

An I-dimensional vector whose elements are

”.

However, unlike setting 2, the objective function uses not only the observation error in the same time period, but also the measurement error in the next time period and beyond, which is affected by the time delay. FIG. 1 is an image diagram showing an overview of this embodiment.

That is, in this embodiment, the number of agents passing through each route in each time period is obtained by solving the optimization problem of the following equation (4).

Here, D is the maximum number of time periods required from the generation of the agent until it is observed. Since D represents how long the agent will be delayed, it can be changed as appropriate according to the situation.

とすることにより、時間帯Ｔ_ｊに発生するエージェントが時間遅れによって影響を与える時間帯の観測誤差まで考慮することができるため、高精度にエージェントの移動経路を推定できるようになる。 the objective function

As a result, it is possible to consider the observation error of the time period in which the agent occurring in the time period _Tj is affected by the time delay, so that the movement path of the agent can be estimated with high accuracy.

<Configuration of moving route estimation device according to first embodiment of the present invention>
The configuration of the moving route estimation device according to the embodiment of the present invention will be described with reference to FIG. FIG. 2 is a block diagram showing the configuration of the moving route estimation device according to the embodiment of the present invention.

The movement route estimation device 100 is composed of a computer having a CPU, a RAM, and a ROM storing a program for executing a movement route estimation processing routine, which will be described later, and is functionally configured as follows. ing.

As shown in FIG. 2, the moving route estimation device 100 according to the present embodiment includes a simulator setting processing unit 110, an optimization processing unit 120, a data storage unit 130, an optimization execution unit 140, and an optimum parameter processing unit. 150, and is configured to be connected to an external device 200 such as an input device or a display device.

The simulator setting processing unit 110 sets the fields necessary for executing the simulator input from the external device 200 in the simulator setting table 131 .

The optimization processing unit 120 sets the maximum optimization execution count S, the time division number J, and the time delay constant D input from the external device 200 in the optimization setting table 132 .

The maximum optimization execution number S is the maximum number of times optimization is performed for one time slot, the time division number J is the number of divisions of the time slot in which data is observed, and the time delay constant D is the agent is the maximum number of time slots from the time of occurrence until it is observed.

The data storage unit 130 has a simulator setting table 131 , an optimization setting table 132 and an optimum parameter table 133 .

The simulator setting table 131 has fields necessary for executing the people flow simulator. Necessary fields are, for example, the road network, walking speed of the agent, and the like.

The optimization setting table 132 has a maximum optimization execution count field, a maximum repetition count field, a time zone division count field, and a time delay constant field.

The maximum optimization execution count field is set with the maximum optimization execution count S, the time division count field is set with the time division count J, and the time delay constant field is set with the time delay constant D. .

The optimum parameter table 133 is set with optimum parameters input from the optimization execution unit 140 .

を最適化する入力パラメータ

を求める。 The optimization execution unit 140 reads the settings of the simulator setting table 131 and the optimization setting table 132, and calculates the objective function

input parameters to optimize

Ask for

Specifically, the optimization execution unit 140 includes a simulator execution unit 141, a next input parameter determination unit 142, an optimization control unit 143, an optimization result storage unit 144, and a time zone optimization result storage unit 145. It has

に基づいて、各時間帯Ｔ_ｊにおいて複数のエージェントが移動するシミュレーションを実行し、シミュレーションの結果から、推定対象時間帯Ｔ_ｊ及び推定対象時間帯の次の時間帯Ｔ_ｊ＋Ｄを含む所定数の時間帯において、観測地点の各々についてのエージェントに関する計算値

と、実環境での観測値

との観測誤差を表す目的関数

を計算する。 The simulator execution unit 141 sets an input parameter, which is the number of _agents passing through the route _{Ri in the estimation target time zone Tj ,} for each of the plurality of routes Ri in the real environment.

Based on, a simulation is performed in which a plurality of agents move in each time period T _j , and from the simulation results, a predetermined number of times including the estimated target time period T _j and the next time period T _{j + D} of the estimated target time period Calculated value for the agent for each observation point in the band

and real-world observations

The objective function representing the observation error between

to calculate

に基づいて、人流シミュレータ（ＭＡＳ）を実行し、目的関数値

を算出し、

を最適化結果保管部１４４に追加する。 Specifically, the simulator execution unit 141 _sets the input parameter

based on the people flow simulator (MAS), the objective function value

to calculate

is added to the optimization result storage unit 144 .

を算出する。 Here, the people flow simulator itself performs simulations for all time zones, and the simulator execution unit 141 obtains the objective function value

Calculate

と、目的関数

の計算結果とに基づいて、次の入力パラメータ

を決定する。 The next input parameter determination unit 142 determines the input parameter

and the objective function

and based on the following input parameters

to decide.

と、目的関数値

との関係式を、例えばガウス過程による推定を行う。

とあらわされるとき、あるパラメータ

における目的関数値

は、下記式（５）であらわされる平均値

と、下記式（６）であらわされる分散値

を持つガウス分布に従う。 For example, when Bayesian optimization is used as the optimization method, the following input parameters are determined by using a stochastic model such as a Gaussian process. Specifically, the next input parameter determination unit 142 uses all the data in the optimization result storage unit 144 to determine the parameter

and the objective function value

is estimated by, for example, a Gaussian process.

When a parameter

objective function value at

is the average value represented by the following formula (5)

and the variance value represented by the following formula (6)

follows a Gaussian distribution with

However, the superscript T represents transposition of the matrix, and the superscript "-1" represents the inverse matrix. This kernel function may be changed depending on the problem. Typical kernels include linear kernels and Gaussian kernels (see Non-Patent Document 2).

であり、ｋ、Ｋは、カーネル関数と呼ばれる、パラメータ

と

との類似度を定義する関数

を用いて、下記式（７）、及び式（８）のように書くことができる。 here,

and k, K are the parameters

When

A function that defines the similarity with

can be written as the following equations (7) and (8).

を決定する。 Then, the next input parameter determining unit 142 determines the parameters to be input to the people flow simulator next according to the following formula (9).

to decide.

は獲得関数と呼ばれ、パラメータ

が最小値を与える可能性を定量的に評価するための指標である。獲得関数には、確率改善（ＰＩ）や、期待値改善（ＥＩ）などを用いてもよい。 here,

is called the acquisition function, and the parameter

is an index for quantitatively evaluating the possibility of giving the minimum value. Probability improvement (PI), expected value improvement (EI), or the like may be used as the acquisition function.

を最適化する入力パラメータ

を求める The optimization control unit 143 repeats the execution by the simulator execution unit 141 and the determination by the next input parameter determination unit 142 until a predetermined repetition condition is satisfied with the time period _Tj as the estimation target time period, and the objective function

input parameters to optimize

ask for

Specifically, first, the optimization control unit 143 initializes the optimization result storage unit 144 to an empty set.

Next, the optimization control unit 143 causes the simulator execution unit 141 and the next input parameter determination unit 142 to repeat the processing until the maximum number of optimization execution times S is exceeded in the time period _Tj .

を入力パラメータとして入力して、人流シミュレータを実行させる。 The optimization control unit 143 supplies the simulator execution unit 141 with the parameters obtained by the next input parameter determination unit 142

as an input parameter to run the people flow simulator.

を算出し、時間帯最適化結果保管部１４５に、

を格納する。ここで、Ｄａｔａは、最適化結果保管部１４４を意味する。 Then, when the iteration ends, the optimization control unit 143 minimizes the error among the input parameters stored in the optimization result storage unit 144.

is calculated, and stored in the time zone optimization result storage unit 145,

to store Here, Data means the optimization result storage unit 144 .

Then, the optimization control unit 143 initializes the optimization result storage unit 144 to an empty set, and performs similar processing using the next time period T _j+1 as the estimation target time.

を算出し、最適パラメータテーブル１３３に格納する。 When the optimization control unit 143 performs the above processing for all time periods (T ₁ to T _J ), the optimization control unit 143 collects the data contained in the time period optimization result storage unit 145 to obtain the optimum parameter

is calculated and stored in the optimum parameter table 133 .

と目的関数値

との組である

を、記憶する。 The optimization result storage unit 144 stores the input parameters in the time period _Tj obtained by the simulator execution unit 141

and the objective function value

is a pair with

to memorize.

を全て削除し、空集合にする。 Further, when the optimization control unit 143 acquires an instruction to be initialized, the optimization result storage unit 144 stores the

is deleted and becomes an empty set.

を記憶している。 The time zone optimization result storage unit 145 stores the optimum parameters in the time zone _Tj obtained by the optimization control unit 143.

Remember.

を、外部装置２００に出力する。出力処理は、例えば、外部装置２００から出力のリクエストが入力された場合等に実行すればよい。 The optimal parameter processing unit 150 uses the optimal parameters acquired from the optimal parameter table 133.

is output to the external device 200 . The output process may be executed, for example, when an output request is input from the external device 200 .

<Operation of the moving route estimation device according to the first embodiment of the present invention>
FIG. 3 is a flow chart showing a moving route estimation processing routine according to the first embodiment of the present invention.

When each setting is input to the simulator setting processing unit 110 and the optimization processing unit 120, the moving route estimation processing routine shown in FIG. 3 is executed in the moving route estimation device 300. FIG.

First, in step S100, the simulator setting processing unit 110 sets the fields necessary for executing the simulator input from the external device 200, and the optimization processing unit 120 sets the maximum optimization execution count input from the external device 200. S, the number of time divisions J, and the time delay constant D are obtained respectively.

In step S110, the simulator setting processing unit 110 sets fields necessary for executing the simulator obtained in step S100 in the simulator setting table 131. FIG.

In step S<b>120 , the optimization processing unit 120 sets the maximum optimization execution count S, the time division number J, and the time delay constant D obtained in step S<b>100 in the optimization setting table 132 .

In step S130, the optimization control unit 143 initializes the optimization result storage unit 144 (Data) to an empty set.

At step S140, j=1. _j is a counter for counting the estimation target time period Tj.

In step S150, the optimization executing unit 140 executes optimization processing.

を算出し、時間帯最適化結果保管部１４５に、

を格納する。 In step S160, the optimization control unit 143 minimizes the error among the input parameters stored in the optimization result storage unit 144.

is calculated, and stored in the time zone optimization result storage unit 145,

to store

At step S170, j=j+1.

In step S180, the optimization control unit 143 determines whether or not j is greater than the time division number J.

If j is not greater than J (NO in step S180), in step S190 the optimization control unit 143 initializes the optimization result storage unit 144 to an empty set, and repeats the processing of steps S150 to S170.

を生成し、最適パラメータテーブル１３３に格納する。 On the other hand, if j is greater than J (YES in step S180), in step S200, the optimization control unit 143 puts together the data contained in the time period optimization result storage unit 145 into an optimal parameter

is generated and stored in the optimum parameter table 133 .

を、外部装置２００に出力する。 In step S210, the optimum parameter processing unit 150 extracts the optimum parameters acquired from the optimum parameter table 133.

is output to the external device 200 .

Here, the optimization processing in step S150 will be described. FIG. 4 is a flow chart showing an optimization processing routine.

In step S300, s=1. s is a counter for counting the number of optimization times.

に基づいて、各時間帯Ｔ_ｊにおいて複数のエージェントが移動するシミュレーションを実行する。 In step S310, the simulator execution unit 141 sets an input parameter having, as an element, the number of agents passing through the route R _i in the estimation target time period T _j for each of the plurality of routes R _i in the real environment.

Based on , a simulation is performed in which a plurality of agents move in each time zone _Tj .

と、実環境での観測値

との観測誤差を表す目的関数

を計算する。 In step _S320 , the simulator execution unit 141 determines from the result of the simulation in step _S310 that each of the observation points is Calculated value for the agent for

and real-world observations

The objective function representing the observation error between

to calculate

を最適化結果保管部１４４に追加する。 In step S330, the simulator execution unit 141 calculates the

is added to the optimization result storage unit 144 .

と、目的関数値

との関係式を推定する。 In step S340, the next input parameter determination unit 142 uses all the data in the optimization result storage unit 144 to determine the parameter

and the objective function value

Estimate the relational expression with

を決定する。 In step S350, the next input parameter determining unit 142 determines the parameters to be input next to the people flow simulator according to the equation (9).

to decide.

In step S360, s=s+1.

In step S<b>370 , the optimization control unit 143 determines whether s is greater than the maximum optimization execution count S.

If s is not greater than the maximum optimization execution count S (NO in step S370), the process returns to step S310 and repeats steps S310 to S360.

If it is larger than the maximum number of optimization execution times S (YES in step S370), return.

As described above, according to the present embodiment, from the simulation results, in a predetermined number of time periods including the time period to be estimated and the time period next to the time period to be estimated, the agent is calculated for each observation point. Calculating an objective function representing an observation error between a value and an observed value in a real environment, and determining the next input parameter based on the input parameter and the calculation result of the objective function are repeated to obtain the objective By obtaining the input parameters that optimize the function, it is possible to efficiently estimate the agent's action path to reduce the observation error even under the circumstances where time delay occurs.

<Overview of Moving Route Estimating Device According to Second Embodiment of the Present Invention>
Next, the outline of the second embodiment of the present invention will be described.

FIG. 5 is an image diagram showing an overview of this embodiment. In this embodiment, the number of agents passing through each route in all time periods is finally obtained by sequentially optimizing the time periods T ₁ , T ₂ , T ₃ . . . according to the first embodiment. . In this case, after optimizing all time zones once, optimization is further performed multiple times for time zones T ₁ , T ₂ , T ₃ . . .

Since the input parameters of the time slot _Tj are affected by the agents that occurred in D preceding and succeeding time slots, even if it is the same time slot, by optimizing again after optimizing the preceding and following time slots, It is possible to improve the accuracy of agent movement route estimation.

<Configuration of Moving Route Estimating Device According to Second Embodiment of the Present Invention>
The configuration of the moving route estimation device according to the embodiment of the present invention will be described with reference to FIG. FIG. 6 is a block diagram showing the configuration of moving route estimation apparatus 300 according to the embodiment of the present invention. It should be noted that the same reference numerals are assigned to the same configurations as those of the moving route estimation apparatus 100 according to the first embodiment, and detailed description thereof will be omitted.

The optimization processing unit 320 sets the maximum optimization execution count S, the maximum repetition count R, the time division count J, and the time delay constant D input from the external device 200 in the optimization setting table 332 .

The maximum number of iterations R is the maximum number of units when the maximum number of optimization executions S is one unit.

The optimization setting table 332 has a maximum optimization execution count field, a maximum repetition count field, a time zone division count field, and a time delay constant field. The maximum number of repetitions R is set in the maximum number of repetitions field.

The optimization execution unit 340 includes a simulator execution unit 141, a next input parameter determination unit 142, an optimization control unit 143, an optimization result storage unit 144, a time zone optimization result storage unit 145, and an iteration control unit 346. It has

The iteration control unit 346 causes the optimization control unit 143 to repeat obtaining the input parameters with each of all the time periods (T ₁ to T _J ) as the estimation target time period.

Specifically, when the optimization control unit 143 finishes processing for all time periods (T ₁ to T _J ), the iteration control unit 346 causes the simulator execution unit 141 to perform the execution and the next input parameter determination unit 142 until the number of repetitions of the determination by and above exceeds the maximum number of repetitions R, the optimization control unit 143 is made to _perform the processing again from the time zone T1.

とその目的関数値

を格納する。 At this time, the optimization control unit 143 does not initialize the optimization result storage unit 144 to an empty set.

and its objective function value

to store

を算出させ、最適パラメータテーブル１３３に格納させる。 Further, when the number of iterations exceeds the maximum number of iterations R, the iteration control unit 346 causes the optimization control unit 143 to collectively collect the data contained in the time zone optimization result storage unit 145 into the optimal parameter

is calculated and stored in the optimum parameter table 133 .

<Operation of the moving route estimation device according to the second embodiment of the present invention>
FIG. 7 is a flow chart showing a moving route estimation processing routine according to the embodiment of the present invention. It should be noted that the same reference numerals are assigned to the same processing as the movement route estimation processing routine according to the first embodiment, and detailed description thereof will be omitted.

In step S<b>400 , the simulator setting processing unit 110 sets the fields necessary for executing the simulator input from the external device 200 , the optimization processing unit 320 sets the maximum number of optimization execution times S input from the external device 200 The number of time divisions J, the maximum number of repetitions R, and the time delay constant D are obtained respectively.

In step S420, the optimization processing unit 320 sets the maximum optimization execution count S, the time division count J, the maximum repetition count R, and the time delay constant D acquired in step S400 in the optimization setting table 332.

In step S435, r=1. r is a counter for counting the number of repetitions of the optimization process.

At step S170, j=j+1. Note that j=1 when j+1>J.

In step S475, r=r+1.

In step S480, the iteration control unit 346 determines whether r is greater than the maximum number of iterations R.

If r is not greater than the maximum number of repetitions R (NO in step S480), the optimization control unit 143 determines whether or not r is greater than the number of time divisions J in step S490.

If r is not greater than J (NO in step S490), in step S500, the optimization result storage unit 144 is initialized to an empty set, and steps S150 to S480 are repeated.

とその目的関数値

を読み出して、最適化結果保管部１４４に格納して、再度ステップＳ１５０～Ｓ４８０の処理を繰り返す。 On the other hand, if r is greater than J (YES in step S490), in step S510, the optimization control unit 143 stores the

and its objective function value

is read out, stored in the optimization result storage unit 144, and the processing of steps S150 to S480 is repeated again.

On the other hand, if j is greater than J (YES in step S490),

On the other hand, if r is greater than the maximum number of repetitions R (YES in step S480), the process proceeds to step S200.

As described above, according to the present embodiment, each of all time periods is set as an estimation target time period, and input parameters are repeatedly obtained for each of all time periods until a predetermined repetition condition is satisfied. is repeatedly executed as an estimation target time period, it is possible to accurately estimate an agent's action path that reduces the observation error even in a situation where a time delay occurs.

<Moving route estimation device according to the third embodiment of the present invention>
Next, a third embodiment of the invention will be described.

FIG. 8 is an image diagram showing an overview of this embodiment. In the present embodiment, when optimizing the time period _Tj in the first embodiment or the second embodiment, by generating only the agents for the preceding and succeeding D time periods, the agents for all time periods , the execution time of MAS is shortened, and as a result, optimization speed can be increased.

In this embodiment, the same components as those of the moving path estimation apparatus according to the first embodiment or the second embodiment are denoted by the same reference numerals, and detailed description thereof will be omitted.

The simulator execution unit 141 includes a predetermined number of time slots (T _j−D ) preceding the estimation target time slot among all the time slots (T ₁ to T _J ), the estimation target time slot (T _j ), and the estimation A simulation is performed in which a plurality of agents move in a predetermined number of time periods (T _j+D ) including the time period next to the target time period.

によって発生するエージェントのみを行動させる。 Specifically, when the simulator execution unit 141 executes the people flow simulator, the parameter

Act only on agents generated by

As described above, according to the present embodiment, among all the time slots, the predetermined number of time slots before the estimation target time slot, the estimation target time slot, and the time slot next to the estimation target time slot are included. By running a simulation in which multiple agents move in a given number of time slots, it is possible to quickly estimate the action paths of agents that minimize observation errors even under conditions where time delays occur. .

The present invention is not limited to the above-described embodiments, and various modifications and applications are possible without departing from the gist of the present invention.

In the above-described embodiment, the case of using Bayesian optimization as an example of the optimization method has been described, but the method is not limited to Bayesian optimization, and other optimization methods and algorithms may be applied. For example, a genetic algorithm can be applied as an optimization method.

から各時間帯に経路Ｒ_ｉを通過した人数

を推定するという場合を考えたが、様々な観測データ（通行人数、単位時間当たりの観測地点の密度、目的地までの平均移動時間等）に対して柔軟に適応させることが出来る。このため、種々のデバイスから得られたデータに対応することが出来る。 In this embodiment, the number of passers-by measured in a certain time period T _j at a plurality of observation locations k

The number of people who passed through route _Ri in each time slot from

However, it can be flexibly adapted to various observation data (passers, density of observation points per unit time, average travel time to destination, etc.). Therefore, it is possible to deal with data obtained from various devices.

Also, in the specification of the present application, an embodiment in which a program is pre-installed has been described. It is possible to run it on a computer or circulate it through a network. It is also possible to provide the program by storing it in a computer-readable recording medium.

100 moving route estimation device 110 simulator setting processing unit 120 optimization processing unit 130 data storage unit 131 simulator setting table 132 optimization setting table 133 optimum parameter table 140 optimization execution unit 141 simulator execution unit 142 next input parameter determination unit 143 optimization Control unit 144 Optimization result storage unit 145 Time zone optimization result storage unit 150 Optimal parameter processing unit 200 External device 300 Movement route estimation device 320 Optimization processing unit 332 Optimization setting table 340 Optimization execution unit 346 Iteration control unit

Claims (5)

For each of a plurality of routes in the real environment, simulation of a plurality of agents moving in each time period, among input parameters whose elements are the number of agents passing through the route in each time period, the input parameter is executed based on the input parameter of the estimation target time period, which is the target time period for estimating , and a predetermined number including the estimation target time period and the time period following the estimation target time period from the result of the simulation a simulator execution unit that calculates an objective function representing an observation error between the calculated value for the agent and the observed value in the real environment for each observation point in the time period of
a next input parameter determination unit that determines a next input parameter based on the input parameter and the result of calculation of the objective function;
Optimizing for estimating input parameters in the estimation target time period for optimizing the objective function by repeating the execution by the simulator execution unit and the determination by the next input parameter determination unit until a predetermined repetition condition is satisfied. a conversion control unit;
Each of all the time slots is sequentially set as the estimation target time slot, and after setting the final time slot as the estimation target time slot, returning to the first time slot and setting it as the estimation target time slot. an iterative control unit that causes the optimization control unit to repeatedly execute the estimation of the input parameter in the estimation target time period until a predetermined repetition condition is satisfied;
Moving path estimation device including. The simulator execution unit performs a predetermined number of time periods including a predetermined number of time periods before the estimation target time period, the estimation target time period, and the time period next to the estimation target time period, among all the time periods. 2. The movement path estimation device according to claim 1 , wherein said simulation is executed in which a plurality of agents move in a band. A simulator execution unit performs a simulation in which a plurality of agents move in each time zone for each of a plurality of routes in a real environment, and an input parameter whose element is the number of agents passing through the route in each time zone. Among them, execution is performed based on the input parameters of the estimation target time period, which is the target time period for estimating the input parameters , and from the result of the simulation, the estimation target time period and the next time of the estimation target time period calculating an objective function representing the observation error between the calculated value for the agent and the observed value in the real environment for each of the observation points in a predetermined number of time periods including the time period;
a next input parameter determination unit determining a next input parameter based on the input parameter and the calculation result of the objective function;
The optimization control unit repeats the execution by the simulator execution unit and the determination by the next input parameter determination unit until a predetermined repetition condition is satisfied, and inputs the estimation target time period for optimizing the objective function. estimating parameters;
The iterative control unit sequentially sets each of all the time periods as the estimation target time period, sets the final time period as the estimation target time period, and then returns to the first time period to set the estimation target time period. a step of causing the optimization control unit to repeatedly execute estimating the input parameter of the estimation target time period until a predetermined repetition condition is satisfied;
Movement path estimation method including The executing step includes a predetermined number of time periods including a predetermined number of time periods before the estimation target time period, the estimation target time period, and the time period following the estimation target time period, among all the time periods. 4. The movement path estimation method according to claim 3 , wherein the simulation is performed in which a plurality of agents move in a band. A program for causing a computer to function as each part of the movement route estimation device according to claim 1 or 2 .

Images