WO2020255492A1 - 進路制御プログラム生成装置、進路制御プログラム生成方法及びプログラム - Google Patents

進路制御プログラム生成装置、進路制御プログラム生成方法及びプログラム Download PDF

Info

Publication number
WO2020255492A1
WO2020255492A1 PCT/JP2020/010012 JP2020010012W WO2020255492A1 WO 2020255492 A1 WO2020255492 A1 WO 2020255492A1 JP 2020010012 W JP2020010012 W JP 2020010012W WO 2020255492 A1 WO2020255492 A1 WO 2020255492A1
Authority
WO
WIPO (PCT)
Prior art keywords
state
section
mobile body
moving body
environment model
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/JP2020/010012
Other languages
English (en)
French (fr)
Inventor
敦義 西面
隆信 半田
顕志 鄭
賢吾 桑名
広昂 岡崎
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Mitsubishi Heavy Industries Ltd
Original Assignee
Mitsubishi Heavy Industries Ltd
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Mitsubishi Heavy Industries Ltd filed Critical Mitsubishi Heavy Industries Ltd
Priority to JP2021527355A priority Critical patent/JP7321416B2/ja
Priority to US17/619,849 priority patent/US12221141B2/en
Priority to EP20827325.0A priority patent/EP3971053A4/en
Publication of WO2020255492A1 publication Critical patent/WO2020255492A1/ja
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Images

Classifications

    • B—PERFORMING OPERATIONS; TRANSPORTING
    • B61—RAILWAYS
    • B61L—GUIDING RAILWAY TRAFFIC; ENSURING THE SAFETY OF RAILWAY TRAFFIC
    • B61L23/00—Control, warning or like safety means along the route or between vehicles or trains
    • B61L23/22—Control, warning or like safety means along the route or between vehicles or trains for controlling traffic in two directions over the same pair of rails
    • B61L23/30—Control, warning or like safety means along the route or between vehicles or trains for controlling traffic in two directions over the same pair of rails using automatic section blocking
    • B—PERFORMING OPERATIONS; TRANSPORTING
    • B61—RAILWAYS
    • B61L—GUIDING RAILWAY TRAFFIC; ENSURING THE SAFETY OF RAILWAY TRAFFIC
    • B61L27/00—Central railway traffic control systems; Trackside control; Communication systems specially adapted therefor
    • B61L27/10—Operations, e.g. scheduling or time tables
    • B61L27/16—Trackside optimisation of vehicle or train operation
    • B—PERFORMING OPERATIONS; TRANSPORTING
    • B61—RAILWAYS
    • B61L—GUIDING RAILWAY TRAFFIC; ENSURING THE SAFETY OF RAILWAY TRAFFIC
    • B61L27/00—Central railway traffic control systems; Trackside control; Communication systems specially adapted therefor
    • B61L27/10—Operations, e.g. scheduling or time tables
    • B61L27/12—Preparing schedules
    • B—PERFORMING OPERATIONS; TRANSPORTING
    • B61—RAILWAYS
    • B61L—GUIDING RAILWAY TRAFFIC; ENSURING THE SAFETY OF RAILWAY TRAFFIC
    • B61L19/00—Arrangements for interlocking between points and signals by means of a single interlocking device, e.g. central control
    • B61L19/06—Interlocking devices having electrical operation
    • B61L2019/065—Interlocking devices having electrical operation with electronic means
    • B—PERFORMING OPERATIONS; TRANSPORTING
    • B61—RAILWAYS
    • B61L—GUIDING RAILWAY TRAFFIC; ENSURING THE SAFETY OF RAILWAY TRAFFIC
    • B61L25/00—Recording or indicating positions or identities of vehicles or trains or setting of track apparatus
    • B61L25/06—Indicating or recording the setting of track apparatus, e.g. of points, of signals
    • B61L25/08—Diagrammatic displays

Definitions

  • the present invention relates to a course control program generator, a course control program generation method and a program.
  • the present application claims priority based on Japanese Patent Application No. 2019-11238 filed in Japan on June 18, 2019, the contents of which are incorporated herein by reference.
  • the track line is divided into sections called block systems, and movement to each block system is performed. Controls to allow or prohibit the entry of the body.
  • Patent Document 1 discloses a method of generating a program for controlling a train course.
  • the geometric patterns of two blocks in a line composed of a plurality of blocks are specified, and the logic used for determining whether or not a train can enter the block is selected based on the specified geometric patterns, and the selected plurality of blocks are selected.
  • the present invention provides a course control program generator, a course control program generation method, and a program that can solve the above-mentioned problems.
  • the course control program generator includes an orbit divided into a plurality of sections, a first mobile body to be controlled and a second mobile body to be controlled not to move on the orbit.
  • the state of the environment model is reserved for the section in which each of the first mobile body and the second mobile body exists, and for each of the first mobile body and the second mobile body.
  • the set In response to a request to move the environment model construction unit for constructing the set of the above and the first moving body to the target predetermined section without falling into a deadlock state with the second moving body, the set.
  • the environment model construction unit is provided with a search unit for searching the order of reaching the state of the environment model that satisfies the requirement while changing the state of the environment model included in the above to the state of another environment model. Constructs the set based on a predetermined constraint condition using the state of the environment model that matches the constraint condition.
  • the course control program generator includes an orbit divided into a plurality of sections, a first mobile body to be controlled and a second mobile body to be controlled not to move on the orbit.
  • the state of the environment model is reserved for the section in which each of the first mobile body and the second mobile body exists, and for each of the first mobile body and the second mobile body.
  • the search unit includes a search unit that searches the order of reaching the state of the environment model that satisfies the requirement while changing the state of the environment model included in the above to the state of another environment model. Based on a predetermined constraint condition, the search is performed while transitioning to the state of the environment model that matches the constraint condition.
  • the constraint condition is that the number of the sections reserved for at least one of the first mobile body and the second mobile body is set to a predetermined value or less. ..
  • the constraint condition sets the number of sections that can be reserved simultaneously in one state transition for at least one of the first mobile body and the second mobile body to a predetermined value or less. That is.
  • the constraint makes it possible to reserve the section in the traveling direction for at least one of the first moving body and the second moving body, and cannot reserve the other section. Is to be.
  • the constraint condition is that at least one of the first mobile body and the second mobile body is counted from the currently existing section in the traveling direction by a predetermined value. It is to make it possible to reserve the above-mentioned section of the above and to make it impossible to reserve the other said section.
  • the passage of time corresponding to a change in the state of the environmental model when the first mobile body or the second mobile body moves once to the adjacent section is defined as one logical time.
  • the constraint condition is to set an upper limit on the number of times of reservation and cancellation of reservation in the one logical time for at least one of the first mobile body and the second mobile body.
  • the search unit when the search unit cannot search the order leading to the state of the environment model satisfying the requirement, the upper limit for the number of executions is increased to obtain a set of the environment models. It builds and searches for the sequence leading up to the state of the environmental model that meets the requirements.
  • the passage of time corresponding to a change in the state of the environmental model when the first mobile body or the second mobile body moves once to the adjacent section is defined as one logical time.
  • both the reservation and the cancellation of the reservation are executed for one of the sections in the one logical time for at least one of the first mobile and the second mobile. It is forbidden to do that.
  • the passage of time corresponding to a change in the state of the environmental model when the first mobile body or the second mobile body moves once to the adjacent section is defined as one logical time. Then, the constraint condition is to prohibit both reservation and cancellation of reservation from being executed for one said section in the one logical time.
  • the environmental model includes a plurality of the second mobile bodies.
  • the course control program generation method includes an orbit divided into a plurality of sections, a first mobile body to be controlled and a second mobile body to be controlled not to move on the orbit.
  • the state of the environment model is reserved for the section in which each of the first mobile body and the second mobile body exists, and for each of the first mobile body and the second mobile body.
  • the said set included in the set. It has a step of searching for an order to reach the state of the environment model that satisfies the requirement while changing the state of the environment model to the state of another environment model, and the step of constructing the environment model has a predetermined constraint. Based on the conditions, the set is constructed using the states of the environment model that meet the constraints.
  • the course control program generation method includes an orbit divided into a plurality of sections, a first mobile body to be controlled and a second mobile body to be controlled not to move on the orbit.
  • the state of the environment model is reserved for the section in which each of the first mobile body and the second mobile body exists, and for each of the first mobile body and the second mobile body.
  • the said set included in the set. It has a step of searching the order of reaching the state of the environment model that satisfies the requirement while changing the state of the environment model to the state of another environment model, and the search step has a predetermined constraint. Based on the conditions, the search is performed while transitioning to the state of the environment model that matches the constraint conditions.
  • the program tells the computer a trajectory divided into a plurality of sections, a first mobile body to be controlled and a second mobile body to be controlled to move on the orbit.
  • the state of the environment model is reserved for the section in which each of the first mobile body and the second mobile body exists, and for each of the first mobile body and the second mobile body.
  • the environment included in the set in response to the step of constructing the set and the request to move the first moving body to the target predetermined section without falling into a deadlock state with the second moving body.
  • a step of searching for an order to reach the state of the environment model that satisfies the requirement is executed, and in the step of constructing the model, a predetermined constraint condition is applied. Based on, the set is constructed using the state of the environment model that meets the constraints.
  • the program tells the computer by an orbit divided into a plurality of sections, a first mobile body to be controlled and a second mobile body to be controlled not to move on the orbit.
  • the state of the environment model is reserved for the section in which each of the first mobile body and the second mobile body exists, and for each of the first mobile body and the second mobile body.
  • the section is determined by the section, and the section is reserved for the first mobile body and the second mobile body, the reservation is canceled, and the reserved section is moved to another reserved section.
  • a plurality of environmental models having different states by changing the section in which the first mobile body and the second mobile body are present and the section reserved for each of the first mobile body and the second mobile body.
  • the environment included in the set in response to the step of constructing the set and the request to move the first moving body to the target predetermined section without falling into a deadlock state with the second moving body.
  • a step of searching for an order to reach the state of the environment model that satisfies the requirement is executed, and in the step of searching, a predetermined constraint condition is used. Based on the above, the search is performed while transitioning to the state of the environment model that meets the constraint conditions.
  • the calculation cost for generating the course control program can be reduced.
  • FIG. 1 is a diagram showing an example of a course control program generator according to the first embodiment of the present invention.
  • the course control program generation device 10 (hereinafter referred to as the generation device 10) includes an environment model construction unit 11, a request setting unit 12, a search unit 13, an input reception unit 14, and an output. A unit 15 and a storage unit 16 are provided.
  • the environmental model construction unit 11 moves and blocks a state transition system in which the position of the moving body and the reservation status of the block are discretely changed by actions such as reserving a block, canceling the reservation of the block, and moving between blocks. Build every time. Further, in the present embodiment, the environment model construction unit 11 leaves only those that show the states and state transitions that meet the predetermined constraint conditions for the constructed state transition system, and uses the remaining state transition system as the environment model.
  • the predetermined constraints are, for example, the following four.
  • Condition 1 The number of blocks reserved for one moving body is not more than a predetermined maximum value.
  • Condition 2) The maximum number of blocks reserved at the same time in one state transition is less than or equal to a predetermined number.
  • Condition 3) Reserve only the closure in the direction of travel.
  • Condition 4) It is possible to reserve a predetermined number of closures from the closure while on the line, counting in the direction of travel.
  • any or a plurality of the above constraints are selected in advance, and the environment model construction unit 11 constructs the environment model only with the state transition system satisfying the selected conditions.
  • FIG. 2 is a diagram illustrating a state and a state transition system of an environmental model according to the first embodiment of the present invention.
  • the environment model is composed of a plurality of closed orbits, one controlled object moving body existing on the orbit, and 0 or more non-controlled moving objects existing on the orbit.
  • the environmental model can take various forms depending on the position of each moving body and the reservation status for each block, and each of them is called the state of the environmental model.
  • FIG. 2 shows an example of the state of the environment model composed of the orbit B divided into the block B0 to B5, the moving body X to be controlled, and the moving body Y not to be controlled.
  • the moving body X exists in the garage IB and the moving body Y exists in the block B4.
  • Blocks B0, B1 and B5 are reserved for the moving body X.
  • the positions of the mobile body X and the mobile body Y and the reservation status of the block system can be variously changed from the state shown in FIG.
  • the block reservation and the cancellation of the block for each moving body are performed in block units. Only one move can be reserved for a block at a time, and only one move can exist in a block at a time.
  • the moving body X in order for the moving body X to move to the block B0, it first reserves the block B0 and then moves to the block B0.
  • the moving body X reserves the block B0
  • the moving body Y cannot reserve the block B0. Then, for example, when the moving body X moves from the block B0 to another block and the reservation for the block B0 is no longer necessary, the reservation for the block B is canceled.
  • the solid line arrow indicates the approach direction to the closures B0 to B5 for the moving body X
  • the broken line arrow indicates the approach direction to the closures B0 to B5 for the moving body Y.
  • the moving body X can move from the block B0 to the block B5, or can move from the block B4 to the block B5, but the mobile body Y can only move from the block B4 to the block B5. Is.
  • the environment model construction unit 11 generates, for example, all patterns of the state of the environment model determined by the combination of the orbit B, the positions of the moving bodies X and Y, and the reservation status of the closure for each of the moving bodies X and Y.
  • the blocks B0, B1 and B5 are reserved for the moving body X, but only the block B0 is reserved, the block B0 and the block B1 are reserved, and the blocks B0 and B4 are reserved.
  • B5 is reserved, and the state of the environment model corresponding to all possible reservation situations is generated.
  • the environment model construction unit 11 changes, for example, the block in which the mobile body X and the mobile body Y exist, and generates the state of the environment model corresponding to all the reservation situations that can be taken in the positional relationship.
  • the set of states of many generated environment models is called a state transition system.
  • the request setting unit 12 sets a request for the movement of the moving bodies X and Y.
  • the requirement consists of safety conditions and goal conditions.
  • the safety conditions are, for example, "no matter what kind of movement other moving objects move, no dangerous result such as collision will occur", "no matter what control the controlled train controls, it will be a deadlock. It is a prohibited condition that must not be reached under any circumstances such as "do not fall”.
  • the goal condition is a condition that must be satisfied someday, such as "getting out of the garage and arriving at a designated station without causing a deadlock".
  • the goal condition may be composed of a combination of a plurality of target states such as "after satisfying a certain intermediate state, the other final state is reached".
  • the search unit 13 searches the action order of the moving bodies X and Y that satisfy the requirements (safety condition and goal condition) on the environment model (state transition system). For example, the search unit 13 determines which block is reserved, which block is canceled, and which block the controlled moving body X is moved with respect to the state of the environment model illustrated in FIG. Such actions are associated and transitioned to the state of the next environment model (state transition). The search unit 13 repeats this state transition until the state of the environment model that satisfies the request is reached.
  • the course control program is the order of state transitions until the state of the environmental model that satisfies the requirements is reached.
  • the course control program reserves which block and which block is reserved for each state of the environmental model from the state of the environmental model at the start to the state of the environmental model that satisfies the requirements. It is associated with actions such as releasing or moving each moving object to which block.
  • the input receiving unit 14 receives a user's instruction operation.
  • the output unit 15 outputs the search result by the search unit 13 to a monitor or the like.
  • the storage unit 16 stores the shape of the orbit, the number of blocks, the number of moving bodies, the constraint conditions to be applied, and the like.
  • FIG. 3 is a first diagram showing an example of a state transition in the first embodiment of the present invention.
  • FIG. 3 shows an example of a state transition that satisfies a requirement.
  • Each of FIGS. 3 (a) to 3 (f) shows one state of the environmental model.
  • the search unit 13 searches for a state transition satisfying the request from the state of FIG. 3A in response to the request to move the moving body X to the destination block B4 without deadlocking.
  • the search unit 13 associates the state of FIG. 3A with the action of reserving the blocks B0, B1, and B5 for the moving body X.
  • the state of the environmental model when the action is taken is shown in FIG. 3 (b).
  • the state of the environment model changes.
  • the search unit 13 associates the action of moving to the closed B0 and B5 with the state shown in FIG. 3 (b).
  • the state of the environmental model after the state transition due to those actions is the state shown in FIG. 3 (c).
  • the moving body X changes direction at the block B5, the state transitions to the state shown in FIG. 3 (d).
  • the search unit 13 associates the action of moving the moving body X with the reserved closing B1 with respect to the state shown in FIG. 3D.
  • the search unit 13 changes the state of the environment model by associating the action of reserving the block B2 with respect to the moving body X and the action of moving to the block B2 in order.
  • the reservation of the block B0, B1, B5 is canceled.
  • the environmental model transitions to the state shown in FIG. 3 (e).
  • the search unit 13 associates the state shown in FIG. 3 (e) with the reservation of the block B3 and B4 and the movement to the block B3 and B4 with respect to the moving body X, and brings the state shown in FIG. 3 (f). Transition.
  • FIGS. 3A to 3F and an action associated with each state are a course control program.
  • the state transition is performed by repeating the actions of making a reservation for closing, moving, and canceling the reservation.
  • the moving body Y moves from the block B3 to the block B4.
  • the mobile body Y waits in the block system B4 until the mobile body X cancels the reservation of the block system B5.
  • the moving body Y is associated with actions such as reservation of the block B5 and movement to the block B5.
  • the state of one environmental model determined by the orbit B divided into a plurality of blocks, the positions of the moving bodies X and Y, and the blocks reserved by each of the moving bodies X and Y is the state of the orbit B.
  • the transition to the next state is discretely performed according to the shape, the approach direction of the moving bodies X and Y into each block, the number of the moving bodies X and Y, the positional relationship of each moving body, the destination, and the like.
  • FIG. 4 is a second diagram showing an example of a state transition in the first embodiment of the present invention.
  • FIGS. 4 (a) to 4 (c) show state transitions in the case of falling into a deadlock state.
  • the search unit 13 transitions to the state shown in FIG. 4B by associating the state of the environment model shown in FIG. 4A with the action of reserving the blocks B0 and B1 for the moving body X.
  • the search unit 13 associates the movement to the block B0 with the moving body X in the state shown in FIG. 4B, and transitions to the state shown in FIG. 4C.
  • the moving body X does not reserve the block B5.
  • the moving body Y moves to the block B5 (FIG. 4 (c)). Then, as shown in FIG. 4C, the moving body X and the moving body Y fall into a deadlock state in which they cannot advance to each other.
  • the search unit 13 considers that the search has failed and cancels the search.
  • the search unit 13 associates actions such as reservation and movement with the state of a certain environment model, repeats the process of changing the state of the environment model, and changes the state to a state that satisfies the request. Find the order (solution).
  • the search unit 13 searches for a solution that satisfies the safety condition and the goal condition for all the states of the innumerable environmental models, the calculation cost is too high. Therefore, in the present embodiment, the search is performed using only the state or state transition that meets any one or more of the constraints described below as the search range, and the course control program is generated.
  • FIG. 5 is a diagram illustrating a first constraint condition in the first embodiment of the present invention.
  • the orbit C is divided into closed blocks C0 to C9.
  • the mobile body X exists in the block C0, and the mobile body Y exists in the block C7.
  • the solid line arrow indicates the approach direction of the moving body X to each block, and the broken line arrow indicates the approach direction of the moving body Y to each block.
  • the environment model construction unit 11 can generate, for example, a state in which all of the other blocks except the block C7 in which the mobile body Y exists are reserved for the mobile body X as a state of one environmental model. However, if the fully closed block can be reserved, the search pattern by the search unit 13 increases.
  • FIG. 5 shows an example of reservation when up to 6 blocks can be reserved at the same time.
  • the blocks marked with (Reservation 1) to (Reservation 6) are shown to be reserved.
  • the number of reserved closures is six.
  • FIGS. 6 to 9 below it is assumed that the block system in which (Reservation 1) and the like are described is reserved. The number "1" in (Reservation 1) is attached to count the total number of reserved closures, and does not indicate the order or order. This also applies to FIGS. 6 to 9.
  • FIG. 6 is a diagram illustrating a second constraint condition in the first embodiment of the present invention.
  • the environmental model shown in FIG. 6 is the same as that described in FIG. Constraint 2 relates to the number of block reservations possible in one state transition.
  • an upper limit is set on the number of blocks that can be reserved for the moving body X.
  • the number of reservations for closure for the moving body 1 is 0.
  • 3 is set for the maximum number of blocks to be reserved at the same time in one state transition, a maximum of 3 blocks can be reserved in the next state in the upper figure of FIG.
  • the lower figure of FIG. 6 shows the state after reserving the three blocks C1, C2, and C9.
  • FIG. 7 is a diagram illustrating a third constraint condition in the first embodiment of the present invention.
  • Constraint 3 is a condition that only the closure in the traveling direction can be reserved for each moving body. According to this constraint condition, in the state of the environment model shown in FIG. 7, the block C0 cannot be reserved for the moving body X.
  • Constraint 4 sets an upper limit on the range of block systems that can be reserved based on the current position of the moving body.
  • this upper limit is 3, for example, the blocks C1, C2, and C9 can be reserved for the moving body X in the state of the environment model shown in FIG.
  • the blocks C1 and C9 can be reserved for the moving body X in FIG.
  • FIG. 9 shows another example in which the constraint condition 4 is applied.
  • the trajectory D illustrated in FIG. 9 is divided into blocks D0 to D4.
  • the mobile body X exists in the block D0
  • the mobile body Y exists in the block D4.
  • the solid line arrow indicates the approach direction of the moving body X
  • the broken line arrow indicates the approach direction of the moving body Y.
  • the range of the block that can be reserved is set to two ahead.
  • the moving body X reserves the closing D1 and D2
  • the moving body X and the moving body Y can move in their respective traveling directions without falling into a deadlock state.
  • FIG. 10 is a flowchart showing an example of a course control program generation process according to the first embodiment of the present invention.
  • the environment model construction unit 11 constructs a state transition system for each moving body and each block (step S11).
  • the environmental model construction unit 11 comprehensively covers the state in which the positions of the moving bodies X and Y and the reservation status of the blocks change discretely by making reservations, moving, and canceling the reservations for the moving bodies X and Y. Generate. Many of the generated states are state transition systems.
  • the environmental model construction unit 11 constructs an environmental model (step S12). Specifically, it is preset whether to apply any of the constraint conditions 1 to 4, and the environment model construction unit 11 leaves only the state of the environment model satisfying the applied constraint conditions. Let the set of the remaining environmental model states be the environmental model. For example, if the upper limit of the number of reservations for constraint condition 1 is 6, the environment model construction unit 11 reserves 7 or more blocks for any of the moving bodies X and Y among the states generated in step S11. Exclude the state that was done. For example, the environment model construction unit 11 may delete the state of the environment model that does not satisfy the condition of the constraint condition 1, or adds information indicating that the environment model is excluded to the state of the environment model. May be good.
  • the environment model construction unit 11 transfers the state 1 to the state 2.
  • Information that excludes transitions may be added.
  • the request setting unit 12 sets a request for the movement of the moving bodies X and Y (step S13). For example, in the examples of FIGS. 2 and 3, the request setting unit 12 sets the safety condition that the deadlock does not occur and the goal condition that the destination of the moving body X is closed B4.
  • the request setting unit 12 may set an initial condition (for example, starting from the state of FIG. 3A) together with the request.
  • the safety condition, the goal condition, and the initial condition may be registered in the storage unit 16 in advance, or may be input by the user to the generation device 10.
  • the input receiving unit 14 receives the input of this instruction operation and instructs the search unit 13 to generate a program.
  • the search unit 13 searches for an action sequence that satisfies the requirements for the mobile body X and the mobile body Y (step S14).
  • the search unit 13 associates actions such as reservation, movement, and cancellation of reservation with the state of the environment model indicated by the initial condition, and performs a state transition. , Search for actions to be associated with each state during the transition when it is possible to finally transition to the state of the environment model that meets the requirements.
  • the search unit 13 determines whether or not there is an action sequence that satisfies the request (step S15).
  • the search unit 13 when the search unit 13 performs a search such as transitioning from the state of FIG. 4A to the state of FIG. 4B and then transitioning to the state of FIG. 4C, the action at this time is performed. Judge that the order does not meet the requirements. For example, when the search unit 13 performs a search such as transitioning from the state of FIG. 3 (a) to each state of FIGS. 3 (b) to 3 (f) in this order, the action order at this time is Judge that the request is satisfied.
  • the output unit 15 outputs the action order searched by the search unit 13 to the monitor (step S16). For example, the output unit 15 outputs the state of each environment model from FIG. 3A to FIG. 3F and the action information associated with each state.
  • the output information is the course control program.
  • the user inputs to the generation device 10 whether or not to search for another action sequence.
  • the input receiving unit 14 receives the input of this instruction operation.
  • the input receiving unit 14 instructs the search unit 13 to search again.
  • the search unit 13 searches for another action sequence that satisfies the request for the mobile body X and the mobile body Y (step S14).
  • the generation device 10 ends the generation process of the course control program.
  • step S15 If an action sequence that satisfies the request is not found even after searching all patterns (step S15; No), the search unit 13 determines that there is no solution. For example, the output unit 15 displays "no solution" on the monitor.
  • the states of the environmental model are comprehensively generated, and only those that meet the predetermined constraints are searched.
  • a course control program that satisfies the requirements can be generated at a lower calculation cost than in the case where no constraint condition is provided. This is especially effective in reducing the calculation cost when the number of blocks and the number of moving objects are large.
  • the calculation cost is reduced by reducing the scale of the environmental model by deleting the states of the environmental model that do not meet the constraints 1 to 4 from the state transition system.
  • the search unit 13a searches for an action procedure that satisfies the request, the action of the moving body is searched within a range that satisfies the constraints 1 to 4.
  • FIG. 11 is a diagram showing an example of a course control program generator according to the second embodiment of the present invention.
  • the course control program generation device 10a includes an environment model construction unit 11a, a request setting unit 12, a search unit 13a, an input reception unit 14, an output unit 15, and a storage unit 16.
  • the functions of the request setting unit 12, the input reception unit 14, the output unit 15, and the storage unit 16 are the same as those in the first embodiment.
  • the environmental model construction unit 11a constructs a state transition system composed of a combination of the trajectory, the positions of the mobile body to be controlled and the mobile body not to be controlled, and all patterns of the reservation status of each block.
  • this state transition system is used as an environmental model.
  • the search unit 13a searches the action sequence of the moving body that satisfies the safety condition and the goal condition on the state transition system.
  • the search unit 13a limits the search range by applying a preselected condition among the constraint conditions 1 to 4 when searching for the action sequence.
  • FIG. 12 is a flowchart showing an example of a course control program generation process according to the second embodiment of the present invention. The same processing as in the first embodiment will be briefly described. It is assumed that which of the constraints 1 to 4 is applied is set in advance. Alternatively, it may be set together with the request in step S13.
  • the environment model construction unit 11a constructs a state transition system in which the position of each moving body and the reservation status of each block system are comprehensively changed (step S11).
  • the request setting unit 12 sets a request for the movement of the moving body X (step S13).
  • the search unit 13a searches for an action sequence that satisfies the requirements for the mobile body to be controlled and other mobile bodies according to the user's instruction (step S14a). Unlike the first embodiment, the search unit 13a searches by making a state transition so as to meet the set constraint conditions 1 to 4. For example, when the constraint condition 1 is set, when transitioning from the state of FIG. 3A to the next state, the search unit 13a selects the transition destination from the states of the environment model that meets the constraint condition 1. Select a state. For example, when up to six blocks can be reserved at the same time, the search unit 13a does not associate an action such that seven blocks are reserved with respect to the current state of the environment model. The same applies to the other constraints 2 to 4.
  • the search unit 13a determines whether or not there is an action sequence that satisfies the request (step S15).
  • the output unit 15 outputs the action order searched by the search unit 13a to the monitor (step S16).
  • step S17; Yes When searching for another action sequence (step S17; Yes), the search unit 13a searches for another action sequence that satisfies the request (step S14a). When not searching for another action sequence (step S17; No), the generation device 10a ends the process of generating the course control program. If the action sequence satisfying the request is not found even after searching all patterns (step S15; No), the search unit 13a determines that there is no solution.
  • the generation device 10 is divided into three mobile bodies X, Y, and Z.
  • the state transition is performed under the conditions of constraint condition 1 to constraint condition 4 to search the action sequence (first embodiment).
  • the generation device 10a constructs a state transition system under the conditions of constraint condition 1 to constraint condition 4 (second embodiment).
  • the constraint conditions 1 to 4 are imposed on each of the first moving body (moving body X) and the second moving body (moving body Y), but the first moving body and the second moving body are imposed.
  • Constraint 1 or the like may be imposed on at least one of the bodies, for example, moving bodies X, Y, Z (moving body X is the first moving body, moving bodies Y, Z are the second moving bodies) in orbit. If there are three of these, even if constraints 1 to 4 are imposed on at least one of the three mobiles X, Y, and Z, the action sequence is searched and the state transition system is constructed. Good.
  • the fact that a plurality of second mobile bodies may exist and that a constraint condition may be imposed on at least one of the first mobile body and the second mobile body is the following third embodiment and fourth embodiment. The same applies to.
  • the moving objects X and Y are moved to the destination while changing the state of the environmental model by the reservation of the block system, the cancellation of the reservation, the movement, and the standby.
  • Create a course control program by searching the action sequence to be moved.
  • the course control program does not include the concept of time, but in the real world, it takes time to control the movement or standby of the moving objects X and Y, and when the movement / standby is completed, the time required for control is Over time, the actual environmental conditions have changed.
  • one state transition accompanied by the movement / standby of the moving objects X and Y on the environment model actually involves the passage of real time.
  • the reservation and cancellation of the block system need only be electronic processing, the action is completed at a speed in which the passage of real time can be ignored as compared with the movement / standby of the moving bodies X and Y. Therefore, it can be considered that a plurality of reservations and cancellations of reservations can be processed at the same time. For example, while the moving body X moves to the next block, many actions such as reservation of block and cancellation of reservation can be executed.
  • an environmental model generated by the control corresponding to the time required for the actual control of the moving bodies X and Y (for example, the time required for the movement to the adjacent block, the time required for the control to stop and wait in the existing block).
  • logical time passage to express the discrete elapsed time corresponding to the transition of the state of.
  • One state transition due to movement or standby corresponds to the passage of one unit of logical time, and the elapsed time during this period is defined as one logical time.
  • Actions that can be executed within one logical time in the process of searching for the action sequence that causes the moving body to reach the destination in correspondence with the actual time required for moving / waiting, making a reservation, and canceling the reservation of the moving bodies X and Y.
  • actions that can be performed within one logical time are reservation of multiple closures, cancellation of multiple reservations, one move or one wait.
  • No other action (reservation, unreservation, move, wait) can be performed after the move or wait. This is because it takes real time to complete the control of movement or standby, so the state of the environment also changes.
  • step S14 in FIG. 10 and step S14a in FIG. 12 the block system is reserved immediately after the block system is reserved.
  • Useless search patterns such as opening may enter. "Immediately after making a reservation” is "after the reservation control is completed, before the movement control of the moving body X or the like to be controlled or the state transition of the other moving body Y or the like occurs". Therefore, the cancellation of the reservation immediately after the reservation has the same result as the fact that the state transition has not occurred, which is useless control. If the cancellation immediately after the reservation can be searched, it becomes possible to search for unnecessary control, and it takes time to calculate the course control program.
  • a constraint is set on an action that can be executed within one logical time (constraint condition ⁇ ). For example, an upper limit is set on the total number of reservations and reservation cancellations that can be executed within one logical time to prevent an unlimited number of unnecessary searches.
  • FIG. 13 is a diagram showing an example of a course control program generator according to the third embodiment of the present invention.
  • the course control program generation device 10b includes an environment model construction unit 11b, a request setting unit 12, a search unit 13b, an input reception unit 14, an output unit 15, and a storage unit 16.
  • the functions of the request setting unit 12, the input reception unit 14, the output unit 15, and the storage unit 16 are the same as those in the first embodiment.
  • the environmental model construction unit 11b constructs a state transition system composed of a combination of the trajectory, the positions of the mobile body to be controlled and the mobile body not to be controlled, and all patterns of the reservation status of each block. Further, the environment model construction unit 11b has a function of selecting a state satisfying the constraint condition ⁇ from the constructed state transition system and constructing the environment model.
  • the search unit 13b searches for the action sequence of the moving body that satisfies the safety conditions and the goal conditions for the environmental model constructed by the environmental model construction unit 11b. Further, the search unit 13b has a function of searching the action order for a limited search range to which the constraint condition ⁇ is applied when searching for the action order.
  • 14 and 15 are first and second views for explaining the constraint conditions in the third embodiment of the present invention.
  • 14 and 15 show a tree showing a search path for actions within the same logical time.
  • solid arrows indicate movement / standby.
  • the dashed arrow indicates the reservation for the block.
  • the dash-dotted arrow indicates the cancellation of the reservation for the block.
  • One solid arrow indicates one move or wait.
  • One dashed arrow indicates one reservation for one block, and one dashed arrow indicates one cancellation for one reserved block.
  • the first, second, ..., On the right side indicate the number of actions.
  • FIG. 14 shows an example of a search path when there is no upper limit on the total of reservations and reservation cancellations.
  • FIG. 15 shows a tree of search paths when the upper limit of the total number of reservations and cancellations is set to 3.
  • node P0 selects cancellation of reservation as the first action to reach node P1
  • cancels reservation as the second action reaches node P4, and reserves as the third action.
  • the node P10 is reached after canceling the reservation, the reservation has already been canceled three times. Therefore, in this logical time, the reservation, the cancellation of the reservation, the movement, or the standby cannot be performed any more, and this logic. The time is complete. This situation is indicated by a cross. A cross indicates that the node cannot be reached.
  • the first action is to cancel the reservation to reach node P1
  • the second action is to select reservation to reach node P5
  • the third action is to cancel the reservation to reach node P12.
  • the reservation since the reservation is made once and the reservation is canceled twice, the total number of reservations and cancellations is limited to three times, and the reservation and reservation cannot be canceled any more.
  • the constraint condition ⁇ is to set an upper limit on the total number of reservations and cancellations of reservations.
  • the constraint ⁇ applies to at least one of the moving bodies X and Y.
  • the upper limit of the total number of reservations and cancellations of reservations may be set in advance, but it may be set as follows. In other words, the upper limit of the total number of times needs to be set appropriately by the designer depending on the complexity of the route such as the number of consecutive branch blocks, but it is appropriate for humans in the environmental conditions that can be controlled including a huge combination pattern. It is difficult to set a certain number of times. Therefore, at first, the upper limit of the total number of times is set to 1, and if there is no solution of the course control program, the upper limit of the total number of times is increased by a predetermined value (for example, 1) until a solution is obtained. By setting the upper limit value in this way, it is possible to obtain a solution (action procedure) that satisfies the safety condition and the goal condition at the lowest upper limit value at which a solution can be obtained and minimizes unnecessary actions.
  • a predetermined value for example, 1
  • FIG. 16 is a first flowchart showing an example of a course control program generation process according to the third embodiment of the present invention.
  • 1 is set as the initial value of the upper limit of the total number of reservations and cancellations of reservations.
  • the environment model construction unit 11 constructs a state transition system in which the position of each moving body and the reservation status of each block system are comprehensively changed (step S11).
  • the environment model construction unit 11 records all of the constructed state transition systems in the storage unit 16.
  • the environmental model building unit 11 builds an environmental model (step S12).
  • the environment model construction unit 11 sets the time for one transition of the state of the environment model by one movement or standby from the state transition system constructed in step S11 as one logical time, and the moving bodies X and Y For at least one of them, only the state of the environmental model that satisfies the demand for action that can be performed in one logical time is left.
  • the request for an action that can be performed in one logical time is a reservation of a closure within the upper limit, a cancellation of the reservation, and one movement or waiting.
  • the environmental model building unit 11 excludes the state including the result of such an action. For example, the environmental model construction unit 11 may delete the state of the environmental model in which the upper limit of the total number of times exceeds 1, or adds information indicating that the environmental model is excluded to the state of the environmental model. You may.
  • the request setting unit 12 sets a request for the movement of the moving bodies X and Y (step S13).
  • the search unit 13b searches for an action sequence that satisfies the requirements for the mobile body X to be controlled and the other mobile body Y (step S14).
  • the search unit 13b determines whether or not there is an action sequence that satisfies the request (step S15).
  • the output unit 15 outputs the action order searched by the search unit 13b to the monitor (step S16).
  • searching for another action sequence step S17; Yes
  • the search unit 13b searches for another action sequence that satisfies the request (step S14).
  • the generation device 10b ends the process of generating the course control program.
  • step S15 determines that there is no solution.
  • the generation device 10b for example, the environment model construction unit 11b
  • the processing after step S12 is repeated again.
  • the environment model construction unit 11b reads out the state transition system stored in the storage unit 16, and includes a state in which the upper limit of the total number of reservations and reservation cancellations exceeds the value after addition. Delete the state of the environment and build the environment model. Then, the generation device 10b executes the processes after step S13.
  • the occurrence of each block reservation and reservation cancellation within one logical time is counted, and when the total number of these reaches a certain number of times (upper limit value), it is more than that within the same logical time. It is prohibited that reservations and cancellations of reservations occur. As a result, for example, it is possible to prevent the occurrence of a search pattern in which reservations and cancellations are infinitely repeated for the same block. By setting an upper limit on the total number of reservations and cancellations of reservations, for example, it is possible to prevent the occurrence of a useless search pattern in which the moving body X reserves all the closures and the moving body Y cannot move. As described above, according to the present embodiment, the search space can be reduced and the calculation time can be shortened.
  • the third embodiment can be combined with the first embodiment. That is, in step S12 of the flowchart of FIG. 16, in addition to the constraint condition ⁇ , the environment model construction unit 11b leaves only a state in which any or all of the constraint conditions 1 to 4 described in the first embodiment are satisfied. You may build an environmental model.
  • FIG. 17 is a second flowchart showing an example of a course control program generation process according to the third embodiment of the present invention.
  • the environment model construction unit 11b constructs a state transition system in which the position of each moving body and the reservation status of each block system are comprehensively changed (step S11).
  • the request setting unit 12 sets a request for the movement of the moving body X (step S13).
  • the search unit 13b searches for an action sequence that satisfies the requirements for the mobile body to be controlled and other mobile bodies (step S14a).
  • the search unit 13b searches by performing a state transition so as to satisfy any of the constraint condition ⁇ , the constraint condition ⁇ , and the constraint conditions 1 to 4.
  • the search unit 13b determines whether or not there is an action sequence that satisfies the request (step S15).
  • the output unit 15 outputs the action order searched by the search unit 13b to the monitor (step S16).
  • the search unit 13b searches for another action sequence that satisfies the request (step S14a).
  • step S17; No When not searching for another action sequence (step S17; No), the generation device 10a ends the process of generating the course control program. If the action sequence satisfying the request is not found even after searching all patterns (step S15; No), the search unit 13a determines that there is no solution. The search unit 13b determines that there is no solution. If there is no solution, the environment model construction unit 11b adds 1 to the upper limit of the total number of reservations and cancellations. Then, the generation device 10b repeats the processing after step S14a again. As a result, the search space can be limited and the calculation time can be shortened.
  • FIG. 18 is a diagram showing an example of a course control program generator according to a fourth embodiment of the present invention.
  • the same processing and configuration as in the first embodiment will be briefly described.
  • the course control program generation device 10c includes an environment model construction unit 11c, a request setting unit 12, a search unit 13c, an input reception unit 14, an output unit 15, and a storage unit 16.
  • the functions of the request setting unit 12, the input reception unit 14, the output unit 15, and the storage unit 16 are the same as those in the first embodiment.
  • the environmental model construction unit 11c constructs a state transition system composed of a combination of the trajectory, the positions of the mobile body to be controlled and the mobile body not to be controlled, and all patterns of the reservation status of each block. Further, the environment model construction unit 11c has a function of selecting a state satisfying the constraint condition ⁇ described below from the constructed state transition systems and constructing the environment model.
  • the search unit 13c searches for the action sequence of the moving body that satisfies the safety conditions and the goal conditions for the environmental model constructed by the environmental model construction unit 11c. Further, the search unit 13c has a function of searching the action order for a limited search range to which the constraint condition ⁇ is applied when searching for the action order.
  • FIG. 19 is a diagram for explaining the constraint conditions in the fourth embodiment of the present invention.
  • the following restrictions are applied to the reservation and the cancellation of the reservation that at least one of the mobile bodies X and Y can execute in one logical time.
  • ⁇ 1 The occurrence of a certain block reservation is limited to once per logical time.
  • ⁇ 2 Cancellation of a certain block reservation is limited to once per logical time.
  • ⁇ 3 When a reservation or cancellation of a reservation occurs for a certain block, the other action does not occur within the same logical time.
  • the actions in which one moving body can be selected in one logical time are one movement or waiting, one reservation for each block ( ⁇ 1), and one action for each block.
  • Cancellation of reservation ( ⁇ 2), reservation for the same block and cancellation of reservation immediately after reservation, or cancellation of reservation for the same block and reservation immediately after cancellation cannot be selected ( ⁇ 3).
  • ⁇ 1 ⁇ ⁇ 3 is the constraint condition ⁇ .
  • the mobile body X cannot reserve the block B5 in one logical time and immediately cancel the reservation of the block B5 ( ⁇ 3).
  • the search space can be reduced and the calculation time required for the search can be shortened without setting an appropriate upper limit value.
  • the behavior of repeatedly reserving and canceling the reservation for the same block within the range not exceeding the upper limit could not be excluded, but according to the constraint ⁇ , this useless behavior can be completely eliminated. it can.
  • step S12 the environmental model building unit 11c builds the environmental model, leaving only the state of the environmental model satisfying the constraint condition ⁇ .
  • the generation device 10c may generate a course control program in the same procedure as the process described with reference to FIG.
  • step S14a of FIG. 12 the search unit 13c selects a state transition that satisfies the constraint condition ⁇ and performs a search.
  • the fourth embodiment can be combined with the first embodiment and the third embodiment. That is, in step S12 of the flowchart of FIG. 10, in addition to the constraint condition ⁇ , the environment model construction unit 11c has the constraint conditions 1 to 4 described in the first embodiment and the constraint conditions ⁇ described in the third embodiment.
  • the environment model may be constructed leaving only the state that satisfies any or all of them.
  • the fourth embodiment can be combined with the second and third embodiments. That is, in step S14a of the flowchart of FIG. 12, in addition to the constraint condition ⁇ , the search unit 13c has any one of the constraint conditions 1 to 4 described in the first embodiment and the constraint condition ⁇ described in the third embodiment. Alternatively, the search can be performed by changing the state so as to satisfy all of them.
  • the constraint condition that both reservation and cancellation of reservation are prohibited for one block in one logical time is set to one or more arbitrary blocks. You may impose on it.
  • FIG. 13 is a diagram showing an example of the hardware configuration of the course control program generator according to each embodiment of the present invention.
  • the computer 900 is, for example, a PC (Personal Computer) including a CPU 901, a main storage device 902, an auxiliary storage device 903, an input / output interface 904, and a communication interface 905, a server terminal device, and the like.
  • the path control program generators 10, 10a, 10b, and 10c described above are mounted on the computer 900.
  • the operation of each processing unit described above is stored in the auxiliary storage device 903 in the form of a program.
  • the CPU 901 reads the program from the auxiliary storage device 903, expands it to the main storage device 902, and executes the above processing according to the program.
  • the CPU 901 secures a storage area corresponding to the storage unit 16 in the main storage device 902 according to the program.
  • the CPU 901 secures a storage area for storing the data being processed in the auxiliary storage device 903 according to the program.
  • the auxiliary storage device 903 is an example of a non-temporary tangible medium.
  • Other examples of non-temporary tangible media include magnetic disks, magneto-optical disks, CD-ROMs, DVD-ROMs, semiconductor memories, etc. connected via the input / output interface 904.
  • the distributed computer 900 may expand the program to the main storage device 902 and execute the above processing.
  • the program may be for realizing a part of the above-mentioned functions.
  • the program may be a so-called difference file (difference program) that realizes the above-mentioned function in combination with another program already stored in the auxiliary storage device 903.
  • the moving body X is an example of the first moving body
  • the moving body Y is an example of the second moving body.
  • Blocks B0 to B5, blocks C0 to C9, and blocks D0 to D4 are examples of sections.
  • the calculation cost for generating the course control program can be reduced.

Landscapes

  • Engineering & Computer Science (AREA)
  • Mechanical Engineering (AREA)
  • Control Of Position, Course, Altitude, Or Attitude Of Moving Bodies (AREA)
  • Train Traffic Observation, Control, And Security (AREA)

Abstract

進路制御プログラムの生成に要する計算コストを低減する生成装置を提供する。進路制御プログラム生成装置は、複数の区間に分割された軌道上に存在する制御対象の第１移動体および制御対象外の第２移動体によって構成される環境モデルについて、環境モデルの状態を様々に変化させた状態の異なる複数の環境モデルの集合を構築し、第１移動体を目的とする所定区間まで移動させる要求に対し、集合の中から選択した１つの環境モデルの状態を他の環境モデルの状態へ遷移させながら第１移動体を目的地まで移動させ、要求を達成できる場合の状態の遷移順を探索する。進路制御プログラム生成装置は、所定の制約条件に基づいて、制約条件に合致する環境モデルの状態で集合を構築する。

Description

進路制御プログラム生成装置、進路制御プログラム生成方法及びプログラム
　本発明は、進路制御プログラム生成装置、進路制御プログラム生成方法及びプログラムに関する。
　本願は、２０１９年６月１８日に、日本に出願された特願２０１９－１１２８３８号に基づき優先権を主張し、その内容をここに援用する。
　複数の移動体が軌道路線上を各々の目的地に向かって移動する鉄道システムや新交通システムでは、移動体同士の衝突を避けるため、軌道路線を閉そくと呼ばれる区間で区切り、各閉そくへの移動体の進入を許可あるいは禁止する制御を行う。
　移動体が閉そくに進入するためには、当該移動体向けに当該閉そくへの進入を予約する必要がある。当該移動体向けに予約された閉そくには当該移動体のみが進入を許可される。
　また、閉そくの予約が解除されると、当該閉そくはどの移動体も進入を禁止された状態になる。予約が解除された閉そくに移動体が進入するためには再度予約を行う必要がある。
　ある移動体が目的地に到達するためには、全ての移動体の位置関係や閉そく予約状況に応じて、当該移動体向けの閉そく予約、予約解除、閉そく間の移動などの制御を適切に行う必要がある。
　適切な制御を行わない場合、制御対象の移動体と他の移動体とがお互いに移動することができない状態（デッドロック）に陥る場合がある。
　デッドロック状態に陥ることなく移動体を目的地に到達させるため、閉そく予約、予約解除、閉そく間の移動などの制御を繰り返すルールを設計し、そのルールに従って移動体を制御する方法がある。このルールを進路制御プログラムと称する。
　関連する技術として特許文献１には、列車の進路制御のためのプログラムを生成する方法が開示されている。この方法では、複数の閉そくから構成される線路における２つの閉そくの幾何パターンを特定し、特定した幾何パターンに基づいて当該閉そくへの列車の進入可否の判断に用いるロジックを選択し、選択した複数のロジックを結合して進路制御プログラムを生成する。
日本国特許第６０７６９５０号公報
　進路制御プログラムを構築する場合、デッドロックに陥ることなく目的地に到着するための各移動体の行動を網羅的に検証する方法が考えられるが、閉そくや移動体の数が増えるにつれて計算コストが指数的に増加してしまう。
　本発明は、上述の課題を解決することのできる進路制御プログラム生成装置、進路制御プログラム生成方法及びプログラムを提供する。
　本発明の一態様によれば、進路制御プログラム生成装置は、複数の区間に分割された軌道と、該軌道上を移動する制御対象の第１移動体および制御対象外の第２移動体と、によって構成される環境モデルについて、前記環境モデルの状態が、前記第１移動体および前記第２移動体の各々が存在する前記区間と、前記第１移動体および前記第２移動体の各々について予約された前記区間とによって決定され、前記第１移動体および前記第２移動体についての前記区間の予約と、前記予約の解除と、予約した前記区間から他の予約した前記区間への移動によって、前記第１移動体および前記第２移動体が存在する前記区間と、前記第１移動体および前記第２移動体の各々について予約された前記区間とを変化させて状態の異なる複数の前記環境モデルの集合を構築する環境モデル構築部と、前記第１移動体を、前記第２移動体とのデッドロック状態に陥らせること無く、目的とする所定の前記区間まで移動させる要求に対し、前記集合に含まれる前記環境モデルの状態を他の前記環境モデルの状態へ変化させながら、前記要求を満たす前記環境モデルの状態へ至るまでの順序を探索する探索部と、を備え、前記環境モデル構築部は、所定の制約条件に基づいて、前記制約条件に合致する前記環境モデルの状態を用いて前記集合を構築する。
　本発明の一態様によれば、進路制御プログラム生成装置は、複数の区間に分割された軌道と、該軌道上を移動する制御対象の第１移動体および制御対象外の第２移動体と、によって構成される環境モデルについて、前記環境モデルの状態が、前記第１移動体および前記第２移動体の各々が存在する前記区間と、前記第１移動体および前記第２移動体の各々について予約された前記区間とによって決定され、前記第１移動体および前記第２移動体についての前記区間の予約と、前記予約の解除と、予約した前記区間から他の予約した前記区間への移動によって、前記第１移動体および前記第２移動体が存在する前記区間と、前記第１移動体および前記第２移動体の各々について予約された前記区間とを変化させて状態の異なる複数の前記環境モデルの集合を構築する環境モデル構築部と、前記第１移動体を、前記第２移動体とのデッドロック状態に陥らせること無く、目的とする所定の前記区間まで移動させる要求に対し、前記集合に含まれる前記環境モデルの状態を他の前記環境モデルの状態へ変化させながら、前記要求を満たす前記環境モデルの状態へ至るまでの順序を探索する探索部と、を備え、前記探索部は、所定の制約条件に基づいて、前記制約条件に合致する前記環境モデルの状態へ遷移させつつ前記探索を行う。
　本発明の一態様によれば、前記制約条件は、前記第１移動体および前記第２移動体のうち少なくとも一つに対して、予約される前記区間の数を所定値以下とすることである。
　本発明の一態様によれば、前記制約条件は、前記第１移動体および前記第２移動体のうち少なくとも一つについて、１つの状態遷移において同時に予約できる前記区間の数を所定値以下とすることである。
　本発明の一態様によれば、前記制約条件は、前記第１移動体および前記第２移動体のうち少なくとも一つについて、進行方向の前記区間を予約可能とし、他の前記区間を予約不可能とすることである。
　本発明の一態様によれば、前記制約条件は、前記第１移動体および前記第２移動体のうち少なくとも一つについて、現在存在している前記区間から進行方向に数えて所定値だけ先までの前記区間を予約可能とし、他の前記区間を予約不可能とすることである。
　本発明の一態様によれば、前記第１移動体又は前記第２移動体が隣接する前記区間へ１回移動するときの前記環境モデルの状態の変化に対応する時間の経過を１論理時間としたときに、前記制約条件が、前記第１移動体および前記第２移動体のうち少なくとも一つについて、前記１論理時間における予約と予約の解除の実行回数に対して上限を設けることである。
　本発明の一態様によれば、前記探索部が前記要求を満たす前記環境モデルの状態へ至るまでの順序が探索できなかった場合、前記実行回数に対する上限を増加させて、前記環境モデルの集合を構築し、前記要求を満たす前記環境モデルの状態へ至るまでの順序を探索する。
　本発明の一態様によれば、前記第１移動体又は前記第２移動体が隣接する前記区間へ１回移動するときの前記環境モデルの状態の変化に対応する時間の経過を１論理時間としたときに、前記制約条件が、前記第１移動体および前記第２移動体のうち少なくとも一つについて、前記１論理時間において、１つの前記区間に対して予約および予約の解除の両方が実行されることを禁止することである。
　本発明の一態様によれば、前記第１移動体又は前記第２移動体が隣接する前記区間へ１回移動するときの前記環境モデルの状態の変化に対応する時間の経過を１論理時間としたときに、前記制約条件が、前記１論理時間において、１つの前記区間に対して予約および予約の解除の両方が実行されることを禁止することである。
　本発明の一態様によれば、前記環境モデルは、前記第２移動体を複数含む。
　本発明の一態様によれば、進路制御プログラム生成方法は、複数の区間に分割された軌道と、該軌道上を移動する制御対象の第１移動体および制御対象外の第２移動体と、によって構成される環境モデルについて、前記環境モデルの状態が、前記第１移動体および前記第２移動体の各々が存在する前記区間と、前記第１移動体および前記第２移動体の各々について予約された前記区間とによって決定され、前記第１移動体および前記第２移動体についての前記区間の予約と、前記予約の解除と、予約した前記区間から他の予約した前記区間への移動によって、前記第１移動体および前記第２移動体が存在する前記区間と、前記第１移動体および前記第２移動体の各々について予約された前記区間とを変化させて状態の異なる複数の前記環境モデルの集合を構築するステップと、前記第１移動体を前記第２移動体とのデッドロック状態に陥らせること無く、目的とする所定の前記区間まで移動させる要求に対し、前記集合に含まれる前記環境モデルの状態を他の前記環境モデルの状態へ変化させながら、前記要求を満たす前記環境モデルの状態へ至るまでの順序を探索するステップと、を有し、前記構築するステップでは、所定の制約条件に基づいて、前記制約条件に合致する前記環境モデルの状態を用いて前記集合を構築する。
　本発明の一態様によれば、進路制御プログラム生成方法は、複数の区間に分割された軌道と、該軌道上を移動する制御対象の第１移動体および制御対象外の第２移動体と、によって構成される環境モデルについて、前記環境モデルの状態が、前記第１移動体および前記第２移動体の各々が存在する前記区間と、前記第１移動体および前記第２移動体の各々について予約された前記区間とによって決定され、前記第１移動体および前記第２移動体についての前記区間の予約と、前記予約の解除と、予約した前記区間から他の予約した前記区間への移動によって、前記第１移動体および前記第２移動体が存在する前記区間と、前記第１移動体および前記第２移動体の各々について予約された前記区間とを変化させて状態の異なる複数の前記環境モデルの集合を構築するステップと、前記第１移動体を前記第２移動体とのデッドロック状態に陥らせること無く、目的とする所定の前記区間まで移動させる要求に対し、前記集合に含まれる前記環境モデルの状態を他の前記環境モデルの状態へ変化させながら、前記要求を満たす前記環境モデルの状態へ至るまでの順序を探索するステップと、を有し、前記探索するステップでは、所定の制約条件に基づいて、前記制約条件に合致する前記環境モデルの状態へ遷移させつつ前記探索を行う。
　本発明の一態様によれば、プログラムは、コンピュータに、複数の区間に分割された軌道と、該軌道上を移動する制御対象の第１移動体および制御対象外の第２移動体と、によって構成される環境モデルについて、前記環境モデルの状態が、前記第１移動体および前記第２移動体の各々が存在する前記区間と、前記第１移動体および前記第２移動体の各々について予約された前記区間とによって決定され、前記第１移動体および前記第２移動体についての前記区間の予約と、前記予約の解除と、予約した前記区間から他の予約した前記区間への移動によって、前記第１移動体および前記第２移動体が存在する前記区間と、前記第１移動体および前記第２移動体の各々について予約された前記区間とを変化させて状態の異なる複数の前記環境モデルの集合を構築するステップと、前記第１移動体を前記第２移動体とのデッドロック状態に陥らせること無く、目的とする所定の前記区間まで移動させる要求に対し、前記集合に含まれる前記環境モデルの状態を他の前記環境モデルの状態へ変化させながら、前記要求を満たす前記環境モデルの状態へ至るまでの順序を探索するステップと、を実行させ、前記構築するステップでは、所定の制約条件に基づいて、前記制約条件に合致する前記環境モデルの状態を用いて前記集合を構築する。
　本発明の一態様によれば、プログラムは、コンピュータに、複数の区間に分割された軌道と、該軌道上を移動する制御対象の第１移動体および制御対象外の第２移動体と、によって構成される環境モデルについて、前記環境モデルの状態が、前記第１移動体および前記第２移動体の各々が存在する前記区間と、前記第１移動体および前記第２移動体の各々について予約された前記区間とによって決定され、前記第１移動体および前記第２移動体についての前記区間の予約と、前記予約の解除と、予約した前記区間から他の予約した前記区間への移動によって、前記第１移動体および前記第２移動体が存在する前記区間と、前記第１移動体および前記第２移動体の各々について予約された前記区間とを変化させて状態の異なる複数の前記環境モデルの集合を構築するステップと、前記第１移動体を前記第２移動体とのデッドロック状態に陥らせること無く、目的とする所定の前記区間まで移動させる要求に対し、前記集合に含まれる前記環境モデルの状態を他の前記環境モデルの状態へ変化させながら、前記要求を満たす前記環境モデルの状態へ至るまでの順序を探索するステップと、を実行させ、前記探索するステップでは、所定の制約条件に基づいて、前記制約条件に合致する前記環境モデルの状態へ遷移させつつ前記探索を行う。
　上記した進路制御プログラム生成装置、進路制御プログラム生成方法及びプログラムによれば、進路制御プログラム生成のための計算コストを削減することができる。
本発明の第一実施形態における進路制御プログラム生成装置の一例を示す図である。 本発明の第一実施形態における環境モデルの状態および状態遷移系を説明する図である。 本発明の第一実施形態における状態遷移の一例を示す第１の図である。 本発明の第一実施形態における状態遷移の一例を示す第２の図である。 本発明の第一実施形態における第１の制約条件を説明する図である。 本発明の第一実施形態における第２の制約条件を説明する図である。 本発明の第一実施形態における第３の制約条件を説明する図である。 本発明の第一実施形態における第４の制約条件を説明する第１の図である。 本発明の第一実施形態における第４の制約条件を説明する第２の図である。 本発明の第一実施形態における進路制御プログラムの生成処理の一例を示すフローチャートである。 本発明の第二実施形態における進路制御プログラム生成装置の一例を示す図である。 本発明の第二実施形態における進路制御プログラムの生成処理の一例を示すフローチャートである。 本発明の第三実施形態における進路制御プログラム生成装置の一例を示す図である。 本発明の第三実施形態における制約条件を説明する第１の図である。 本発明の第三実施形態における制約条件を説明する第２の図である。 本発明の第三実施形態における進路制御プログラムの生成処理の一例を示す第１のフローチャートである。 本発明の第三実施形態における進路制御プログラムの生成処理の一例を示す第２のフローチャートである。 本発明の第四実施形態における進路制御プログラム生成装置の一例を示す図である。 本発明の第四実施形態における制約条件を説明する図である。 本発明の各実施形態における進路制御プログラム生成装置のハードウェア構成の一例を示す図である。
＜第一実施形態＞
　以下、本発明の第一実施形態による進路制御プログラムの生成方法について図１～図１０を参照して説明する。
　図１は、本発明の第一実施形態における進路制御プログラム生成装置の一例を示す図である。図１に示すように進路制御プログラム生成装置１０（以下、生成装置１０と記載する。）は、環境モデル構築部１１と、要求設定部１２と、探索部１３と、入力受付部１４と、出力部１５と、記憶部１６と、を備える。
　環境モデル構築部１１は、閉そくを予約する、閉そくの予約を解除する、閉そく間を移動する等の行動によって移動体の位置や閉そくの予約状況が離散的に変わる状態遷移系を移動体や閉そく毎に構築する。また、本実施形態では、環境モデル構築部１１は、構築した状態遷移系について、所定の制約条件に適合する状態や状態遷移を示すもののみを残し、残った状態遷移系を環境モデルとする。所定の制約条件とは、例えば、以下の４つである。
　条件１）１つの移動体に予約された閉そくの数は予め定めた最大値以下である。
　条件２）１つの状態遷移において同時に予約する閉そくの最大数が予め定めた数以下である。
　条件３）進行方向の閉そくのみを予約する。
　条件４）在線中の閉そくから進行方向に数えて予め定めた数だけ先までの閉そくが予約可能である。
　本実施形態では、上記の制約条件の何れか又は複数が予め選択され、環境モデル構築部１１は、選択された条件を満たす状態遷移系のみで環境モデルを構築する。
　ここで、図２を参照して、環境モデルの状態および状態遷移系について説明する。図２は、本発明の第一実施形態における環境モデルの状態および状態遷移系を説明する図である。
　環境モデルは、複数の閉そくに分割された軌道と、軌道上に存在する１つの制御対象の移動体と、軌道上に存在する制御対象でない０以上の移動体とで構成される。環境モデルは、各移動体の位置や各閉そくに対する予約の状況に応じて様々な態様を取りうるが、その１つ１つを環境モデルの状態という。
　図２に、閉そくＢ０～Ｂ５に分割された軌道Ｂと、制御対象の移動体Ｘと、制御対象ではない移動体Ｙとで構成された環境モデルの状態の一例を示す。図２の例では、移動体Ｘが車庫ＩＢに存在し、移動体Ｙが閉そくＢ４に存在する。移動体Ｘについて、閉そくＢ０，Ｂ１，Ｂ５が予約されている。移動体Ｘと移動体Ｙの位置および閉そくの予約の状況は、図２に示す状態から様々に遷移し得る。本実施形態では、閉そく単位で各移動体向けの閉そくの予約および予約の解除を行う。１つの閉そくについて同時に１つの移動体のみが予約可能であり、１つの閉そくに同時に存在できるのは１つの移動体のみである。例えば、移動体Ｘが、閉そくＢ０へ移動するためには、まず、閉そくＢ０を予約し、その後、閉そくＢ０へ移動する。移動体Ｘが、閉そくＢ０を予約すると、移動体Ｙは、閉そくＢ０を予約することができない。そして、例えば、移動体Ｘが、閉そくＢ０から他の閉そくへ移動し、閉そくＢ０の予約が必要なくなると、閉そくＢの予約を解除する。
　実線矢印は、移動体Ｘについての閉そくＢ０～Ｂ５への進入方向を示し、破線矢印は、移動体Ｙについての閉そくＢ０～Ｂ５への進入方向を示している。例えば、閉そくＢ５について、移動体Ｘは閉そくＢ０から閉そくＢ５への移動、または、閉そくＢ４から閉そくＢ５への移動が可能であるが、移動体Ｙは閉そくＢ４から閉そくＢ５への移動のみが可能である。
　環境モデル構築部１１は、軌道Ｂと、移動体Ｘ，Ｙの位置と、移動体Ｘ，Ｙそれぞれについての閉そくの予約状況の組合せによって定まる環境モデルの状態を、例えば、全パターン生成する。例えば、図２の状態は、移動体Ｘについて閉そくＢ０，Ｂ１，Ｂ５を予約しているが、他にも閉そくＢ０のみを予約する状態、閉そくＢ０および閉そくＢ１を予約する状態、閉そくＢ０，Ｂ４，Ｂ５を予約する状態など、取りうる全ての予約状況に対応する環境モデルの状態を生成する。環境モデル構築部１１は、例えば、移動体Ｘと移動体Ｙが存在する閉そくを変化させて、その位置関係において取りうる全ての予約状況に対応する環境モデルの状態を生成する。生成した多数の環境モデルの状態の集合を状態遷移系と呼ぶ。
　要求設定部１２は、移動体Ｘ，Ｙの移動についての要求を設定する。要求は、セーフティ条件およびゴール条件から構成される。セーフティ条件とは、例えば「他移動体がどのような動きをした場合でも、衝突などの危険な結果に陥らない」、「制御対象列車がどのような制御をしても身動きできなくなるデッドロックに陥らない」等のいかなる場合でも到達してはならない禁止条件である。ゴール条件とは、例えば「車庫から出庫してデッドロックを起こさずに指定された駅に到着する」等、いつか満足しなければならない条件である。ゴール条件は「ある中間状態を満たした後、他の最終状態に至る」等の複数の目標状態の組み合わせで構成されていてもよい。本実施形態では、例えば、信号制御等の他の安全システムにより、ある閉そくには１つの移動体しか進入できない条件が担保されているとする。よって、移動体Ｘと移動体Ｙの衝突については考えず、制御対象の移動体Ｘが、デッドロックに陥ることなく目的地へ到着することを要求として設定する。
　探索部１３は、環境モデル（状態遷移系）上で、要求（セーフティ条件およびゴール条件）を満たす移動体Ｘ，Ｙの行動順序を探索する。例えば、探索部１３は、図２に例示する環境モデルの状態に対して、どの閉そくを予約するか、どの閉そくへの予約を解除するか、制御対象の移動体Ｘをどの閉そくまで移動させるかといった行動を対応付け、次の環境モデルの状態へ遷移させる（状態遷移）。探索部１３は、要求を満たす環境モデルの状態となるまで、この状態遷移を繰り返す。進路制御プログラムは、要求を満たす環境モデルの状態となるまでの状態遷移の順序である。換言すれば、進路制御プログラムは、開始時点の環境モデルの状態から、要求を満たす環境モデルの状態へ至るまでの各環境モデルの状態に対して、どの閉そくを予約するか、どの閉そくの予約を解除するか、各移動体をどの閉そくまで移動させるかといった行動を対応付けたものである。
　入力受付部１４は、ユーザの指示操作を受け付ける。
　出力部１５は、探索部１３による探索結果をモニタ等へ出力する。
　記憶部１６は、軌道の形状、閉そくの数、移動体の数、適用する制約条件などを記憶する。
　ここで、図３、図４を参照して、探索部１３による探索結果の例について説明する。
　図３は、本発明の第一実施形態における状態遷移の一例を示す第１の図である。図３に示すのは、要求を満たす状態遷移の例である。
　図３（ａ）～図３（ｆ）の各々は、環境モデルの１つの状態を示している。探索部１３は、移動体Ｘを目的地である閉そくＢ４へデッドロックさせないで移動させるという要求に対し、図３（ａ）の状態から、要求を満たす状態遷移を探索する。例えば、探索部１３は、図３（ａ）の状態に対して、移動体Ｘについて閉そくＢ０，Ｂ１，Ｂ５を予約するという行動を対応付ける。その行動をとったときの環境モデルの状態を図３（ｂ）に示す。このようにある環境モデルの状態に対して予約、予約の解除、移動を対応付けると環境モデルの状態が遷移する。図３（ｂ）に示す状態では、区間Ｂ５が予約されているために、移動体Ｙは、閉そくＢ５に侵入することができず、閉そくＢ４で待機する。次に探索部１３は、図３（ｂ）に示す状態に閉そくＢ０、Ｂ５への移動という行動を対応付ける。それらの行動による状態遷移後の環境モデルの状態は、図３（ｃ）に示す状態である。次に移動体Ｘが閉そくＢ５で方向を転換すると、図３（ｄ）に示す状態に遷移する。次に探索部１３は、図３（ｄ）に示す状態に対して、移動体Ｘを予約済みの閉そくＢ１へ移動するという行動を対応付ける。次に探索部１３は、移動体Ｘについて閉そくＢ２を予約するという行動、閉そくＢ２へ移動するという行動を順に対応付けて、環境モデルの状態を遷移させる。また、閉そくＢ０，Ｂ１，Ｂ５の予約を解除する。これらの行動により、環境モデルは図３（ｅ）に示す状態に遷移する。次に探索部１３は、図３（ｅ）に示す状態に対して、移動体Ｘについて閉そくＢ３，Ｂ４の予約、閉そくＢ３，Ｂ４への移動を対応付け、図３（ｆ）に示す状態に遷移する。図３（ａ）～図３（ｆ）の各状態および各状態に対応付けた行動が進路制御プログラムである。
　移動体Ｙについても同様に閉そくの予約、移動、予約の解除という行動を繰り返して状態遷移を行う。例えば、図３（ａ）～図３（ｂ）の間に、移動体Ｙは閉そくＢ３から閉そくＢ４へ移動している。その後、移動体Ｘが閉そくＢ５の予約を解除するまで移動体Ｙは閉そくＢ４で待機している。その後、移動体Ｙについては、閉そくＢ５の予約、閉そくＢ５への移動という行動などが対応付けられる。
　このように複数の閉そくに分割された軌道Ｂと、移動体Ｘ，Ｙの位置と、移動体Ｘ，Ｙのそれぞれが予約する閉そくとで決定される１つの環境モデルの状態は、軌道Ｂの形状、移動体Ｘ，Ｙの各閉そくへの進入方向、移動体Ｘ，Ｙ等の数、それぞれの移動体の位置関係や目的地などに応じて離散的に次の状態へ遷移する。
　次に状態遷移系の他の例について図４を参照して説明する。
　図４は、本発明の第一実施形態における状態遷移の一例を示す第２の図である。
　図４（ａ）～図４（ｃ）にデッドロック状態に陥る場合の状態遷移を示す。探索部１３は、図４（ａ）に示す環境モデルの状態に対し、移動体Ｘについて閉そくＢ０，Ｂ１を予約するという行動を対応付けて図４（ｂ）に示す状態へ遷移する。次に探索部１３は、図４（ｂ）の状態の移動体Ｘに対し、閉そくＢ０への移動を対応付け、図４（ｃ）の状態へ遷移する。図２の場合と異なり、移動体Ｘは閉そくＢ５を予約していない。その為、移動体Ｙは、閉そくＢ５へ移動する（図４（ｃ））。すると、図４（ｃ）に示すように移動体Ｘと移動体Ｙが互いに進むことができないデッドロック状態に陥る。探索部１３は、この例のように移動体Ｘがデッドロック状態に陥ると、その探索は失敗であるとしてその探索を中止する。
　以上、説明したように、探索部１３は、ある環境モデルの状態に対し、予約や移動などの行動を対応付け、環境モデルを状態遷移させる処理を繰り返し行い、要求を満たす状態に至る状態遷移の順序（解）を見つけ出す。ここで、探索部１３が、無数に存在する環境モデルの状態の全てを対象として、セーフティ条件とゴール条件を満たす解を探索すると計算コストが掛かりすぎる。そこで、本実施形態では、以下に説明する制約条件の何れか１つまたは複数に合致する状態または状態遷移のみを探索範囲として探索を行い、進路制御プログラムを生成する。
（制約条件１）
　図５は、本発明の第一実施形態における第１の制約条件を説明する図である。
　軌道Ｃは、閉そくＣ０～Ｃ９に分割されている。移動体Ｘは閉そくＣ０に存在し、移動体Ｙは閉そくＣ７に存在する。実線矢印は各閉そくへの移動体Ｘの進入方向を示し、破線矢印は各閉そくへの移動体Ｙの進入方向を示す。環境モデル構築部１１は、移動体Ｘについて、例えば、移動体Ｙが存在する閉そくＣ７を除く他の閉そくの全てを予約する状態を１つの環境モデルの状態として生成し得る。しかし、全閉そくを予約可能とすると、探索部１３による探索パターンが増える。そこで、本実施形態では、移動体Ｘ、Ｙについて予約できる閉そくの数に上限を設ける。図５に、閉そくを６つまで同時に予約可能な場合の予約例を示す。図５に示す例の場合、移動体Ｘについて予約された閉そくは、閉そくＣ１，Ｃ３，Ｃ４，Ｃ６，Ｃ８，Ｃ９の６つである。
　ここで、図５において（予約１）～（予約６）が付された閉そくは予約済みである事を示している。図５に示す例では、予約済みの閉そくの数は６つである。以下の図６～図９についても（予約１）等が記載された閉そくは予約済みであることを示すものとする。（予約１）の数字「１」は予約済みの閉そくの総数を数えるために付されたものであって、順番や序列を表すものでは無い。このことは、図６～図９においても同様である。
（制約条件２）
　図６は、本発明の第一実施形態における第２の制約条件を説明する図である。
　図６に示す環境モデルは、図５で説明したものと同様である。制約条件２は、１回の状態遷移において可能な閉そくの予約数に関する。例えば、図６の上図から下図の状態へ遷移する場合に、移動体Ｘについて予約可能な閉そくの数に上限を設ける。例えば、図６の上図では、移動体１についての閉そくの予約数が０であるとする。１つの状態遷移において同時に予約する閉そくの最大数に３が設定されている場合、図６の上図の次の状態において、最大で３つの閉そくを予約することができる。図６の下図は、３つの閉そくＣ１，Ｃ２，Ｃ９を予約した後の状態を示している。
（制約条件３）
　図７は、本発明の第一実施形態における第３の制約条件を説明する図である。
　制約条件３は、各移動体について、進行方向の閉そくのみを予約できるという条件である。この制約条件によれば、図７に示す環境モデルの状態では、移動体Ｘについて、閉そくＣ０を予約することができない。
（制約条件４）
　図８．図９は、それぞれ、本発明の一実施形態における第４の制約条件を説明する第１の図、第２の図である。
　制約条件４では、現在の移動体の位置を基準として予約可能な閉そくの範囲に上限を設ける。この上限が３の場合、例えば、図８に示す環境モデルの状態での移動体Ｘについて、閉そくＣ１、Ｃ２、Ｃ９が予約可能な範囲である。例えば、図８の移動体Ｘについて、閉そくＣ１、Ｃ９を予約することができる。
　制約条件４に関して、閉そく範囲の最大数は、移動体の進路と軌道の形状によって決める事ができる。閉そく範囲の最大数が大きいとデッドロックを回避しやすくなるが探索部１３による探索範囲が広がり計算コストが増加する。図９に制約条件４を適用する他の例を示す。図９に例示する軌道Ｄは、閉そくＤ０～Ｄ４に分割されている。移動体Ｘは閉そくＤ０に存在し、移動体Ｙは閉そくＤ４に存在する。実線矢印は移動体Ｘの進入方向を示し、破線矢印は移動体Ｙの進入方向を示す。図９に示す軌道Ｄの形状、移動体Ｘ，Ｙの進路および位置の場合、例えば、予約可能な閉そくの範囲を２つ先までと設定する。例えば、移動体Ｘが閉そくＤ１，Ｄ２を予約すれば、移動体Ｘと移動体Ｙは、デッドロック状態に陥ることなく、それぞれの進行方向に移動することができる。
　図１０は、本発明の第一実施形態における進路制御プログラムの生成処理の一例を示すフローチャートである。
　まず、環境モデル構築部１１は、各移動体、各閉そくについて状態遷移系を構築する（ステップＳ１１）。環境モデル構築部１１は、各移動体Ｘ，Ｙについて各閉そくへの予約、移動、予約の解除によって、移動体Ｘ，Ｙの位置や閉そくの予約状況が離散的に変化する状態を網羅的に生成する。生成された多数の状態が状態遷移系である。
　次に環境モデル構築部１１は、環境モデルを構築する（ステップＳ１２）。具体的には、制約条件１～４のうちの何れかを適用するかが予め設定されていて、環境モデル構築部１１は、適用される制約条件を満たす環境モデルの状態だけを残す。残った環境モデルの状態の集合を環境モデルとする。例えば、制約条件１について予約数の上限値が６であれば、環境モデル構築部１１は、ステップＳ１１で生成した各状態のうち、移動体Ｘ，Ｙの何れかについて７つ以上の閉そくが予約された状態を除外する。例えば、環境モデル構築部１１は、制約条件１の条件を満たさない環境モデルの状態を削除してもよいし、この環境モデルの状態に対して、除外対象であることを示す情報を付加してもよい。制約条件３および制約条件４についても同様である。状態遷移に関する制約条件２については、例えば、状態１から状態２への状態遷移が、制約条件２を満たさないようであれば、環境モデル構築部１１は、状態１に対して、状態２への遷移を除外するような情報を付加してもよい。
　次に要求設定部１２が、移動体Ｘ、Ｙの移動についての要求を設定する（ステップＳ１３）。例えば、図２、図３の例であれば、要求設定部１２は、セーフティ条件としてデッドロックが生じないこと、ゴール条件として移動体Ｘの目的地を閉そくＢ４として設定する。要求設定部１２は、要求とともに初期条件（例えば、図３（ａ）の状態から開始すること）を設定してもよい。セーフティ条件、ゴール条件、初期条件は、予め記憶部１６に登録されていてもよいし、ユーザが生成装置１０へ入力してもよい。
　次にユーザは、進路制御プログラムの生成指示を生成装置１０へ入力する。入力受付部１４は、この指示操作の入力を受け付け、探索部１３へプログラムの生成を指示する。探索部１３は、移動体Ｘおよび移動体Ｙについて、要求を満たす行動順序を探索する（ステップＳ１４）。探索部１３は、図３、図４を用いて説明したように、初期条件が示す環境モデルの状態に対して、閉そくの予約、移動、予約の解除などの行動を対応付け、状態遷移を行い、最終的に要求を満たす環境モデルの状態へ遷移させることができる場合に遷移中の各状態に対して対応付ける行動を探索する。次に探索部１３は、要求を満たす行動順序が存在するかどうかを判断する（ステップＳ１５）。例えば、探索部１３は、図４（ａ）の状態から図４（ｂ）の状態へ遷移し、その後、図４（ｃ）の状態へ遷移するような探索を行った場合、このときの行動順序は要求を満たさないと判断する。例えば、探索部１３は、図３（ａ）の状態から、図３（ｂ）～図３（ｆ）の各状態へこの順で遷移するような探索を行った場合、このときの行動順序は要求を満たすと判断する。要求を満たす行動順序が存在する場合（ステップＳ１５；Ｙｅｓ）、出力部１５は、探索部１３が探索した行動順序をモニタへ出力する（ステップＳ１６）。例えば、出力部１５は、図３（ａ）～図３（ｆ）へ至るまでの各環境モデルの状態と、各状態に対応付けられた行動の情報を出力する。出力された情報が進路制御プログラムである。
　次にユーザは、別の行動順序を探索するかどうかを生成装置１０へ入力する。入力受付部１４は、この指示操作の入力を受け付ける。別の行動順序を探索する旨が入力された場合（ステップＳ１７；Ｙｅｓ）、入力受付部１４は、探索部１３へ再度の探索を指示する。探索部１３は、移動体Ｘおよび移動体Ｙについて、要求を満たす別の行動順序を探索する（ステップＳ１４）。
　別の行動順序を探索しない旨が入力された場合（ステップＳ１７；Ｎｏ）、生成装置１０は、進路制御プログラムの生成処理を終了する。
　全パターン探索しても、要求を満たす行動順序が見つからない場合（ステップＳ１５；Ｎｏ）、探索部１３は解なしと判断する。例えば、出力部１５は「解なし」をモニタに表示する。
　本実施形態によれば、環境モデルの状態を網羅的に生成し、その中から所定の制約条件に合致するもののみを探索対象とする。これにより、要求を満足する進路制御プログラムを、制約条件を設けない場合と比べて少ない計算コストで生成することができる。特に閉そくの数や移動体の数が多い場合の計算コストの低減に有効である。
＜第二実施形態＞
　次に図１１、図１２を参照して、第二実施形態における進路制御プログラムの生成処理について説明する。第一実施形態では、制約条件１～４に適合しない環境モデルの状態を状態遷移系から削除することにより環境モデルの規模を小さくすることで計算コストの削減を図った。第二実施形態では、探索部１３ａが要求を満たす行動手順を探索する際に、制約条件１～４に適合する範囲で移動体の行動を探索する。
　図１１は、本発明の第二実施形態における進路制御プログラム生成装置の一例を示す図である。第一実施形態と同様の処理、構成については簡単に説明する。
　進路制御プログラム生成装置１０ａは、環境モデル構築部１１ａと、要求設定部１２と、探索部１３ａと、入力受付部１４と、出力部１５と記憶部１６とを備える。
　要求設定部１２、入力受付部１４、出力部１５、記憶部１６の機能は第一実施形態と同様である。
　環境モデル構築部１１ａは、軌道と、制御対象の移動体および制御対象外の移動体の位置、各閉そくの予約状況の全パターンの組合せによって構成される状態遷移系を構築する。第二実施形態では、この状態遷移系を環境モデルとする。
　探索部１３ａは、状態遷移系上で、セーフティ条件およびゴール条件を満たす移動体の行動順序を探索する。第二実施形態では、探索部１３ａは、行動順序の探索の際に制約条件１～４のうちの予め選択された条件を適用して探索範囲を限定する。
　図１２は、本発明の第二実施形態における進路制御プログラムの生成処理の一例を示すフローチャートである。第一実施形態と同様の処理については簡単に説明を行う。
　制約条件１～４の何れを適用するかについては、予め設定されているとする。あるいは、ステップＳ１３で要求とともに設定してもよい。
　まず、環境モデル構築部１１ａは、各移動体の位置、各閉そくの予約状況を網羅的に変化させた状態遷移系を構築する（ステップＳ１１）。次に要求設定部１２が、移動体Ｘの移動についての要求を設定する（ステップＳ１３）。
　次に探索部１３ａは、ユーザの指示などにより、制御対象の移動体および他の移動体について要求を満たす行動順序を探索する（ステップＳ１４ａ）。第一実施形態と異なり、探索部１３ａは、設定された制約条件１～４に適合するように状態遷移させて探索する。例えば、制約条件１が設定されている場合、図３（ａ）の状態から次の状態へ遷移させる際に、探索部１３ａは、制約条件１に適合する環境モデルの状態の中から遷移先の状態を選択する。例えば、閉そくを６つまで同時に予約可能な場合、探索部１３ａは、現在の環境モデルの状態に対して、閉そくが７つ予約された状態となるような行動を対応付けない。他の制約条件２～４についても同様である。次に探索部１３ａは、要求を満たす行動順序が存在するかどうかを判断する（ステップＳ１５）。要求を満たす行動順序が存在する場合（ステップＳ１５；Ｙｅｓ）、出力部１５は、探索部１３ａが探索した行動順序をモニタへ出力する（ステップＳ１６）。
　別の行動順序を探索する場合（ステップＳ１７；Ｙｅｓ）、探索部１３ａは、要求を満たす別の行動順序を探索する（ステップＳ１４ａ）。別の行動順序を探索しない場合（ステップＳ１７；Ｎｏ）、生成装置１０ａは、進路制御プログラムの生成処理を終了する。
　全パターン探索しても、要求を満たす行動順序が見つからない場合（ステップＳ１５；Ｎｏ）、探索部１３ａは解なしと判断する。
　本実施形態によれば、第一実施形態と同様、要求を満足することが保障された進路制御プログラムを少ない計算コストで生成することができる。
　上記実施形態では、制御対象の第１移動体（移動体Ｘ）に対し、制御対象外の第２移動体（移動体Ｙ）が、１台の場合を例に説明を行ったが、第２移動体が軌道上に複数存在しても、同様である。例えば、制御対象の移動体Ｘの他に、軌道上に制御対象外の移動体Ｙと移動体Ｚの２台が存在する場合、生成装置１０は、移動体Ｘ，Ｙ，Ｚの３台に対して、制約条件１～制約条件４の条件下で状態遷移を行って行動順序を探索する（第一実施形態）。生成装置１０ａは、制約条件１～制約条件４の条件下で状態遷移系の構築を行う（第二実施形態）。また、上記の実施形態では、第１移動体（移動体Ｘ）と第２移動体（移動体Ｙ）のそれぞれについて制約条件１～４を課すこととしたが、第１移動体と第２移動体のうちの少なくとも一つに制約条件１等を課せばよく、例えば、軌道上に移動体Ｘ，Ｙ，Ｚ（移動体Ｘが第１移動体、移動体Ｙ，Ｚが第２移動体）の３台が存在する場合、移動体Ｘ，Ｙ，Ｚの３台のうち少なくとも一つに対して、制約条件１～４を課して行動順序の探索や状態遷移系の構築を行ってもよい。
　第２移動体が複数存在してもよいことや、第１移動体と第２移動体のうちの少なくとも一つに制約条件を課せばよいことは、以下の第三実施形態、第四実施形態においても同様である。
＜第三実施形態＞
　次に図１３～図１７を参照して、第三実施形態における進路制御プログラムの生成処理について説明する。第一実施形態、第二実施形態で説明したように、本開示では、閉そくの予約、予約の解除、移動、待機によって、環境モデルの状態を変化させながら、目的地まで移動体Ｘ、Ｙを移動させる行動順序を探索して進路制御プログラムを作成する。進路制御プログラムでは時間の概念は含まれないが、実際の世界では、移動体Ｘ，Ｙの移動もしくは待機の制御には時間がかかり、移動・待機が完了した時点では、制御に要した時間の経過に伴って、実際の環境の状態も変化している。つまり、環境モデル上での移動体Ｘ、Ｙの移動・待機を伴った１回の状態遷移は、実際には実時間の経過を伴う。これに対し、閉そくの予約や予約の解除は、電子的な処理だけで済むので、移動体Ｘ、Ｙの移動・待機と比較して実時間の経過を無視できる早さで行動が完了する。よって、複数の予約、予約の解除は同時処理が可能とみなせる。例えば、移動体Ｘが１つ隣の閉そくへ移動する間に、閉そくの予約、予約の解除というアクションを多数実行することができる。ここで、移動体Ｘ，Ｙの実際の制御に要する時間（例えば、隣の閉そくへの移動、現在存在する閉そくに停止させて待機する制御に要する時間）に対応する、その制御によって生じる環境モデルの状態の遷移に対応する離散的な経過時間を表現するため論理時間経過という概念を導入する。移動もしくは待機による１回の状態遷移は１単位の論理時間経過に相当し、この間の経過時間を１論理時間とする。移動体Ｘ，Ｙの移動・待機、予約、予約の解除、に要する実際の時間に対応させて、移動体を目的地へ到達させる行動順序を探索する処理において、１論理時間内に実行できる行動を定義する。例えば、１論理時間内に実行可能な行動は、複数回の閉そくの予約、複数回の予約の解除、１回の移動もしくは１回の待機、である。移動もしくは待機の後に他の行動（予約、予約の解除、移動、待機）は実行できない。移動もしくは待機の制御を完了するためには実時間を要するので、環境の状態も遷移してしまうからである。
　１論理時間に実行できる閉そくの予約、予約の解除に制約を設けない場合、行動の探索（図１０のステップＳ１４、図１２のステップＳ１４ａ）において、ある閉そくを予約した直後にその閉そくの予約を開放する等の無駄な探索パターンが入り込む場合がある。「予約した直後」とは、「予約制御を完了した後、制御対象とする移動体Ｘ等の移動制御や他の移動体Ｙ等の状態遷移が発生する前」である。よって、予約直後の予約の解除は状態遷移が起こっていない事と同じ結果になり、無駄な制御である。予約直後の解除を探索可能にすると、無駄な制御の探索が可能になり、進路制御プログラムの計算に時間がかかる。予約済みの閉そくを解除して、直後に同じ閉そくを予約する場合についても同様である。このように電子的な処理である予約、予約の解除に制約を設けないと、無駄な探索が生じ得る。第三実施形態では、１論理時間における行動手順を探索する際に、１論理時間内に実行できる行動に制約を設ける（制約条件α）。例えば、１論理時間内に実行可能な予約と予約の解除の総回数に上限を設け、無駄な探索が無制限に発生することを防ぐ。
　図１３は、本発明の第三実施形態における進路制御プログラム生成装置の一例を示す図である。
　第一実施形態と同様の処理、構成については簡単に説明する。
　進路制御プログラム生成装置１０ｂは、環境モデル構築部１１ｂと、要求設定部１２と、探索部１３ｂと、入力受付部１４と、出力部１５と、記憶部１６とを備える。要求設定部１２、入力受付部１４、出力部１５、記憶部１６の機能は第一実施形態と同様である。
　環境モデル構築部１１ｂは、軌道と、制御対象の移動体および制御対象外の移動体の位置、各閉そくの予約状況の全パターンの組合せによって構成される状態遷移系を構築する。さらに、環境モデル構築部１１ｂは、構築した状態遷移系の中から制約条件αを満たす状態を選択して環境モデルを構築する機能を有する。
　探索部１３ｂは、環境モデル構築部１１ｂが構築した環境モデルについて、セーフティ条件およびゴール条件を満たす移動体の行動順序を探索する。さらに、探索部１３ｂは、行動順序の探索の際に制約条件αを適用した限定された探索範囲を対象に行動順序を探索する機能を有する。
　次に図１４、図１５を参照して、制約条件αについて説明する。
　図１４、図１５は、本発明の第三実施形態における制約条件を説明する第１の図、第２の図である。
　図１４、図１５に、同一論理時間内の行動の探索パス示すツリーを示す。
　図１４、図１５において、実線矢印は、移動・待機を示す。破線矢印は、閉そくに対する予約を示す。一点鎖線の矢印は、閉そくに対する予約の解除を示す。１つの実線矢印は、１回の移動もしくは待機を示す。１つの破線矢印は、１つの閉そくに対する１回の予約を示し、１つの一点鎖線矢印は、予約済みの１つの閉そくに対する１回の予約の解除を示す。右側の１回目、２回目、・・・、は、行動の回数を示している。
　図１４に予約および予約の解除の合計に上限を設けない場合の探索パスの一例を示す。ノードＰ０から開始して１回目の行動として、移動もしくは待機を選択した場合、実線矢印のパスに沿ってノードＰ３に至る。ノードＰ３からは、次のパスは伸びていない。これは、１回の移動もしくは待機によって、１論理時間が終了することを示している。ノードＰ０から開始して１回目の行動として、任意の閉そくの予約を行うとノードＰ２に至り、任意の予約済みの閉そくの解除を行うとノードＰ１に至る。何れの場合も１回の予約、予約の解除によっては、１論理時間は完了しない為、２回目の行動として、移動もしくは待機、予約、予約の解除の何れかを選択することができる。例えば、ノードＰ１，Ｐ２のそれぞれにおいて、２回目の行動として移動もしくは待機を選択すると、ノードＰ６，Ｐ９へ至り現在の論理時間は完了する。ノードＰ１，Ｐ２のそれぞれにおいて、２回目の行動として予約、予約の解除を選択した場合には、選択した行動に応じてノードＰ４，Ｐ５，Ｐ７，Ｐ８の何れかへ至る。図１４の３回目以降の行動についても同様である。１論理時間における予約、予約の解除の回数に上限を設けない場合、各ノードにおいて選択される行動が、予約又は予約の解除の場合、図１４に例示するツリーは際限なく拡大し得る。これを防止するために、１論理時間内における予約の回数と予約の解除の回数の合計値に上限を設ける。
　図１５に予約と予約の解除の総回数の上限を３回に設定したときの探索パスのツリーを示す。上限を３回に設定した場合、ノードＰ０から１回目の行動として予約の解除を選択しノードＰ１に至り、２回目の行動として予約の解除を選択しノードＰ４に至り、３回目の行動として予約の解除を行ってノードＰ１０に至った場合、既に予約の解除を３回行っているので、この論理時間では、これ以上、予約、予約の解除および移動もしくは待機を行うことはできず、この論理時間は完了する。この様子を×印で表す。×印は、そのノードへ到達できないことを示す。例えば、ノードＰ０から１回目の行動として予約の解除を選択しノードＰ１に至り、２回目の行動として予約を選択しノードＰ５に至り、３回目の行動として予約の解除を行ってノードＰ１２に至った場合、予約を１回、予約の解除を２回行っているので、予約と予約の解除の総回数は上限の３回になり、これ以上、予約、予約の解除を行うことはできない。他のＰ１１、Ｐ１３～Ｐ１７についても同様である。このように、予約と予約の解除の総回数に上限を設けることによって、探索パスの増加を防ぐことができる。制約条件αとは、予約と予約の解除の総回数に上限を設けることである。制約条件αは、移動体Ｘ、Ｙのうちの少なくとも一つについて適用する。
　予約と予約の解除の総回数の上限値は予め設定されていてもよいが、次のようにして定めてもよい。つまり、総回数の上限は、連続する分岐閉そくの数など、路線の複雑さによって設計者が適切に設定する必要があるが、膨大な組合せパターンを含む制御が可能な環境条件において、人が適切な一定回数を設定することは困難である。そこで、最初は、総回数の上限値を１とし、進路制御プログラムの解が無い場合、解を得られるまで総回数の上限値を所定値（例えば、１）ずつ増加させる。このようにして上限値を設定することにより、解が得られる最低の上限値における、セーフティ条件およびゴール条件を満たし、かつ無駄な行動を極小に抑える解（行動手順）を得ることができる。
　図１６は、本発明の第三実施形態における進路制御プログラムの生成処理の一例を示す第１のフローチャートである。第一実施形態と同様の処理については簡単に説明を行う。予約と予約の解除の総回数の上限値の初期値として、例えば、１が設定されている。
　まず、環境モデル構築部１１は、各移動体の位置、各閉そくの予約状況を網羅的に変化させた状態遷移系を構築する（ステップＳ１１）。環境モデル構築部１１は、構築した状態遷移系の全てを記憶部１６へ記録する。次に環境モデル構築部１１は、環境モデルを構築する（ステップＳ１２）。環境モデル構築部１１は、ステップＳ１１で構築した状態遷移系の中から、１回の移動もしくは待機によって環境モデルの状態が１つ遷移する時間を１論理時間としたときに、移動体Ｘ、Ｙのうちの少なくとも一つについて、１論理時間に実行可能な行動の要求を満たす環境モデルの状態だけを残す。１論理時間に実行可能な行動の要求とは、上限値内の閉そくの予約および予約の解除、１回の移動もしくは待機である。１回の移動もしくは待機に関し、移動もしくは待機の前に、上限値未満の回数の予約、予約の解除を行うことは可能だが、１回の移動もしくは待機後の予約、予約の解除は実行できない。残った環境モデルの状態の集合を環境モデルとする。例えば、予約と予約の解除の総回数の上限値が１の場合、図１５において、ノードＰ１，Ｐ２からのその先のノードへ至るような行動を採ることはできない。環境モデル構築部１１は、そのような行動の結果が含まれた状態を除外する。例えば、環境モデル構築部１１は、総回数の上限値が１を超える環境モデルの状態を削除してもよいし、この環境モデルの状態に対して、除外対象であることを示す情報を付加してもよい。
　次に要求設定部１２が、移動体Ｘ、Ｙの移動についての要求を設定する（ステップＳ１３）。次に探索部１３ｂが、制御対象の移動体Ｘおよび他の移動体Ｙについて要求を満たす行動順序を探索する（ステップＳ１４）。次に探索部１３ｂは、要求を満たす行動順序が存在するかどうかを判断する（ステップＳ１５）。要求を満たす行動順序が存在する場合（ステップＳ１５；Ｙｅｓ）、出力部１５は、探索部１３ｂが探索した行動順序をモニタへ出力する（ステップＳ１６）。別の行動順序を探索する場合（ステップＳ１７；Ｙｅｓ）、探索部１３ｂは、要求を満たす別の行動順序を探索する（ステップＳ１４）。別の行動順序を探索しない場合（ステップＳ１７；Ｎｏ）、生成装置１０ｂは、進路制御プログラムの生成処理を終了する。
　全パターン探索しても、要求を満たす行動順序が見つからない場合（ステップＳ１５；Ｎｏ）、探索部１３ｂは解なしと判断する。解なしの場合、生成装置１０ｂ（例えば、環境モデル構築部１１ｂ）は、予約と予約の解除の総回数の上限値に１を加算する。そして、再びステップＳ１２以降の処理を繰り返す。例えば、ステップＳ１２において、環境モデル構築部１１ｂは、記憶部１６に保存した状態遷移系を読み出して、予約と予約の解除の総回数の上限値が、加算後の値を超える状態が含まれた環境の状態を削除して、環境モデルを構築する。そして、生成装置１０ｂは、ステップＳ１３以降の処理を実行する。
　本実施形態によれば、１論理時間内の各閉そくの予約、予約の解除の発生をカウントし、これらの合計数が一定回数（上限値）に達した場合は，同論理時間内ではそれ以上の予約、予約の解除が発生することを禁止する。これにより、例えば、同じ閉そくに対して、無限に予約と予約の解除を無制限に繰り返すような探索パターンの発生を防止することができる。予約と予約の解除の総回数に上限を設けることで、例えば、移動体Ｘによって全ての閉そくが予約され、移動体Ｙが動けなくなるような無駄な探索パターンの発生を防ぐことができる。このように本実施形態によれば、探索空間が削減され、計算時間を短縮することができる。
　第三実施形態は、第一実施形態と組み合わせることが可能である。つまり、図１６のフローチャートのステップＳ１２にて、環境モデル構築部１１ｂは、制約条件αに加えて、第一実施形態で説明した制約条件１～４の何れか又は全部を満たす状態だけを残して環境モデルを構築してもよい。
　第三実施形態は、第二実施形態と組み合わせることが可能である。第二実施形態と組み合わせた場合の処理を図１７に示す。
　図１７は、本発明の第三実施形態における進路制御プログラムの生成処理の一例を示す第２のフローチャートである。第二実施形態と同様の処理については簡単に説明を行う。
　まず、環境モデル構築部１１ｂは、各移動体の位置、各閉そくの予約状況を網羅的に変化させた状態遷移系を構築する（ステップＳ１１）。次に要求設定部１２が、移動体Ｘの移動についての要求を設定する（ステップＳ１３）。
　次に探索部１３ｂは、制御対象の移動体および他の移動体について要求を満たす行動順序を探索する（ステップＳ１４ａ）。探索部１３ｂは、制約条件α、又は、制約条件αおよび制約条件１～４の何れかに適合するように状態遷移を行って探索する。次に探索部１３ｂは、要求を満たす行動順序が存在するかどうかを判断する（ステップＳ１５）。要求を満たす行動順序が存在する場合（ステップＳ１５；Ｙｅｓ）、出力部１５は、探索部１３ｂが探索した行動順序をモニタへ出力する（ステップＳ１６）。別の行動順序を探索する場合（ステップＳ１７；Ｙｅｓ）、探索部１３ｂは、要求を満たす別の行動順序を探索する（ステップＳ１４ａ）。別の行動順序を探索しない場合（ステップＳ１７；Ｎｏ）、生成装置１０ａは、進路制御プログラムの生成処理を終了する。全パターン探索しても、要求を満たす行動順序が見つからない場合（ステップＳ１５；Ｎｏ）、探索部１３ａは解なしと判断する。探索部１３ｂは解なしと判断する。解なしの場合、環境モデル構築部１１ｂは、予約と予約の解除の総回数の上限値に１を加算する。そして、生成装置１０ｂは、再びステップＳ１４ａ以降の処理を繰り返す。これにより、探索空間を制限し、計算時間を短縮することができる。
＜第四実施形態＞
　次に図１８～図１９を参照して、第四実施形態における進路制御プログラムの生成処理について説明する。
　図１８は、本発明の第四実施形態における進路制御プログラム生成装置の一例を示す図である。
　第一実施形態と同様の処理、構成については簡単に説明する。
　進路制御プログラム生成装置１０ｃは、環境モデル構築部１１ｃと、要求設定部１２と、探索部１３ｃと、入力受付部１４と、出力部１５と記憶部１６とを備える。要求設定部１２、入力受付部１４、出力部１５、記憶部１６の機能は第一実施形態と同様である。
　環境モデル構築部１１ｃは、軌道と、制御対象の移動体および制御対象外の移動体の位置、各閉そくの予約状況の全パターンの組合せによって構成される状態遷移系を構築する。さらに、環境モデル構築部１１ｃは、構築した状態遷移系の中から、次に説明する制約条件βを満たす状態を選択して環境モデルを構築する機能を有する。
　探索部１３ｃは、環境モデル構築部１１ｃが構築した環境モデルについて、セーフティ条件およびゴール条件を満たす移動体の行動順序を探索する。さらに、探索部１３ｃは、行動順序の探索の際に制約条件βを適用した限定された探索範囲を対象に行動順序を探索する機能を有する。
　次に図１９を参照して、制約条件βについて説明する。
　図１９は、本発明の第四実施形態における制約条件を説明する図である。
　第四実施形態では、図１９において、移動体Ｘ、Ｙのうち少なくとも一つが１論理時間に実行できる予約と予約の解除について、次の制約を加える。（β１）ある閉そくの予約の発生は１論理時間あたり１回までとする。（β２）ある閉そくの予約の解除の発生は１論理時間あたり１回までとする。（β３）ある閉そくに対して予約もしくは予約の解除が発生した場合、同じ論理時間内で他方の行動は発生しない。第四実施形態において、１論理時間内に１つの移動体が選択可能な行動は、１回の移動もしくは待機、各閉そくに対し１回の閉そくの予約（β１）、各閉そくに対し１回の予約の解除（β２）であって、同じ閉そくに対する予約と予約直後の予約の解除、又は、同じ閉そくに対する予約の解除と解除直後の予約は選択できない（β３）。（１回の移動もしくは待機の前に各閉そくに対し１回の予約および予約の解除の何れかを行うことは可能だが、１回の移動もしくは待機の後の行動は不可である。）これらβ１～β３が制約条件βである。例えば、移動体Ｘは、１論理時間において閉そくＢ５を予約し、その直後に閉そくＢ５の予約の解除を行うことはできない（β３）。
　制約条件βにより、適切な上限値の設定を行うことなく、探索空間を削減し、探索に要する計算時間を短縮できる。第三実施形態では、上限値を超えない範囲での同一閉そくに対する予約と予約の解除を繰り返す行動を排除できなかったが、制約条件βによれば、この無駄な行動を完全に排除することができる。
　第四実施形態における進路制御プログラムの生成処理の流れについては、図１０で説明したものと同様である。第四実施形態の場合には、ステップＳ１２にて、環境モデル構築部１１ｃは、制約条件βを満たす環境モデルの状態だけを残して、環境モデルを構築する。あるいは、生成装置１０ｃは、図１２で説明した処理と同様の手順で進路制御プログラムを生成してもよい。この場合、図１２のステップＳ１４ａにて、探索部１３ｃは、制約条件βを満たす状態遷移を選んで探索を行う。
　さらに第四実施形態は、第一実施形態、第三実施形態と組み合わせることが可能である。つまり、図１０のフローチャートのステップＳ１２にて、環境モデル構築部１１ｃは、制約条件βに加えて、第一実施形態で説明した制約条件１～４および第三実施形態で説明した制約条件αの何れか又は全部を満たす状態だけを残して環境モデルを構築してもよい。
　第四実施形態は、第二実施形態、第三実施形態と組み合わせることが可能である。つまり、図１２のフローチャートのステップＳ１４ａにて、探索部１３ｃは、制約条件βに加えて、第一実施形態で説明した制約条件１～４および第三実施形態で説明した制約条件αの何れか又は全部を満たすように状態を遷移させて探索を行うことができる。
　なお、第四実施形態に関連して、１論理時間において、１つの閉そくに対して予約および予約の解除の両方が実行されることを禁止するという制約条件を、１又は複数の任意の閉そくに対して課してもよい。
　図１３は、本発明の各実施形態における進路制御プログラム生成装置のハードウェア構成の一例を示す図である。
　コンピュータ９００は、ＣＰＵ９０１、主記憶装置９０２、補助記憶装置９０３、入出力インタフェース９０４、通信インタフェース９０５を備える例えばＰＣ（Personal Computer）、サーバ端末装置などである。上述の進路制御プログラム生成装置１０，１０ａ，１０ｂ，１０ｃは、コンピュータ９００に実装される。そして、上述した各処理部の動作は、プログラムの形式で補助記憶装置９０３に記憶されている。ＣＰＵ９０１は、プログラムを補助記憶装置９０３から読み出して主記憶装置９０２に展開し、当該プログラムに従って上記処理を実行する。ＣＰＵ９０１は、プログラムに従って、記憶部１６に対応する記憶領域を主記憶装置９０２に確保する。ＣＰＵ９０１は、プログラムに従って、処理中のデータを記憶する記憶領域を補助記憶装置９０３に確保する。
　少なくとも１つの実施形態において、補助記憶装置９０３は、一時的でない有形の媒体の一例である。一時的でない有形の媒体の他の例としては、入出力インタフェース９０４を介して接続される磁気ディスク、光磁気ディスク、ＣＤ－ＲＯＭ、ＤＶＤ－ＲＯＭ、半導体メモリ等が挙げられる。このプログラムが通信回線によってコンピュータ９００に配信される場合、配信を受けたコンピュータ９００が当該プログラムを主記憶装置９０２に展開し、上記処理を実行しても良い。当該プログラムは、前述した機能の一部を実現するためのものであっても良い。さらに、当該プログラムは、前述した機能を補助記憶装置９０３に既に記憶されている他のプログラムとの組み合わせで実現するもの、いわゆる差分ファイル（差分プログラム）であっても良い。
　その他、本発明の趣旨を逸脱しない範囲で、上記した実施の形態における構成要素を周知の構成要素に置き換えることは適宜可能である。この発明の技術範囲は上記の実施形態に限られるものではなく、本発明の趣旨を逸脱しない範囲において種々の変更を加えることが可能である。
　移動体Ｘは第１移動体の一例、移動体Ｙは第２移動体の一例である。閉そくＢ０～Ｂ５、閉そくＣ０～Ｃ９、閉そくＤ０～Ｄ４は、区間の一例である。
　上記した進路制御プログラム生成装置、進路制御プログラム生成方法及びプログラムによれば、進路制御プログラム生成のための計算コストを削減することができる。
１０、１０ａ、１０ｂ、１０ｃ　　　進路制御プログラム生成装置
１１、１１ａ、１１ｂ、１１ｃ　　　環境モデル構築部
１２　　　要求設定部
１３、１３ａ、１３ｂ、１３ｃ　　　探索部
１４　　　入力受付部
１５　　　出力部
１６　　　記憶部
９００　　　コンピュータ
９０１　　　ＣＰＵ
９０２　　　主記憶装置
９０３　　　補助記憶装置
９０４　　　入出力インタフェース
９０５　　　通信インタフェース

Claims (15)

  1. 　複数の区間に分割された軌道と、該軌道上を移動する制御対象の第１移動体および制御対象外の第２移動体と、によって構成される環境モデルについて、前記環境モデルの状態が、前記第１移動体および前記第２移動体の各々が存在する前記区間と、前記第１移動体および前記第２移動体の各々について予約された前記区間とによって決定され、前記第１移動体および前記第２移動体についての前記区間の予約と、前記予約の解除と、予約した前記区間から他の予約した前記区間への移動によって、前記第１移動体および前記第２移動体が存在する前記区間と、前記第１移動体および前記第２移動体の各々について予約された前記区間とを変化させて状態の異なる複数の前記環境モデルの集合を構築する環境モデル構築部と、
    　前記第１移動体を、前記第２移動体とのデッドロック状態に陥らせること無く、目的とする所定の前記区間まで移動させる要求に対し、前記集合に含まれる前記環境モデルの状態を他の前記環境モデルの状態へ変化させながら、前記要求を満たす前記環境モデルの状態へ至るまでの順序を探索する探索部と、
    　を備え、
    　前記環境モデル構築部は、所定の制約条件に基づいて、前記制約条件に合致する前記環境モデルの状態を用いて前記集合を構築する、
    　進路制御プログラム生成装置。
  2. 　複数の区間に分割された軌道と、該軌道上を移動する制御対象の第１移動体および制御対象外の第２移動体と、によって構成される環境モデルについて、前記環境モデルの状態が、前記第１移動体および前記第２移動体の各々が存在する前記区間と、前記第１移動体および前記第２移動体の各々について予約された前記区間とによって決定され、前記第１移動体および前記第２移動体についての前記区間の予約と、前記予約の解除と、予約した前記区間から他の予約した前記区間への移動によって、前記第１移動体および前記第２移動体が存在する前記区間と、前記第１移動体および前記第２移動体の各々について予約された前記区間とを変化させて状態の異なる複数の前記環境モデルの集合を構築する環境モデル構築部と、
    　前記第１移動体を、前記第２移動体とのデッドロック状態に陥らせること無く、目的とする所定の前記区間まで移動させる要求に対し、前記集合に含まれる前記環境モデルの状態を他の前記環境モデルの状態へ変化させながら、前記要求を満たす前記環境モデルの状態へ至るまでの順序を探索する探索部と、
    　を備え、
    　前記探索部は、所定の制約条件に基づいて、前記制約条件に合致する前記環境モデルの状態へ遷移させつつ前記探索を行う、
    　進路制御プログラム生成装置。
  3. 　前記制約条件が、前記第１移動体および前記第２移動体のうち少なくとも一つに対して、予約される前記区間の数を所定値以下とすることである、
    　請求項１または請求項２に記載の進路制御プログラム生成装置。
  4. 　前記制約条件が、前記第１移動体および前記第２移動体のうち少なくとも一つについて、１つの状態遷移において同時に予約できる前記区間の数を所定値以下とすることである、
    　請求項１から請求項３の何れか１項に記載の進路制御プログラム生成装置。
  5. 　前記制約条件が、前記第１移動体および前記第２移動体のうち少なくとも一つについて、進行方向の前記区間を予約可能とし、他の前記区間を予約不可能とすることである、
    　請求項１から請求項４の何れか１項に記載の進路制御プログラム生成装置。
  6. 　前記制約条件が、前記第１移動体および前記第２移動体のうち少なくとも一つについて、現在存在している前記区間から進行方向に数えて所定値だけ先までの前記区間を予約可能とし、他の前記区間を予約不可能とすることである、
    　請求項１から請求項５の何れか１項に記載の進路制御プログラム生成装置。
  7. 　前記第１移動体又は前記第２移動体が隣接する前記区間へ１回移動するときの前記環境モデルの状態の変化に対応する時間の経過を１論理時間としたときに、
    　前記制約条件が、前記第１移動体および前記第２移動体のうち少なくとも一つについて、前記１論理時間における予約と予約の解除の実行回数に対して上限を設けることである、
    　請求項１から請求項６の何れか１項に記載の進路制御プログラム生成装置。
  8. 　前記探索部が前記要求を満たす前記環境モデルの状態へ至るまでの順序が探索できなかった場合、前記実行回数に対する上限を増加させて、前記環境モデルの集合を構築し、前記要求を満たす前記環境モデルの状態へ至るまでの順序を探索する、
    　請求項７に記載の進路制御プログラム生成装置。
  9. 　前記第１移動体又は前記第２移動体が隣接する前記区間へ１回移動するときの前記環境モデルの状態の変化に対応する時間の経過を１論理時間としたときに、
    　前記制約条件が、前記第１移動体および前記第２移動体のうち少なくとも一つについて、前記１論理時間において、１つの前記区間に対して予約および予約の解除の両方が実行されることを禁止することである、
    　請求項１から請求項８の何れか１項に記載の進路制御プログラム生成装置。
  10. 　前記第１移動体又は前記第２移動体が隣接する前記区間へ１回移動するときの前記環境モデルの状態の変化に対応する時間の経過を１論理時間としたときに、
    　前記制約条件が、前記１論理時間において、１つの前記区間に対して予約および予約の解除の両方が実行されることを禁止することである、
    　請求項１から請求項８の何れか１項に記載の進路制御プログラム生成装置。
  11. 　前記環境モデルが前記第２移動体を複数含む、請求項１から請求項１０の何れか１項に記載の進路制御プログラム生成装置。
  12. 　複数の区間に分割された軌道と、該軌道上を移動する制御対象の第１移動体および制御対象外の第２移動体と、によって構成される環境モデルについて、前記環境モデルの状態が、前記第１移動体および前記第２移動体の各々が存在する前記区間と、前記第１移動体および前記第２移動体の各々について予約された前記区間とによって決定され、前記第１移動体および前記第２移動体についての前記区間の予約と、前記予約の解除と、予約した前記区間から他の予約した前記区間への移動によって、前記第１移動体および前記第２移動体が存在する前記区間と、前記第１移動体および前記第２移動体の各々について予約された前記区間とを変化させて状態の異なる複数の前記環境モデルの集合を構築するステップと、
    　前記第１移動体を、前記第２移動体とのデッドロック状態に陥らせること無く、目的とする所定の前記区間まで移動させる要求に対し、前記集合に含まれる前記環境モデルの状態を他の前記環境モデルの状態へ変化させながら、前記要求を満たす前記環境モデルの状態へ至るまでの順序を探索するステップと、
    　を有し、
    　前記構築するステップでは、所定の制約条件に基づいて、前記制約条件に合致する前記環境モデルの状態を用いて前記集合を構築する、進路制御プログラム生成方法。
  13. 　複数の区間に分割された軌道と、該軌道上を移動する制御対象の第１移動体および制御対象外の第２移動体と、によって構成される環境モデルについて、前記環境モデルの状態が、前記第１移動体および前記第２移動体の各々が存在する前記区間と、前記第１移動体および前記第２移動体の各々について予約された前記区間とによって決定され、前記第１移動体および前記第２移動体についての前記区間の予約と、前記予約の解除と、予約した前記区間から他の予約した前記区間への移動によって、前記第１移動体および前記第２移動体が存在する前記区間と、前記第１移動体および前記第２移動体の各々について予約された前記区間とを変化させて状態の異なる複数の前記環境モデルの集合を構築するステップと、
    　前記第１移動体を、前記第２移動体とのデッドロック状態に陥らせること無く、目的とする所定の前記区間まで移動させる要求に対し、前記集合に含まれる前記環境モデルの状態を他の前記環境モデルの状態へ変化させながら、前記要求を満たす前記環境モデルの状態へ至るまでの順序を探索するステップと、
    　を有し、
    　前記探索するステップでは、所定の制約条件に基づいて、前記制約条件に合致する前記環境モデルの状態へ遷移させつつ前記探索を行う、進路制御プログラム生成方法。
  14. 　コンピュータに、
    　複数の区間に分割された軌道と、該軌道上を移動する制御対象の第１移動体および制御対象外の第２移動体と、によって構成される環境モデルについて、前記環境モデルの状態が、前記第１移動体および前記第２移動体の各々が存在する前記区間と、前記第１移動体および前記第２移動体の各々について予約された前記区間とによって決定され、前記第１移動体および前記第２移動体についての前記区間の予約と、前記予約の解除と、予約した前記区間から他の予約した前記区間への移動によって、前記第１移動体および前記第２移動体が存在する前記区間と、前記第１移動体および前記第２移動体の各々について予約された前記区間とを変化させて状態の異なる複数の前記環境モデルの集合を構築するステップと、
    　前記第１移動体を、前記第２移動体とのデッドロック状態に陥らせること無く、目的とする所定の前記区間まで移動させる要求に対し、前記集合に含まれる前記環境モデルの状態を他の前記環境モデルの状態へ変化させながら、前記要求を満たす前記環境モデルの状態へ至るまでの順序を探索するステップと、
    　を実行させ、
    　前記構築するステップでは、所定の制約条件に基づいて、前記制約条件に合致する前記環境モデルの状態を用いて前記集合を構築する、プログラム。
  15. 　コンピュータに、
    　複数の区間に分割された軌道と、該軌道上を移動する制御対象の第１移動体および制御対象外の第２移動体と、によって構成される環境モデルについて、前記環境モデルの状態が、前記第１移動体および前記第２移動体の各々が存在する前記区間と、前記第１移動体および前記第２移動体の各々について予約された前記区間とによって決定され、前記第１移動体および前記第２移動体についての前記区間の予約と、前記予約の解除と、予約した前記区間から他の予約した前記区間への移動によって、前記第１移動体および前記第２移動体が存在する前記区間と、前記第１移動体および前記第２移動体の各々について予約された前記区間とを変化させて状態の異なる複数の前記環境モデルの集合を構築するステップと、
    　前記第１移動体を、前記第２移動体とのデッドロック状態に陥らせること無く、目的とする所定の前記区間まで移動させる要求に対し、前記集合に含まれる前記環境モデルの状態を他の前記環境モデルの状態へ変化させながら、前記要求を満たす前記環境モデルの状態へ至るまでの順序を探索するステップと、
    　を実行させ、
    　前記探索するステップでは、所定の制約条件に基づいて、前記制約条件に合致する前記環境モデルの状態へ遷移させつつ前記探索を行う、プログラム。
PCT/JP2020/010012 2019-06-18 2020-03-09 進路制御プログラム生成装置、進路制御プログラム生成方法及びプログラム Ceased WO2020255492A1 (ja)

Priority Applications (3)

Application Number Priority Date Filing Date Title
JP2021527355A JP7321416B2 (ja) 2019-06-18 2020-03-09 進路制御プログラム生成装置、進路制御プログラム生成方法及びプログラム
US17/619,849 US12221141B2 (en) 2019-06-18 2020-03-09 Route control program generation device, route control program generation method and program
EP20827325.0A EP3971053A4 (en) 2019-06-18 2020-03-09 ROUTE CONTROL PROGRAM GENERATION DEVICE, ROUTE CONTROL PROGRAM GENERATION METHOD AND PROGRAM

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
JP2019112838 2019-06-18
JP2019-112838 2019-06-18

Publications (1)

Publication Number Publication Date
WO2020255492A1 true WO2020255492A1 (ja) 2020-12-24

Family

ID=74040018

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/JP2020/010012 Ceased WO2020255492A1 (ja) 2019-06-18 2020-03-09 進路制御プログラム生成装置、進路制御プログラム生成方法及びプログラム

Country Status (4)

Country Link
US (1) US12221141B2 (ja)
EP (1) EP3971053A4 (ja)
JP (1) JP7321416B2 (ja)
WO (1) WO2020255492A1 (ja)

Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP2402229A1 (en) * 2010-06-22 2012-01-04 Universität Stuttgart Method and system for simulating, planning and/or controlling operating processes in a track guided transportation system
JP2014139052A (ja) * 2013-01-21 2014-07-31 Mitsubishi Heavy Ind Ltd 列車運行制御検査装置、列車運行制御検査方法及びプログラム
JP6076950B2 (ja) 2014-09-29 2017-02-08 株式会社日立製作所 進路制御プログラム生成方法および進路制御装置
JP2019112838A (ja) 2017-12-25 2019-07-11 Ｓａｎｅｉ株式会社 偏心管カバー及びこれを備えた湯水混合水栓

Family Cites Families (9)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPS5881078U (ja) 1981-11-25 1983-06-01 トヨタ自動車株式会社 ブロ−ホ−ル対策用クリ−ニングト−チ
JPS6076950U (ja) 1983-10-31 1985-05-29 株式会社シマノ 運動装置
JPS6080944U (ja) 1983-11-10 1985-06-05 キヤノン株式会社 記録ヘツドのモニタ装置
US5623413A (en) * 1994-09-01 1997-04-22 Harris Corporation Scheduling system and method
JP5624956B2 (ja) 2011-07-28 2014-11-12 株式会社日立製作所 進路制御プログラム生成方法および進路制御装置
JP5881078B2 (ja) 2011-12-13 2016-03-09 株式会社日立製作所 列車運行制御装置及び列車運行制御方法
JP6080944B2 (ja) 2013-03-29 2017-02-15 三菱重工業株式会社 車上装置、信号システム及び移動体の制御方法
JP6596750B2 (ja) 2015-11-25 2019-10-30 三菱重工エンジニアリング株式会社 車両制御システム、走行管理装置、リソース管理装置、車両制御方法、プログラム
JP6927090B2 (ja) * 2018-03-05 2021-08-25 トヨタ自動車株式会社 経路生成装置

Patent Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP2402229A1 (en) * 2010-06-22 2012-01-04 Universität Stuttgart Method and system for simulating, planning and/or controlling operating processes in a track guided transportation system
JP2014139052A (ja) * 2013-01-21 2014-07-31 Mitsubishi Heavy Ind Ltd 列車運行制御検査装置、列車運行制御検査方法及びプログラム
JP6076950B2 (ja) 2014-09-29 2017-02-08 株式会社日立製作所 進路制御プログラム生成方法および進路制御装置
JP2019112838A (ja) 2017-12-25 2019-07-11 Ｓａｎｅｉ株式会社 偏心管カバー及びこれを備えた湯水混合水栓

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
See also references of EP3971053A4

Also Published As

Publication number Publication date
EP3971053A1 (en) 2022-03-23
US20220289258A1 (en) 2022-09-15
JPWO2020255492A1 (ja) 2020-12-24
JP7321416B2 (ja) 2023-08-07
EP3971053A4 (en) 2022-07-20
US12221141B2 (en) 2025-02-11

Similar Documents

Publication Publication Date Title
Kim et al. Deadlock prevention for automated guided vehicles in automated container terminals
CN106794854A (zh) 列车运行图校正装置及列车运行图校正程序
Chalaki et al. An optimal coordination framework for connected and automated vehicles in two interconnected intersections
Lei et al. Hybrid heuristic search approach for deadlock-free scheduling of flexible manufacturing systems using Petri nets
Vial et al. Scheduling autonomous vehicle platoons through an unregulated intersection
Fantechi et al. Model checking geographically distributed interlocking systems using UMC
Bešinović et al. Stable and robust train routing in station areas with balanced infrastructure capacity occupation
Doniec et al. Anticipation based on constraint processing in a multi-agent context
JP7321416B2 (ja) 進路制御プログラム生成装置、進路制御プログラム生成方法及びプログラム
RU2742959C1 (ru) Система для управления работой участка железной дороги с построением единого расписания
AU2017262949B2 (en) Traffic management method and traffic management system
JP7190975B2 (ja) 列車制御装置、方法及びプログラム
Girault et al. On-line compositional controller synthesis for AGV
Chen et al. Invariant safe contingency model predictive control for intersection coordination of mixed traffic
Weits Simulation of railway traffic control
Li et al. Traffic signal priority/preemption control with colored petri nets
Stankaitis et al. A railway simulation suite for modelling advanced railway control systems
CN115494829B (zh) 一种自主列车运行控制系统建模及验证方法
Farkas et al. Optimizing Rail Traffic with Reinforcement Learning and Graph Attention Networks
Ghosh et al. Cooperative traffic control where autonomous cars meet human drivers
Vilela et al. A heuristic approach to train dispatch planning
Basile et al. Automated generation of a simulation model for the decentralized control of automated warehouse systems
Žarnay Use of Petri Net for Modelling of Traffic in Railway Stations
Pozanco et al. Train Route Planning as a Multi-agent Path Finding Problem
Zeng et al. SafeCrossLight: Pedestrian-Aware Traffic Light Control using Deep Reinforcement Learning

Legal Events

Date Code Title Description
121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 20827325

Country of ref document: EP

Kind code of ref document: A1

ENP Entry into the national phase

Ref document number: 2021527355

Country of ref document: JP

Kind code of ref document: A

NENP Non-entry into the national phase

Ref country code: DE

ENP Entry into the national phase

Ref document number: 2020827325

Country of ref document: EP

Effective date: 20211215