# US 12,007,239 B2 · Information processing apparatus, information processing method, computer program, and travel management system

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 12,007,239 B2
- Document ID: US12007239B2
- Status: Granted
- Kind: B2
- Application number: 17/193,362
- Filed: 2021-03-05
- Published: 2022-03-17
- Granted: 2024-06-11
- Earliest claimed: 2020-09-14
- Assignees: Kabushiki Kaisha Toshiba
- Applicants: Kabushiki Kaisha Toshiba
- Inventors: Michio Yamashita; Noriyuki Hirayama; Yoshikazu Yamane; Hideyuki Aisu; Shizu Sakakibara
- Web page: https://patentgrep.com/patent/US12007239B2

## CPC

- G01C 21/20: Instruments for performing navigational calculations (G01C21/24, G01C21/26 take precedence)
- G01C 21/343: {Calculating itineraries (travelling salesman problem G06Q10/04; optimisation of routes G06Q10/047)}
- G01C 21/3461: {Preferred or disfavoured areas, e.g. dangerous zones, toll or emission zones, intersections, manoeuvre types or segments such as motorways, toll roads or ferries}
- G01C 21/3605: {Destination input or retrieval}
- G01C 21/3667: {Display of a road map (G01C21/3614 takes precedence; guidance using 3D or perspective road maps G01C21/3635)}
- G08G 1/202: {Dispatching vehicles on the basis of a location, e.g. taxi dispatching}
- G01C: MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY (measuring liquid level G01F; radio navigation, determining distance or velocity by use of propagation effects, e.g. Doppler effects, propagation time, of radio waves, analogous arrangements using other waves G01S)
- G08G: TRAFFIC CONTROL SYSTEMS (guiding railway traffic, ensuring the safety of railway traffic B61L; arrangement of road signs or traffic signals E01F9/00; radar or analogous systems, sonar systems, lidar systems specially adapted for traffic control G01S13/91, G01S15/88, G01S17/88; {radar or analogous systems, sonar systems, lidar systems specially adapted for anti-collision purposes G01S13/93, G01S15/93, G01S17/93})

## Abstract

An information processing apparatus for a travel network including travel paths and reference regions coupling the paths includes a first scheduler configured to generate a first schedule including (1) a sequence of representative regions allowing a first mobile object to pass through the representative regions, and (2) timings of passage through the representative regions, based on move command information for the first mobile object to travel to a first reference region; and a second scheduler selecting a first representative region from among the representative regions included in the first schedule according to a travel situation of the first mobile object, and generate a second schedule including (1) a first route allowing the first mobile object to travel in a first area including the first representative region, and (2) timings for the first mobile object to pass through the reference regions included in the first route.

## Claims

### Claim 1

An information processing apparatus comprising:
processing circuitry configured to:
read, from a database, structure information on a travel network including a plurality of travel paths and a plurality of reference regions connecting the plurality of travel paths, the structure information of the travel network including graph data which includes nodes corresponding to the reference regions and links corresponding to the travel paths,
divide the travel network into a plurality of areas each containing two or more of the reference regions based on the structure information,
determine a representative region in each area, representative regions in adjacent areas being connected to each other via the travel path,
divide each of the areas into a plurality of subareas, a sub-representative region among the reference regions included in each of the subareas being connected to a sub-representative region of other subarea via the travel path, the representative region corresponding to the sub representative region of the sub-area containing the representative region;
generate a first virtual travel network including representative subnodes corresponding to the sub-representative regions and first links connecting between representative subnodes of sub-representative regions in each area and between representative subnodes of sub-representative regions in different areas;
acquire move command information that instructs the mobile object to travel from a first reference region to a second reference region, specify a first sub-area including the first reference region and a second sub-area including the second reference regions, and generate virtual move command information which instructs the mobile object to travel from a sub-representative region of the first sub-area to a sub-representative region of the second sub-area on the first virtual travel network;
generate a second schedule on the first virtual travel network, which includes sub-representative regions of passing through for moving from the sub-representative region of the first sub-area to the sub-representative region of the second sub-area and includes times of passing through the sub-representative regions, based on the virtual move command information;
generate a first schedule on the travel network, which includes reference regions of passing through for moving from the first reference region of the first sub-area to the sub-representative region of the first sub-area and includes times of passing through the reference regions, based on the second schedule and the move command information; and
control circuitry configured to control the mobile object to move from the first reference region to the sub-representative region of the first sub-area based on the first schedule and after detecting that the mobile object arrives at the sub-representative region of the first sub-area, control the mobile object to move from the sub-representative area region of the first sub-area to the sub-representative region of the second sub-area based on the second schedule,
wherein:
the processing circuitry identifies the second sub-area as a subarea that includes the reference area specified by the move command information according to an execution status of the second schedule, and based on the second schedule, generates a third schedule which includes reference regions of passing through for moving from the sub-representative region of the second sub-area to the second reference region in the second sub-area and includes times of passing through the reference regions,
the control circuitry controls the mobile object to move from the sub-representative region of the second sub-area to the second reference region based on the third schedule after detecting that the mobile object arrives at the sub-representative region of the second sub-area, and
the processing circuit updates the second schedule according to an execution status of the first schedule or updates the third schedule according to an execution status of the second schedule.

### Claim 2 (depends on 1)

The information processing apparatus according to claim 1, wherein:
the move command information instructs the mobile object to travel from the first reference region in a first area to the second reference region in a second area, and
the processing circuitry is further configured to:
generate a second virtual mobile network which includes representative nodes each representing a representative region of each area and fourth links connecting the representative nodes,
generate second virtual move command information to travel from a representative region of the first area to a representative region of the second area on the second virtual travel network, based on the movement command information;
generate a global operation schedule based on the second virtual move command information that includes representative regions of passing through for moving from the representative region in the first area to the representative region in the second area, and includes times of passing through the representative regions; and
generate a second local operation schedule that includes reference regions of passing through for moving from the first reference region of the first area to the representative region of the first area and includes times of passing through the reference regions based on the global operation schedule, and wherein
the processing circuitry further identifies the second area as an area that includes the reference area specified by the move command information according to an execution status of the global operation schedule, and based on the global operation schedule, generates a third local operation schedule which includes reference regions of passing through for moving from the representative region of the second area to the second reference region in the second area and includes times of passing through the reference regions, and
the control circuitry further controls the mobile object to move from the representative region of the second area to the second reference region based on the third local operation schedule after detecting that the mobile object arrives at the representative region of the second area.

### Claim 3 (depends on 2)

The information processing apparatus according to claim 2, wherein the control circuitry generates move command data based on the global operation schedule, the second local operation schedule, and the third local operation schedule, and transmits the movement command data to the first mobile object.

### Claim 4 (depends on 3)

The information processing apparatus according to claim 3, wherein the plurality of reference regions are three-dimensionally arranged.

### Claim 5 (depends on 3)

The information processing apparatus according to claim 3, wherein the mobile object is a vehicle.

### Claim 6 (depends on 3)

The information processing apparatus according to claim 3, wherein the mobile object is a flight body.

### Claim 7 (depends on 3)

A travel management system, comprising:
the information processing apparatus according to claim 3; and
the mobile object.

### Claim 8 (depends on 3)

The information processing apparatus according to claim 3, further comprising
an input circuit to receive instructions from a person in charge of operation management,
wherein the processing circuitry divides the travel network into the plurality of areas according to the instructions from the input circuit, and stores information of the divided areas in the database.

### Claim 9 (depends on 2)

The information processing apparatus according to claim 2, wherein the processing circuitry is configured to detect a position of the mobile object via communication circuitry or via a sensor arranged in the travel network; and generate the third local operation schedule at timing of moving from one previous representative region to the representative region in the second area.

### Claim 10 (depends on 9)

The information processing apparatus according to claim 9, wherein the control circuitry generates move command data based on the global operation schedule, the second local operation schedule, and the third local operation schedule, and transmits the movement command data to the first mobile object.

### Claim 11 (depends on 2)

The information processing apparatus according to claim 2, wherein:
the processing circuitry generates the third local operation schedule at timing when the processing circuitry detects that the mobile object moves from one previous representative region to the representative region of the second area.

### Claim 12 (depends on 11)

The information processing apparatus according to claim 11, wherein
the processing circuitry is further configured to:
set lower nodes via one or more fifth links to each representative node in the second virtual mobile network, the lower nodes being able to be assigned each only one mobile object,
assign the mobile object in the first area to any one of the lower nodes of the representative node of the first area, the assigned lower node corresponding to a location of the mobile object in the travel network, and generate the second local operation schedule to move from the assigned lower node to the representative region of the first area, and de-allocate the mobile object when the mobile object moves out of the first area due to an execution of the second local operation schedule, and
wait to assign the mobile object to the lower node when other mobile objects are already assigned to all of the lower nodes until the lower node becomes available, and assign the mobile object to the lower node when the lower node becomes available.

### Claim 13 (depends on 11)

The information processing apparatus according to claim 11, wherein the processing circuitry is capable of changing a number of the lower nodes connected to at least one of the representative nodes in accordance a received instruction.

### Claim 14 (depends on 2)

The information processing apparatus according to claim 2, wherein when the processing circuitry detects that a command to move to a third reference region other than the representative region within a third area between the first area and the second area has been added to the movement command information after the mobile object has departed from the first reference region, the processing circuitry generates a fourth local operation schedule that includes reference regions of passing through for round trip between the representative region of the third area and the third reference region and times of passing through the reference regions, based on the global operation schedule before the mobile object arrives at the representative region of the third area.

### Claim 15 (depends on 2)

The information processing apparatus according to claim 2, wherein when the move command information for a second mobile object to a K-th mobile object (“K” is an integer of two or more) which is different from a first mobile object being the mobile object is an instruction of travel from any reference region in the area identical to that of the first reference region to any reference region in the area identical to that of the second reference region, the processing circuitry is configured to generate the global operation schedule allowing a sequence of the first mobile object to the K-th mobile object to consecutively pass through each of the representative regions included in the global operation schedule for the first mobile object to the K-th mobile object.

### Claim 16

An information processing method comprising:
reading, from a database, structure information on a travel network including a plurality of travel paths and a plurality of reference regions connecting the plurality of paths, the structure information of the travel network including graph data which includes nodes corresponding to the reference regions and links corresponding to the travel paths;
dividing the travel network into a plurality of areas each containing two or more of the reference regions based on the structure information;
determining a representative region in each area, representative regions in adjacent areas being connected to each other via the travel path;
dividing each of the areas into a plurality of subareas, a sub-representative region among the reference regions included in each of the subareas being connected to a sub-representative region of other subarea via the travel path, the representative region corresponding to the sub representative region of the sub-area containing the representative region;
generating a first virtual travel network including representative subnodes corresponding to the sub-representative regions and first links connecting between representative subnodes of sub-representative regions in each area and between representative subnodes of sub-representative regions in different areas;
acquiring move command information that instructs the mobile object to travel from a first reference region to a second reference region, specify a first sub-area including the first reference region and a second sub-area including the second reference regions, and generate virtual move command information which instructs to travel from a sub-representative region of the first sub-area to a sub-representative region of the second sub-area on the first virtual travel network;
generating a second schedule on the first virtual travel network, which includes sub-representative regions of passing through for moving from the sub-representative of the first sub-area to the sub-representative region of the second sub-area and includes times of passing through the sub-representative regions, based on the virtual move command information;
generating a first schedule on the travel network, which includes reference regions of passing through for moving from the first reference region of the first subarea to the sub-representative region of the first sub-area and includes times of passing through the reference regions, based on the second schedule and the move command information;
controlling the mobile object to move from the first reference region to the subrepresentative region of the first sub-area based on the first schedule and after detecting that the mobile object arrives at the sub-representative region of the first subarea, control the mobile object to move from the sub-representative region of the first subarea to the sub-representative region of the second sub-area based on the second schedule;
identifying the second sub-area as a sub-area that includes the reference area specified by the move command information according to an execution status of the second schedule, and based on the second schedule, generates a third schedule which includes reference regions of passing through for moving from the sub-representative region of the second sub-area to the second reference region in the second sub-area and includes times of passing through the reference regions;
controlling the mobile object to move from the sub-representative region of the second sub-area to the second reference region based on the third schedule after detecting that the mobile object arrives at the sub-representative region of the second sub-area; and
updating the second schedule according to an execution status of the first schedule or updates the third schedule according to an execution status of the second schedule.

### Claim 17

A non-transitory computer readable medium having a computer program stored in the medium and causing, when executed by a computer, the computer to perform processes comprising:
reading, from a database, structure information on a travel network including a plurality of travel paths and a plurality of reference regions connecting the plurality of paths, the structure information of the travel network including graph data which includes nodes corresponding to the reference regions and links corresponding to the travel paths;
dividing the travel network into a plurality of areas each containing two or more of the reference regions based on the structure information;
determining a representative region in each area, representative regions in adjacent areas being connected to each other via the travel path;
dividing each of the areas into a plurality of subareas, a sub-representative region among the reference regions included in each of the subareas being connected to a sub-representative region of other subarea via the travel path, the representative region corresponding to the sub representative region of the sub-area containing the representative region;
generating a first virtual travel network including representative subnodes corresponding to the sub-representative regions and first links connecting between representative subnodes of sub-representative regions in each area and between representative subnodes of sub-representative regions in different areas;
acquiring move command information that instructs the mobile object to travel from a first reference region to a second reference region, specify a first sub-area including the first reference region and a second sub-area including the second reference regions, and generate virtual move command information which instructs to travel from a sub-representative region of the first sub-area to a sub-representative region of the second sub-area on the first virtual travel network;
generating a second schedule on the first virtual travel network, which includes sub-representative regions of passing through for moving from the sub-representative of the first sub-area to the sub-representative region of the second sub-area and includes times of passing through the sub-representative regions, based on the virtual move command information;
generating a first schedule on the travel network, which includes reference regions of passing through for moving from the first reference region of the first subarea to the sub-representative region of the first sub-area and includes times of passing through the reference regions, based on the second schedule and the move command information;
controlling the mobile object to move from the first reference region to the subrepresentative region of the first sub-area based on the first schedule and after detecting that the mobile object arrives at the sub-representative region of the first subarea, control the mobile object to move from the sub-representative region of the first subarea to the sub-representative region of the second sub-area based on the second schedule;
identifying the second sub-area as a sub-area that includes the reference area specified by the move command information according to an execution status of the second schedule, and based on the second schedule, generates a third schedule which includes reference regions of passing through for moving from the sub-representative region of the second sub-area to the second reference region in the second sub-area and includes times of passing through the reference regions;
controlling the mobile object to move from the sub-representative region of the second sub-area to the second reference region based on the third schedule after detecting that the mobile object arrives at the sub-representative region of the second sub-area; and
updating the second schedule according to an execution status of the first schedule or updates the third schedule according to an execution status of the second schedule.