JP7577010B2 - Planned travel route creation device for a mobile object, and planned travel route creation program for a mobile object - Google Patents

Description

The present invention relates to a device that creates a planned movement route for a moving object that avoids obstacles so that the moving object can move through a target movement area that includes obstacles while avoiding the obstacles.

The applicant has invented a mobile object movement control system that includes a movement schedule information creation process that creates movement schedule information (planned movement route) for a mobile object that moves on a movement target surface (movement target area), and a movement control process that moves the mobile object based on the movement schedule information and controls the movement of the mobile object by comparing the actual movement information of the mobile object acquired by a movement information acquisition means with the movement schedule information (see Patent Document 1).

JP 2020-154400 A

In the above-mentioned method for controlling the movement of a moving body, the moving body is caused to move along a zigzag route as the planned movement route, so there was a problem that depending on the shape of the target movement area, the moving body may be caused to move along an inefficient route.
In view of the above-mentioned problems, the present invention provides a planned movement route creation device for a moving object, which is capable of accurately creating an efficient planned movement route in accordance with the shape of a target movement area.

The planned movement route creation device for a moving body according to the present invention is a planned movement route creation device for a moving body that creates a planned movement route for moving the moving body while avoiding pillars within a movement target area, and includes a movement target area creation means that creates a movement target area surrounded by a movement target area boundary line that divides the movement target area based on XY coordinate information of the movement target area that indicates the position of the movement target area, a pillar area creation means that creates a pillar area surrounded by a pillar area boundary line that divides a pillar that exists within the movement target area based on XY coordinate information that indicates the position of a corner of a pillar within the movement target area, and a pillar area creation means that creates a pillar area surrounded by a pillar area boundary line that divides a pillar that exists within the movement target area based on XY coordinate information that indicates the position of the movement target area and the ... corner of a pillar within the movement target area. The mobile area dividing means divides a movable area avoiding pillars into a plurality of divided areas, and a divided area planned movement route creating means creates a planned movement route of the moving body within each of the plurality of divided areas, the movable area dividing means creating a first boundary line connecting pillars , a second boundary line connecting the pillar and the movement target area boundary line, and a third boundary line connecting the pillar and the first boundary line or the second boundary line, and dividing the movement target area with these boundaries, thereby creating a divided area surrounded by the divided area boundary line formed by these boundaries, the pillar area boundary line, and the movement target area boundary line, and a divided area creating means assigning identification information to each of the plurality of divided areas and each pillar area. and divided area recognizing means for recognizing each of the plurality of divided areas by dividing the area to be moved into a plurality of horizontal lines parallel to the X-axis at equal intervals along the Y-axis, and the intra-divided area planned movement route creating means includes horizontal line creating means for creating a plurality of horizontal lines parallel to the X-axis that divide the area to be moved into into a plurality of vertical lines parallel to the Y-axis that divide the area to be moved into into into a plurality of vertical lines parallel to the X-axis that divide the area to be moved into ... The system is characterized by comprising: a second route creation means for creating a zigzag second route for each divided area that proceeds along an X-axis formed by connecting the intersections with vertical straight lines; a first movement efficiency calculation means for calculating the movement efficiency when moving along the first route for each divided area; a second movement efficiency calculation means for calculating the movement efficiency when moving along the second route for each divided area; and a route selection means for comparing the movement efficiency when moving along the first route and the movement efficiency when moving along the second route within the same divided area, and selecting the route with the better movement efficiency from the first route and the second route as the planned movement route within the divided area.
The divided area creating means is characterized by comprising: a pillar grouping means for grouping a plurality of pillars existing within the movement target area into groups of pillars having similar X-coordinate information of their center of gravity and pillars having similar Y-coordinate information of their center of gravity; a pillar corner recognizing means for recognizing the corners of the pillars by assigning identification information to a plurality of corners of each pillar ; a first connecting line creating means for creating a first connecting line as a first boundary line connecting a corner of one pillar grouped as having similar X-coordinate information of its center of gravity and a corner of the other pillar , and a first connecting line as a first boundary line connecting a corner of one pillar grouped as having similar Y-coordinate information of its center of gravity and a corner of the other pillar , the first connecting line being a first boundary line connecting a corner of one pillar not connected to the first connecting line and a corner of the other pillar, the second connecting line creating means for creating a second connecting line as a second boundary line connecting a corner of the pillar not connected to the first connecting line and the movement target area boundary line; and a third connecting line creating means for creating a third connecting line as a third boundary line connecting a corner of the pillar not connected to the first and second connecting lines and the already created first connecting line or second connecting line.
The present invention is also characterized by comprising an inter-division area planned movement route creating means for creating a planned movement route of the mobile object between the division areas.
The inter-divided area planned movement route creation means is characterized by comprising: an inter-divided area straight line planned movement route creation means for creating a planned movement route between divided areas by connecting an end point of a planned movement route within one divided area and a start point of a planned movement route within the divided area of the other divided area with a straight line; and an inter-divided area detour planned movement route creation means for creating an inter-divided area detour planned movement route, which is a planned movement route between divided areas that does not come into contact with the movement target area boundary line or the pillar area boundary line, when the planned straight line movement route between divided areas created by the inter-divided area straight line movement planned route creation means comes into contact with the movement target area boundary line or the pillar area boundary line.
A planned movement route creation processing program for a moving body according to the present invention, which creates a planned movement route for moving a moving body while avoiding obstacles within a movement target area, comprises: a movement target area creation means for creating a movement target area surrounded by movement target area boundary lines that divide the movement target area based on XY coordinate information of the movement target area that indicates the position of the movement target area; a pillar area creation means for creating a pillar area surrounded by pillar area boundary lines that divide pillars present within the movement target area based on XY coordinate information that indicates the position of a pillar within the movement target area; a first boundary line connecting pillars , a second boundary line connecting the pillar and the movement target area boundary line, and a third boundary line connecting the pillar and the first boundary line or the second boundary line, and creating a boundary line connecting the pillar and the movement target area boundary line to divide the movement target area by these boundary lines, a divided area creation means for creating a divided area surrounded by a divided area boundary formed by a line, a pillar area boundary, and a movement target area boundary; a divided area recognition means for recognizing each of the plurality of divided areas by assigning identification information to each of the plurality of divided areas and each pillar area; a horizontal line creation means for creating a plurality of horizontal lines parallel to the X axis which divide the movement target area at equal intervals along the Y axis; a vertical line creation means for creating a plurality of vertical lines parallel to the Y axis which divide the movement target area at equal intervals along the X axis; a first intersection recognition means for recognizing an intersection between the divided area boundary line and the horizontal lines; a second intersection recognition means for recognizing an intersection between the divided area boundary line and the vertical lines; a first route creation means for creating a zigzag first route for each divided area proceeding along the Y axis formed by connecting the intersections on each divided area boundary line with horizontal lines;
The program is a planned movement route creation processing program for a moving body to function as a second route creation means for creating a zigzag second route for each divided area that proceeds along an X-axis formed by connecting the intersections on the boundary lines of each divided area with vertical straight lines, and a route selection means for comparing the movement efficiency when moving along the first route within the same divided area with the movement efficiency when moving along the second route, and selecting the route with the better movement efficiency from the first route and the second route as the planned movement route within the divided area.
According to the present invention, it is possible to provide a planned movement route creation device for a moving body, and a planned movement route creation processing program, which are capable of accurately creating an efficient planned movement route for moving a moving body while avoiding obstacles within a target movement area, in accordance with the shape of the target movement area.

FIG. 4 is an explanatory diagram of the process of creating a movement target area and an obstacle area (phase 1). FIG. 11 is an explanatory diagram of the obstacle grouping process (phase 2). FIG. 11 is an explanatory diagram of the obstacle angle recognition process (phase 3). FIG. 11 is an explanatory diagram of the obstacle boundary line creation process (phase 4). FIG. 13 is an explanatory diagram of the divided area division process (phase 5). FIG. 13 is an explanatory diagram of the divided area division process (phase 5). FIG. 13 is an explanatory diagram of the divided area recognition process (phase 6). FIG. 13 is an explanatory diagram of the divided area recognition process (phase 6). FIG. 13 is an explanatory diagram of the equally spaced straight line path creation process (phase 7). FIG. 13 is an explanatory diagram of the intersection coordinate extraction process (phase 8). 13 is an explanatory diagram of the process of extracting intersection coordinates for each area (phase 9) and the process of creating a zigzag movement planned route within a divided area (phase 10). FIG. 10 is an explanatory diagram of a process for creating a zigzag movement planned route within a divided area (phase 10) and a process for creating a movement planned route between divided areas (phase 11). FIG. 11 is a flowchart showing the procedure of a process (phase 1) for creating a movement target area and an obstacle area. 11 is a flowchart showing a procedure of the obstacle grouping process (phase 2). 11 is a flowchart showing a procedure of an obstacle angle recognition process (phase 3). 11 is a flowchart showing a procedure of an obstacle boundary line creation process (phase 4). 11 is a flowchart showing the procedure of a divided area division process (phase 5). 13 is a flowchart showing the procedure of a divided area recognition process (phase 6). 13 is a flowchart showing the procedure of an equally spaced straight line path creation process (phase 7) and an intersection coordinate extraction process (phase 8). 13 is a flowchart showing the procedure of an area-by-area intersection coordinate extraction process (phase 9); 10 is a flowchart showing the procedure of a process (phase 10) for creating a zigzag movement planned route within a divided area. 11 is a flowchart showing the procedure of a movement cost calculation process (phase 11). 11 is a flowchart showing the procedure of another route creation processing (phases 12 to 16). 13 is a flowchart showing the procedure of a route selection process (phase 17). 13 is a flowchart showing the procedure of a process (phase 18) for creating a planned movement route between divided areas. FIG. 13 is an explanatory diagram of the divided area recognition process (phase 6). FIG. 13 is an explanatory diagram of the divided area recognition process (phase 6). FIG. 13 is an explanatory diagram of the divided area recognition process (phase 6). 13 is an explanatory diagram of the process of extracting intersection coordinates for each area (phase 9) and the process of creating a zigzag movement planned route within a divided area (phase 10). FIG. FIG. 10 is an explanatory diagram of the process of creating a zigzag movement planned route within a divided area (phase 10). FIG. 1 is a perspective view showing an example of a moving body.

The planned movement route creation device for a moving body of the embodiment is a device that creates a planned movement route for a moving body to move while avoiding obstacles within a target movement area, i.e., an obstacle avoidance planned movement route for a moving body moving within the target movement area.
The planned movement route creation device for a moving object includes a movement target area creation means, an obstacle area creation means, a movable area dividing means, an intra-divided area planned movement route creation means, and an inter-divided area planned movement route creation means.
That is, the movement target area creation means is a means for creating a movement target area surrounded by a movement target area boundary line that divides the movement target area based on the XY coordinate information of the movement target area (i.e., the planar coordinate information of the movement target area) indicating the position of the movement target area.
The obstacle area creation means is means for creating an obstacle area surrounded by obstacle area boundaries that partition obstacles present within the movement target area based on XY coordinate information indicating the position of the obstacle within the movement target area.
The movable area dividing means divides the movable area into a plurality of divided areas by using XY coordinate information indicating the position of the target area of movement and XY coordinate information indicating the positions of obstacles within the target area of movement, while avoiding obstacles.
The intra-divided area planned movement route creation means is means for creating a planned movement route of the mobile object within each of the plurality of divided areas.
The inter-divided area planned movement route creation means is a means for creating a planned movement route of a moving object between the divided areas.

The movable area dividing means includes a divided area creating means and a divided area recognizing means.
The divided area creation means creates a first boundary line connecting obstacles to each other, a second boundary line connecting the obstacles to the movement target area boundary line, and a third boundary line connecting the obstacles to the first boundary line or the second boundary line, and divides the movement target area with these boundary lines, thereby creating a divided area surrounded by divided area boundary lines formed by these boundaries, the obstacle area boundary line, and the movement target area boundary line.
The divided area recognition means is a means for recognizing each of the plurality of divided areas by providing identification information to each of the plurality of divided areas and each of the obstacle areas.
In addition, the planned movement route creation means within the divided area includes a horizontal line creation means, a vertical line creation means, a first intersection recognition means, a second intersection recognition means, a first route creation means, a second route creation means, a first movement efficiency calculation means, a first movement efficiency calculation means, and a route selection means.
The horizontal line creating means creates a plurality of horizontal lines parallel to the X axis that divide the movement target area at equal intervals along the Y axis.
The vertical line creating means creates a plurality of vertical lines parallel to the Y axis that divide the movement target area at equal intervals along the X axis.
The first intersection recognition means is a means for recognizing an intersection between a divided area boundary line and a horizontal straight line.
The second intersection recognition means is a means for recognizing an intersection between a divided area boundary line and a vertical straight line.
The first route creation means creates a zigzag first route for each divided area that proceeds along the Y axis formed by connecting the intersections on the boundaries of the divided areas with horizontal straight lines.
The second route creation means creates a zigzag second route for each divided area that proceeds along the X-axis formed by connecting the intersections on the boundaries of the divided areas with vertical straight lines.
The first movement efficiency calculation means is means for calculating the movement efficiency when moving along the first route for each divided area.
The second movement efficiency calculation means is means for calculating the movement efficiency when moving along the second route for each divided area.
The route selection means is a means for comparing the travel efficiency when moving along a first route and the travel efficiency when moving along a second route within the same divided area, and selecting the route having the better travel efficiency from the first route and the second route as the planned travel route within the divided area.
More specifically, the divided area creating means includes obstacle grouping means for grouping a plurality of obstacles present within the movement target area into groups of obstacles having similar X-coordinate information and obstacles having similar Y-coordinate information; obstacle angle recognizing means for recognizing the corners of the obstacles by assigning identification information to a plurality of corners of each obstacle; first connection line creating means for creating a first connection line connecting a corner of one obstacle grouped as having similar X-coordinate information to a corner of the other obstacle grouped as having similar Y-coordinate information, and a first connection line connecting a corner of one obstacle grouped as having similar Y-coordinate information to a corner of the other obstacle grouped as having similar Y-coordinate information; second connection line creating means for creating a second connection line connecting a corner of the obstacle not connected to the first connection line to the movement target area boundary line; and third connection line creating means for creating a third connection line connecting a corner of the obstacle not connected to the first and second connection lines to the already created first connection line or second connection line.
In addition, more specifically, the inter-divided area planned movement route creation means is configured to include an inter-divided area straight line planned movement route creation means for creating a planned movement route between divided areas by connecting an end point of a planned movement route within one divided area and a start point of a planned movement route within the divided area of the other divided area with a straight line, and an inter-divided area detour planned movement route creation means for creating an inter-divided area detour planned movement route, which is a planned movement route between divided areas that does not come into contact with the movement target area boundary line or the obstacle area boundary line, when the straight line planned movement route between divided areas created by the inter-divided area straight line planned movement route creation means comes into contact with the movement target area boundary line or the obstacle area boundary line.

The movement target area creation means, obstacle area creation means, obstacle grouping means, obstacle angle recognition means, first connecting line creation means, second connecting line creation means, third connecting line creation means, divided area recognition means, horizontal line creation means, vertical line creation means, first intersection recognition means, second intersection recognition means, first route creation means, second route creation means, first movement efficiency calculation means, second movement efficiency calculation means, route selection means, and inter-divided area planned movement route creation means, which constitute the planned movement route creation device of the embodiment, are realized by a control means, and the control means which executes each of the means is composed of a processing program that indicates the procedure of processing executed by each means, and hardware resources such as a computer that realizes information processing by the processing program.
In other words, the planned movement route creation processing program of the embodiment is a program that causes a computer to function as the above-mentioned movement target area creation means, obstacle area creation means, obstacle grouping means, obstacle angle recognition means, first connecting line creation means, second connecting line creation means, third connecting line creation means, divided area recognition means, horizontal line creation means, vertical line creation means, first intersection recognition means, second intersection recognition means, first route creation means, second route creation means, first movement efficiency calculation means, second movement efficiency calculation means, route selection means, and inter-divided area planned movement route creation means.

The above-mentioned movement target area creating means and obstacle area creating means execute the movement target area and obstacle area creating process (phase 1) shown in FIG. 1 and FIG.
The obstacle grouping means executes the obstacle grouping process (phase 2) shown in FIG. 2 and FIG.
The obstacle angle recognition means executes the obstacle angle recognition process (phase 3) shown in FIG. 3 and FIG.
The first connection line generating means executes the obstacle boundary line generating process (phase 4) shown in FIG. 4 and FIG.
The second connection line creating means and the third connection line creating means execute the division area division process (phase 5) shown in FIGS.
The divided area recognition means executes the divided area recognition process (phase 6) shown in FIGS.
Further, the horizontal straight line creating means executes the equally spaced straight line path creating process (phase 7) shown in FIG. 9 and FIG.
The first intersection recognition means executes the intersection coordinate extraction process (phase 8) shown in Figs. 10 and 19, and the area-specific intersection coordinate extraction process (phase 9) shown in Figs.
The first route creation means executes the process of creating a zigzag movement planned route within a divided area (phase 10) shown in Figs.
The first movement efficiency calculation means executes the movement cost calculation process (phase 11) shown in FIG. 22 when moving along the first route for each divided area.
The vertical straight line creating means executes phase 12 shown in step S230 of FIG. 23, which is a process replacing the equally spaced straight line path creating process (phase 7).
The second intersection recognition means executes phase 13 shown in step S240 of FIG. 23, which is a process replacing the intersection coordinate extraction process (phase 8), and phase 14 shown in step S250 of FIG. 23, which is the same process as the intersection coordinate extraction process for each area (phase 9).
The second route generating means executes phase 15 shown in step S260 in FIG. 23, which is a process replacing the process for generating a zigzag movement planned route within a divided area (phase 10).
The second movement efficiency calculation means executes phase 16 shown in step S270 of Fig. 23. That is, in the case of moving along the second route for each divided area, the same movement cost calculation process as the movement cost calculation process (phase 11) shown in Fig. 22 is executed.
The route selection means executes the route selection process (phase 17) shown in FIG.
The inter-divided area planned travel route creating means executes the inter-divided area planned travel route creating process shown in FIG. 12 and FIG.
In addition, the inter-divided area straight-line movement planned route creation means of the inter-divided area movement planned route creation means executes the inter-divided area straight-line movement planned route creation process (the part other than the route search algorithm part of Figure 25), and the inter-divided area detour movement planned route creation means of the inter-divided area movement planned route creation means executes the processing of the route search algorithm part of Figure 25 as the inter-divided area detour movement planned route creation process.

The moving body is a moving body 1 configured to be able to move on a target surface within a target area for movement, such as a floor surface F, based on a planned movement route created by a moving body planned movement route creation device according to the embodiment (see Figure 31).
The control means is mounted on the moving body 1, for example, as shown in FIG.
Therefore, in this case, the moving body 1 is equipped with a control means 50 that creates a planned movement route for the moving body 1 and controls the movement of the moving body 1 based on the created planned movement route (planned movement information (XY coordinate information)).
The control means for creating the planned movement route of the moving body 1 may be configured not by a computer mounted on the moving body 1, but by a computer such as a personal computer separate from the moving body 1, and the above-mentioned processing program processed by the computer. In this case, as described below, the XY coordinate information of the movement target area in which the moving body 1 is to be moved and the XY coordinate information of obstacles within the movement target area are input to the computer, so that the movement target area and obstacles are recognized and a planned movement route is created. Then, by inputting the created planned movement route to the control means of the moving body 1, the control means of the moving body 1 becomes able to move the moving body 1 within a movable area within the movement target area based on the planned movement route.

In the process of creating a planned movement route, first, XY coordinate information of a corner of a wall at a boundary position between a floor surface area and a wall as a target movement area A indoors, and XY coordinate information of a corner of a pillar (hereinafter referred to as pillar B) as an obstacle B existing in the floor surface area as the target movement area A are inputted in advance to a computer. Then, the computer converts the inputted XY coordinate information into XY coordinate information on a display screen D managed by the computer, and records the converted information in a storage means.
That is, the XY coordinate information of the corner of the wall at the boundary position between the floor area and the wall is inputted into the computer in advance as the XY coordinate information of the area to be moved indicating the position of area A, and the XY coordinate information of the corner of pillar B is inputted as the XY coordinate information of the area to be moved indicating the position of pillar (obstacle) B.
Furthermore, the computer recognizes the target movement area A and the pillar (obstacle) B and displays them, for example, on a display screen D (see Figure 1), and finally recognizes the created planned movement route and displays it, for example, on a display screen D (see Figure 12).

In the present invention, the XY coordinate information refers to actual XY coordinate information in the movement target area A, and XY coordinate information managed on the display screen D by the computer controlling the display screen D based on the actual XY coordinate information.
The minimum spacing in the X-axis direction and the minimum spacing in the Y-axis direction that the computer manages on the display screen D can be set to a constant spacing on the actual target movement area A based on an XY coordinate spacing setting program installed in the computer.
For example, the minimum interval in the X-axis direction and the minimum interval in the Y-axis direction managed by the computer on the display screen D are set to correspond to an actual 10 cm. In this case, for example, a position a 10 cm away in the positive direction of the X-axis direction from a reference point O set outside the actual movement target area A, and a position b 10 cm away in the positive direction of the Y-axis direction from the position a are recorded and managed by the computer as XY coordinate values a=(1,0), b=(1,1) based on the reference point O on the display screen D.
In addition, the XY coordinate information of the corners of the walls partitioning the actual target area A of movement and the XY coordinate information of each corner of each of the actual pillars B, B... are recorded in the memory means, for example, by inputting the measured values measured using a measuring means such as a range finder, such as the distance from a reference point O set outside the actual target area A of movement to the position of each corner of the wall, and the distance from the reference point O to the position of each corner of each of the pillars B, B..., or by inputting them from a design drawing, etc.
For example, as shown in FIG. 1, a case will be described in which the position diagonally downward to the left from the bottom left corner of the movement target area A is determined as the reference point O.
In this case, the measured distance from the reference point O to each corner is input into a computer, and the computer records in a file, based on an XY coordinate interval setting program, a distance of, for example, 10 cm, as an XY coordinate value converted into one scale on the XY coordinate axis of the display screen D.
For example, if a certain corner is located 100 cm away from the reference point O in the positive direction along the X-axis and 100 cm away from the reference point O in the positive direction along the Y-axis, the XY coordinate values of the corner are recorded as (10, 10). Note that if a certain corner is located 94 cm away from the reference point O in the positive direction along the X-axis and 96 cm away from the origin in the positive direction along the Y-axis, the XY coordinate values of the corner are recorded as (9, 10), for example, by rounding off.

First, in the process of creating a movement target area and an obstacle area (phase 1), the computer displays the movement target area A and a number of pillars B, B... within the movement target area A on a display screen D, for example as shown in Figure 1, in accordance with the procedures of the movement target area creation processing program and the obstacle area creation processing program.
1, the computer displays the movement target area A on a display screen D by creating a boundary line between the inside and outside of the movement target area A, i.e., a movement target area boundary line C, and also displays a number of pillars B, B... that exist within the movement target area A. In this case, the movement target area boundary line C is created, for example, by connecting XY coordinate information of a wall corner at the boundary position between the floor area as the movement target area A and the wall, and the boundary line of pillar B (obstacle area boundary line) is created, for example, by connecting XY coordinate information of the corner of pillar B.
Specifically, the computer performs a process (phase 1) of creating a movement target area and an obstacle area as shown in the flowchart of FIG. 13, in accordance with the procedures of a movement target area creating process program and an obstacle area creating process program.
First, data (XY coordinate values of the corners of the walls (boundaries)) is extracted from a file that records XY coordinate information indicating the position of the movement target area A, for example, the XY plane coordinates of the corners of the walls (boundaries) that separate the movement target area A, to create the movement target area boundary line C on the display screen D (step S1). That is, all corners of the walls (boundaries) that separate the movement target area A are displayed on the display screen D, and the movement target area boundary line C is displayed on the display screen D by connecting each corner with a straight line.
Next, the pillar number control variable is initialized, that is, the pillar number control variable n is set to 1 (step S2). The pillar number control variable is a variable for specifying the pillar to be checked, and is successively recorded in the storage means and managed.
Then, it is determined whether or not there exists a file recording XY coordinate information indicating the position of an obstacle, for example, a pillar B, and the XY coordinates of the corner of the n-th pillar B (step S3).
That is, in the process of creating the movement target area and obstacle area, the computer performs the process using storage means such as a wall angle coordinate recording file which records the XY coordinates of the corners of the movement target area A, for example the corners of the wall at the boundary position between the floor area which becomes the movement target area A and the wall, a pillar angle coordinate recording file which records the XY coordinates of the corners of each pillar B, B... existing within the floor area, and a pillar number management variable register.
Next, in step S3, if it is determined that a file recording the XY coordinates of the corner of the nth pillar exists, data is extracted from the file recording the XY coordinates of the corner of the nth pillar and the nth pillar is displayed on the display screen D (step S4), after which the pillar number management variable n is updated to n+1 (step S5), and the process returns to step S3.
If it is determined in step S3 that a file recording the XY coordinates of the corner of the nth pillar does not exist, it is recognized that all pillars B within the movement target area A are displayed on the display screen D, the movement target area and obstacle area creation process (phase 1) is terminated, and the process proceeds to obstacle grouping process (phase 2).
By the above-described process of creating the movement target area and obstacle area (phase 1), for example, as shown in FIG. 1, a movement target area boundary line C which is the boundary of the movement target area A, and n pillars (pillar interior areas (obstacle areas)) B, B... existing within the movement target area A are displayed on the display screen D (for example, as shown in FIG. 1, pillars B(n) = B(1), B(2), B(3), B(4) are displayed).
In other words, a movement target area A and pillars (intra-pillar areas (obstacle areas)) B, B . . . recognized by the computer are created.

In the obstacle grouping process (phase 2), the computer, following the procedure of the obstacle grouping process program, groups pillars B with similar X coordinate values and pillars B with similar Y coordinate values, using the center coordinate of pillar B as a reference, as shown in Figure 2. The grouping is performed by assigning numbers. Therefore, each pillar B, B... is assigned a number in the X-axis direction and a number in the Y-axis direction. That is, the number of the leftmost pillar B (1) in Figure 2 is 1-1, and the number of the rightmost pillar B (5) in Figure 2 is 4-3. For example, the number 4-3 of the rightmost pillar B (5) in Figure 2 means that the pillar B (5) belongs to the fourth group in the X-axis direction and the third group in the Y-axis direction.

That is, the computer performs the obstacle grouping process (phase 2) as shown in the flowchart of FIG. 14 in accordance with the procedure of the obstacle grouping process program.
In the obstacle grouping process (phase 2), first, variable initialization process is performed. That is, the pillar number management variable n is set to 0, the comparison target management variable p is set to 0, and the group number variable gx is set to 1 (step S11).
That is, in the obstacle grouping process, the computer performs the process using storage means such as the pillar number control variable register, the comparison object control variable register, the group number variable register, and the pillar group number recording file.
Next, it is determined whether the value of the pillar number control variable n matches the number of pillars (step S12).
If it is determined in step S12 that the value of n does not match the number of columns, it is recognized that there are columns that have not yet been grouped, and the column number management variable n is set to n+1 to update the columns to be grouped (step S13), and it is determined whether the nth column (e.g., the number in parentheses of column B in FIG. 2) has already been assigned the X-axis direction group number gx (step S14). For example, it is determined whether the n=1 (first) column (e.g., column B(1) in FIG. 2) has already been assigned the X-axis direction group number gx. In the case of FIG. 2, the number of columns is "5", and the maximum value of n is "5".
If it is determined in step S14 that the n-th pillar has not been assigned the X-axis direction group number gx, the n-th pillar is assigned the X-axis direction group number gx (step S15). The group number is recorded in a pillar group number record file that records the group number of each pillar.
Thereafter, it is determined whether the value of n+p matches the number of columns (step S16).
The comparison target management variable p refers to the column to be compared. For example, the columns to be compared with column B(1) in FIG. 2 are column B(2), column B(3), column B(4), and column B(5) in FIG. 2. In this case, for example, the value of p for column B(2) in FIG. 2 is 1, the value of p for column B(3) is 2, the value of p for column B(4) is 3, and the value of p for column B(5) is 4. Therefore, in the case of FIG. 2, the maximum value of the number of columns to be compared p for the first column B(1) is 4, the maximum value of the number of columns to be compared p for the second column B(2) is 3, the maximum value of the number of columns to be compared p for the third column B(3) is 2, and the maximum value of the number of columns to be compared p for the fourth column B(4) is 1, so the maximum value of n+p and the number of columns match. That is, in the case of FIG. 2, the number of columns is "5", and the maximum value of n+p is also "5".
If it is determined in step S16 that the value of n+p does not match the number of pillars, it is recognized that there are remaining pillars to be compared, and the pillars to be compared are updated by setting p to p+1 (step S17). After calculating the difference ex between the central coordinate of the nth pillar (hereinafter referred to as the "centre of gravity of the pillar") and the X-coordinate of the centre of gravity of the n+pth pillar (step S18), it is determined whether the absolute value of the difference ex is less than or equal to a reference value E (step S19).
If it is determined in step S19 that the absolute value of the difference ex is equal to or smaller than the reference value E, it is determined whether or not the X-axis direction group number gx has already been assigned to the (n+p)th column (step S20).
If it is determined in step S20 that the (n+p)th column has already been assigned the X-axis direction group number gx, the process returns to step S16 and a comparison process (steps S17 to S19) is performed between the nth column and the next comparison target, the (n+p)th column.
If it is determined in step S20 that the (n+p)th column has not been assigned the X-axis direction group number gx, the (n+p)th column is assigned the X-axis direction group number gx (step S21), and then the process returns to step S16 to compare the nth column with the next comparison target, the (n+p)th column (steps S17 to S19).
In other words, if the absolute value of the difference ex of the X-coordinate between the center of gravity of the nth column and the center of gravity of the n+pth column is less than or equal to a reference value E, the n+pth column is assigned the same X-axis direction group number gx as that assigned to the nth column.
Furthermore, in step S19, if the absolute value of the difference ex is not less than or equal to the reference value E (No in step S19), the process returns to step S16 and a comparison process (steps S17 to S19) is performed between the nth column and the next comparison target, the n+pth column.
If it is determined in step S16 that the value of n+p matches the number of columns, gx is set to gx+1, p is set to 0 (step S22), and the process returns to step S12. That is, the X-axis direction group number for the (n+p)th column to be compared is updated, and the process proceeds to comparison with the nth column.
In addition, in step S19, if it is determined that the absolute value of the difference ex of the X-coordinate of the center of gravity is not less than the reference value E, the (n+p)th column will be assigned an X-axis direction group number via step S22 before the process of assigning the X-axis direction group number is completed.
If it is determined in step S14 that the n-th column has already been assigned the X-axis direction group number gx, the process returns to step S12.
Furthermore, if it is determined in step S12 that the value of n matches the number of pillars, it is recognized that the X-axis direction group number gx has been assigned to all pillars, and the same process as that for assigning the X-axis direction group number gx is performed for assigning the Y-axis direction group number gy (step S23), thereby terminating the obstacle grouping process (phase 2) and proceeding to the next process, which is the obstacle angle recognition process (phase 3).

In the obstacle angle recognition process (phase 3), the computer recognizes the corners of pillars B, such as pillar B1 with a square cross-section, pillar B2 with a rectangular cross-section, pillar B3 with a circular cross-section, and pillar B4 with an L-shaped cross-section, by assigning numbers to the corners of the pillars B in accordance with the procedures of the obstacle angle recognition process program, for example as shown in FIG. 3.
As shown in FIG. 3, for example, a number from 1 to 4 is assigned to each corner of each column B, B.... However, in the case of a column B3 (round column) with a circular cross section that has no corners, the four points on the outer periphery of the round column that intersect a line parallel to the X-axis and passing through the center coordinates of the round column with a line parallel to the Y-axis and passing through the center coordinates of the round column are regarded as corners, and a number is assigned to each of the four corners.

That is, the computer performs the obstacle angle recognition process (phase 3) as shown in the flowchart of FIG. 15 in accordance with the procedure of the obstacle angle recognition process program.
In the obstacle angle recognition process (phase 3), first, a pillar number control variable initialization process is performed, that is, the pillar number control variable n is set to 0 (step S31).
Next, it is determined whether the value of n matches the number of columns (step S32).
If it is determined in step S32 that the value of n does not match the number of columns, it is recognized that there are columns that have not yet been numbered, and n is updated to n+1 (step S33). After that, it is determined whether there are multiple corners of the nth column that have the largest Y-axis coordinate value (step S34).
In step S34, if it is determined that there is only one corner with the highest Y-axis coordinate value among the corners of the n-th pillar (No in step S34), the corner with the highest Y-axis coordinate value for the n-th pillar is assigned corner number 1 (step S35, see, for example, pillars B1 and B3 in FIG. 3), and then it is determined whether there are multiple corners with the highest X-axis coordinate value among the corners of the n-th pillar (step S37). Note that the corner numbers are recorded in a pillar corner number record file that records the corner numbers of each pillar.
That is, in the obstacle angle recognition process, the computer performs the process using storage means such as a pole number management variable register, a pole angle coordinate recording file, and a pole angle number recording file.
In step S34, if it is determined that there are multiple corners with the largest Y-axis coordinate value among the corners of the n-th column (Yes in step S34), the corners with the largest Y-axis coordinate value for the n-th column are compared with each other, and the corner with the smallest X-axis coordinate value is assigned corner number 1 (step S36; see, for example, columns B2 and B4 in FIG. 3). In other words, the corner with the smallest X-axis coordinate value among the multiple corners with the largest Y-axis coordinate value is assigned corner number 1, and then the process proceeds to step S37.
In step S37, if it is determined that there is one corner of the nth column with the largest X-axis coordinate value (No in step S37), corner number 2 is assigned to the corner of the nth column with the largest X-axis coordinate value (step S38, see e.g. columns B1 and B3 in Figure 3), and then it is determined whether there are multiple corners of the nth column with the smallest Y-axis coordinate values (step S40).
In step S37, if it is determined that there are multiple corners with the largest X-axis coordinate value among the corners of the nth column (Yes in step S37), the corners with the largest X-axis coordinate value for the nth column are compared, and the corner with the largest Y-axis coordinate value is assigned corner number 2 (step S39; see, for example, columns B2 and B4 in FIG. 3). In other words, the corner with the largest Y-axis coordinate value among the multiple corners with the largest X-axis coordinate value is assigned corner number 2, and then the process proceeds to step S40.
In step S40, if it is determined that there is one corner of the nth column with the smallest Y-axis coordinate value (No in step S40), corner number 3 is assigned to the corner of the nth column with the smallest Y-axis coordinate value (step S41, see e.g. columns B1 and B3 in Figure 3), and then it is determined whether there are multiple corners of the nth column with the smallest X-axis coordinate values (step S43).
In step S40, if it is determined that there are multiple corners with the smallest Y-axis coordinate value among the corners of the nth column (Yes in step S39), the corners with the smallest Y-axis coordinate value for the nth column are compared, and the corner with the largest X-axis coordinate value is assigned the corner number 3 (step S42; see, for example, columns B2 and B4 in FIG. 3). In other words, the corner with the largest X-axis coordinate value among the multiple corners with the smallest Y-axis coordinate value is assigned the corner number 3, and then the process proceeds to step S43.
In step S43, if it is determined that there is one corner of the nth column that has the smallest X-axis coordinate value (No in step S43), corner number 4 is assigned to the corner of the nth column that has the smallest X-axis coordinate value (step S44; see, for example, columns B1 and B3 in Figure 3), and then the process returns to step S32.
In step S43, if it is determined that there are multiple corners with the smallest X-axis coordinate value among the corners of the nth column (Yes in step S43), the corners with the smallest X-axis coordinate values for the nth column are compared, and the corner with the smallest Y-axis coordinate value is assigned corner number 4 (step S45; see, for example, columns B2 and B4 in FIG. 3). In other words, the corner with the smallest Y-axis coordinate value among the multiple corners with the smallest X-axis coordinate values is assigned corner number 4, and then the process returns to step S32.
Then, in step S32, if it is determined that the value of n matches the number of pillars, it is recognized that numbers have been assigned to each corner of all the pillars B, B..., and the obstacle angle recognition process (phase 3) is terminated, and the process proceeds to the obstacle boundary line creation process (phase 4).

In the obstacle boundary line creation process (phase 4) by the first connection line creation means, the computer creates a boundary line between pillars B, B, i.e., an obstacle boundary line (obstacle boundary line (first boundary line)), as shown in FIG. 4, in accordance with the procedure of the obstacle boundary line creation process program. For example, an obstacle boundary line is created between pillars B, B that have the same group number and are closest to each other. That is, FIG. 4 shows an example in which pillar B (4) with number 3-1 and pillar B (3) with number 3-3, which are in the same 3 group in the X-axis direction, are connected by an obstacle boundary line M, pillar B (1) with number 1-1 and pillar B (4) with number 3-1, which are in the same 1 group in the Y-axis direction, are connected by an obstacle boundary line M, and pillar B (3) with number 3-3 and pillar B (5) with number 4-3, which are in the same 3 group in the Y-axis direction, are connected by an obstacle boundary line M. That is, for each pillar, the most suitable pillar for connecting the boundary line is selected, and the pillars are connected by the boundary line.
In addition, in Figure 4, an example is shown in which a crank-shaped boundary line along the X-axis direction or a crank-shaped boundary line along the Y-axis direction is created as the inter-column boundary line M, but the inter-column boundary line M may also be a diagonal straight boundary line that intersects with the X-axis direction and the Y-axis direction, or a smoothly curved boundary line.

That is, the computer performs an obstacle boundary line creation process (phase 4) as shown in the flowchart of FIG. 16 in accordance with the procedure of the obstacle boundary line creation process program.
First, a variable initialization process is performed, that is, the column number management variable n is set to 0, and the comparison target management variable p is set to 0 (step S51).
Next, it is determined whether the value of n matches the number of columns (step S52).
In step S52, if the value of n does not match the number of columns (No in step S52), the connection candidate registration variable s is initialized, that is, s is set to Null (step S53). Furthermore, after setting n to n+1 (step S54), it is determined whether or not a boundary line has already been connected to the nth column in the positive X-axis direction (step S55).
That is, in the obstacle-to-obstacle boundary line creation process, the computer performs the process using storage means such as the above-mentioned pillar number management variable register, comparison target management variable register, connection candidate registration variable register, pillar corner coordinate recording file, and pillar corner number recording file.
The connection candidate registration variable s is a variable for temporarily recording connection candidates.
In step S55, if no boundary line is connected in the positive X-axis direction for the n-th pillar (No in step S55), it is determined whether the value of n+p matches the number of pillars (step S56).
In step S56, if the value of n+p does not match the number of columns (No in step S56), this means that there are columns remaining to be compared, so p is updated to p+1 (step S57), and then it is determined whether the X-axis direction group number of the nth column is the same as the X-axis direction group number of the n+pth column (step S58).
If it is determined in step S58 that the X-axis direction group number of the nth column and the X-axis direction group number of the (n+p)th column are the same, it is determined whether the center of gravity (central coordinates) of the (n+p)th column is in the positive X-axis direction as viewed from the nth column (step S59).
If it is determined in step S58 that the X-axis direction group number of the nth column and the X-axis direction group number of the (n+p)th column are not the same, the process returns to step S56.
If it is determined in step S59 that the center of gravity of the (n+p)th column is not in the positive X-axis direction as viewed from the nth column, the process returns to step S56.
If it is determined in step S59 that the center of gravity of the (n+p)th column is in the positive X-axis direction as viewed from the nth column, it is determined whether or not s=Null (step S60).
In step S60, if s = Null, the distance L* between the centers of gravity of the nth pillar and the (n+p)th pillar is calculated (step S61), and then n+p is substituted for the connection destination candidate variable s (step S62), and the process returns to step S56.
If s=Null is not satisfied in step S60, the distance L between the centers of gravity of the nth pillar and the (n+p)th pillar is calculated (step S63), and then it is determined whether L*>L is satisfied (step S64).
If L*>L in step S64, L is substituted for L* (step S65), n+p is substituted for the connection destination candidate variable s (step S66), and the process returns to step S56.
If it is determined in step S64 that L*>L is not satisfied, the process returns to step S56.
If it is determined in step S56 that the value of n+p matches the number of pillars, it is determined whether s=Null (step S67). If s=Null, the process returns to step S52. If s=Null is not true, the process returns to step S52. If s=Null is not true, the process draws a boundary line M between the second corner of the nth pillar and the fourth corner of the sth pillar (for example, in FIG. 4, a boundary line M that extends rightward from the second corner of pillar B(1) to connect to the fourth corner of pillar B(4)), and then returns to step S52.
Then, in step S52, if it is determined that the value of n and the number of pillars match, the connection process to the positive X-axis direction boundary line is terminated, and then the connection process to the negative X-axis direction boundary line, the connection process to the positive Y-axis direction boundary line, and the connection process to the negative Y-axis direction boundary line are each performed in the same manner as the connection process to the positive X-axis direction boundary line (however, the connection to the boundary line in the X-axis direction is made between corner number 2 and corner number 4, and the connection to the boundary line in the Y-axis direction is made between corner number 1 and corner number 3) (step S69).
Then, when the process of connecting to the negative X-axis direction boundary line, the process of connecting to the positive Y-axis direction boundary line, and the process of connecting to the negative Y-axis direction boundary line are completed, the process proceeds to the next divided area division process (phase 5).

The obstacle boundary line creation process (phase 4) will now be described in more detail.
4 as an example, in step S58, column B(1) as the n=1th column and column B(2) as the n+p=2nd column do not have the same X-axis group number, so in step S57, column B(1) is compared with column B(3) as the n+p=3rd column in step S58. Since columns B(1) and B(3) also do not have the same X-axis group number, column B(1) is compared with column B(4) as the n+p=4th column in step S57. Columns B(1) and B(4) have the same X-axis group number, so in step S60, after steps S59 and S60, the distance L* between the centers of gravity of columns B(1) and B(4) is calculated, and the number of column B(4), n+p="4", is stored as the connection candidate variable s. After that, in step S57, column B(1) is compared with column B(5) which is the n+p=5th column in step S58. Since columns B(1) and B(5) do not have the same X-axis direction group number, the process returns to step S57, and in step S67, in step S68, the second corner of column B(1) and the fourth corner of column B(4) are connected with a boundary line.
In the example of Fig. 4, three or more columns do not have the same X-axis direction group number, but if, for example, there is a column B(6) not shown in Fig. 4 that has the same X-axis direction group number as columns B(1) and B(4), the distance L between the centers of gravity of column B(1) and column B(6) is calculated in step S63. Then, in step S64, if the distance L between the centers of gravity of column B(1) and column B(6) is smaller than the distance L* between the centers of gravity of column B(1) and column B(4), the number of column B(6), n+p = "6", is stored as the connection destination candidate variable s, and after step S67, in step S68, the second corner of column B(1) and the fourth corner of column B(6) are connected by a boundary line.

In the divided area division process (phase 5) using the second connection line creation means and the third connection line creation means, the computer creates a boundary line N (second boundary line) connecting the pillar B and the movement target area boundary line C, or a boundary line Q (third boundary line) connecting the pillar B and the inter-pillar boundary line M (first boundary line) or the boundary line N (second boundary line) as shown in Figure 5, in accordance with the procedures of the divided area division process program, and divides the movement target area A into a number of divided areas E, E... (see Figure 6) which are a number of movable areas partitioned by boundaries C, M, N, Q.
In other words, in the obstacle-to-obstacle boundary creation process (phase 4), a boundary line N (second boundary line) is created that connects the corner of pillar B that is not connected by the inter-pillar boundary line M to the movement target area boundary line C, or a boundary line Q (third boundary line) that connects the corner of pillar B that is not connected by the inter-pillar boundary line M (first boundary line) to the inter-pillar boundary line M (first boundary line) or boundary line N (second boundary line).
As a result, the movement target area A is divided into a plurality of divided areas E, E . . . (see FIG. 6) which are a plurality of movable areas partitioned by boundary lines C, M, N, and Q.

That is, the computer performs the divided area division process (phase 5) as shown in the flowchart of FIG. 17 in accordance with the procedure of the divided area division process program.
In the division area division process (phase 5), first, a variable initialization process is performed, that is, the column number management variable n is set to 0 (step S71).
Next, it is determined whether the value of n matches the number of columns (step S72).
In step S72, if the value of n does not match the number of pillars, it means that there are still pillars to be compared, so the pillar corner number management variable is initialized, i.e., the pillar corner number management variable c is set to 1 (step S73), and further, the pillar number management variable n is updated to n+1 (step S74), and it is determined whether or not a boundary line has already been connected for the corner of the nth pillar with corner number c (step S75).
That is, in the division area division process, the computer performs the process using storage means such as a column number management variable register, a column corner number management variable register, a column corner coordinate recording file, and a column corner number recording file.
In step S75, if no boundary line is connected to the corner with corner number c of the n-th pillar, it is determined whether c=1 (step S76).
If it is not determined in step S76 that c=1, it is determined whether or not c=2 (step S77).
If it is not determined in step S77 that c=2, it is determined whether or not c=3 (step S78).
In step S78, if c=3 is not satisfied, the boundary line N is extended in the negative X-axis direction from corner number 4 until it contacts either a wall, a pillar, or a boundary line (step S79, see, for example, pillar B(1), pillar B(2), and pillar B(3) in FIG. 5). After that, the pillar corner number control variable c is updated to c+1 (step S80), and it is determined whether c=5 is satisfied (step S81).
In step S76, if c=1, the boundary line N is extended in the positive Y-axis direction from corner number 1 until it contacts either a wall, a pillar, or a boundary line (step S82, see, for example, pillar B(1), pillar B(2), and pillar B(3) in FIG. 5). Then, the process proceeds to step S80.
Also, in step S77, if c=2, the boundary line N is extended in the positive X-axis direction from corner number 2 until it touches either a wall, a pillar, or a boundary line (step S83, see, for example, pillar B(2) and pillar B(4) in FIG. 5). Then, the process proceeds to step S80.
Also, in step S78, if c=3, the boundary line N is extended in the negative Y-axis direction from corner number 3 until it touches either a wall, a pillar, or a boundary line (step S84, see, for example, pillar B(1), pillar B(2), and pillar B(4) in FIG. 5). Then, the process proceeds to step S80.
That is, after the process of extending the boundary line from each corner number is completed (steps S82, S83, S84, S79), the column corner number control variable c is updated to c+1 (step S80), and it is determined whether c=5 (step S81).
If c=5 in step S81, the process returns to step S72 and moves to the process for the next column to be compared.
If it is determined in step S81 that c=5, the process returns to step S75, and the processes in steps S75 to S84 are repeated.
Then, in step S72, if the value of n matches the number of columns, the divided area division process (phase 5) is terminated, and the process proceeds to the divided area recognition process (phase 6).

In the divided area recognition process (phase 6), the computer recognizes each of the multiple divided areas E, E... by assigning numbers as identification information in a predetermined order to each of the multiple areas separated by lines in the movement target area A (the area outside the wall (the area outside the movement target area A), the area inside the pillar B (obstacle area), and all of the divided areas) in accordance with the procedures of the divided area recognition process program.
The divided area recognition process (phase 6) is a process in which areas are extracted by a filling process, for example, as shown in Figures 8 and 23 to 25, an individual area number is assigned to each extracted area, and then each divided area E, E... is recognized.

The computer performs the divided area recognition process (phase 6) as shown in the flowchart of FIG. 18 in accordance with the procedure of the divided area recognition process program.
In the divided area recognition process, the computer uses storage means such as a fill-in judgment and area number recording array file, an X-axis direction search management variable register, a Y-axis direction search management variable register, an area number management variable range register, an X-axis direction fill-in management variable register, a Y-axis direction fill-in management variable register, a fill-in management file, and a fill-in management variable temporary holding register, and performs the process while referring to the values stored in these storage means.
First, variables are initialized. That is, the fill-in judgment and area number recording array Stack[Xmax][Ymax] is set to [0,0,0,...], the X-axis direction search management variable i is set to 0, the Y-axis direction search management variable j is set to 0, and the area number management variable a is set to 1 (step S91). That is, the X-axis direction search management variable register is set to 0, the Y-axis direction search management variable register is set to 0, and all values of each XY coordinate position in the fill-in judgment and area number recording array file are maintained at 0, and the area number management variable range register is set to 1, and the process begins with filling the area outside the movement target area A with "1".
First, it is determined whether i>Xmax is satisfied (step S92), and if i>Xmax is not satisfied, it is determined whether Stack[i][j]=0 is satisfied (step S93).
In step S93, if Stack[i][j]=0, Stack[i][j] is set to -1 (step S94), resulting in, for example, the states shown in Figures 8(b) and (f), Figures 23(b) and (d), Figures 24(b), (d), and (f), and Figure 25(b).
Thereafter, the filling control variables are initialized, that is, the X-axis direction filling control variable fi is set to i, and the Y-axis direction filling control variable fj is set to j (step S95).
In the fill management, when performing fill processing for each area, in order not to fill areas that already have area numbers, the values of each XY coordinate position are managed in a fill management file that is separate from the fill judgment and area number record array file. That is, the values of each XY coordinate position in the fill judgment and area number record array file, Stack[i][j], are replaced with the values of each XY coordinate position in the fill management file, Stack[fi][fj] (see FIG. 23(d) for example), so that the values of each XY coordinate position in areas that already have area numbers are not searched for, thereby making it possible to speed up the fill processing.
Next, it is determined whether fi>Xmax (step S97).
If fi>Xmax is not satisfied in step S97, it is determined whether Stack[fi][fj]=-1 is satisfied (step S98).
In step S98, if Stack[fi][fj] = -1 (YES in step S98), proceed to step S98A, set mi to fi and mj to fj in the fill management variable temporary holding register, and then set Stack[fi][fj] to a (step S99).
Then, it is determined whether or not the coordinate (fi+1, fj) exists, there is no wall, pillar, or boundary between the coordinate (fi, fj), and Stack[fi+1][fj] is 0 (step S100). In other words, if there is no wall, pillar, or boundary between the coordinate [fi][fj] set to a (initially "1") and the coordinate (fi+1, fj) on the positive side of the X-axis direction of the coordinate [fi][fj], and the coordinate (fi+1, fj) is 0 (Yes in step S100), Stack[fi+1][fj] is set to -1 (step S104). Then, proceed to step S101.
If the answer is No in step S100, that is, if a wall, pillar, or boundary line passes between (fi, fj) and (fi+1, fj), proceed to step S101 to determine whether or not the coordinate (fi-1, fj) exists, there is no wall, pillar, or boundary line between the coordinate (fi, fj), and Stack[fi-1][fj] is 0. In other words, if there is no wall, pillar, or boundary line between the coordinate [fi][fj] set to a (initially "1") and the coordinate (fi-1, fj) on the negative side of the X-axis direction of the coordinate [fi][fj], and the coordinate (fi-1, fj) is 0 (if the answer is Yes in step S101), then set Stack[fi-1][fj] to -1 (step S105). Thereafter, the process proceeds to step S105A, where mi is set to fi-1 (except when fi=0), and the process proceeds to step S102.
If the answer is No in step S101, that is, if a wall, pillar, or boundary line passes between (fi, fj) and (fi-1, fj), the process proceeds to step S102, where it is determined whether or not the coordinate (fi, fj+1) exists, there is no wall, pillar, or boundary line between the coordinate (fi, fj), and Stack[fi][fj+1] is 0. In other words, if there is no wall, pillar, or boundary line between the coordinate [fi][fj] set to a (initially "1") and the coordinate (fi, fj+1) on the Y-axis direction + side of the coordinate [fi][fj], and the coordinate (fi, fj+1) is 0 (if the answer is Yes in step S102), Stack[fi][fj+1] is set to -1 (step S106). Then, the process proceeds to step S103.
If the answer is No in step S102, that is, if a wall, pillar, or boundary line passes between (fi, fj) and (fi, fj+1), proceed to step S103 to determine whether or not the coordinate (fi, fj-1) exists, there is no wall, pillar, or boundary line between the coordinate (fi, fj), and Stack[fi][fj-1] is 0. In other words, if there is no wall, pillar, or boundary line between the coordinate [fi][fj] set to a (initially "1") and the coordinate (fi, fj-1) on the negative side of the Y-axis direction of the coordinate [fi][fj], and the coordinate (fi, fj-1) is 0 (if the answer is Yes in step S103), then Stack[fi][fj-1] is set to -1 (step S107). Thereafter, the process proceeds to step S107A, where mj is set to fj-1 (except when fi=0), and then the process proceeds to step S103A, where fi is set to mi and fj is set to mj.
If step S103 is No, that is, if there is a wall, pillar, or boundary line between (fi, fj) and (fi, fj-1), the process also proceeds to step S103A, where fi is set to mi and fj is set to mj.
After the processing of step S103A, the process returns to step S97.
If it is not determined in step S98 that Stack[fi][fj]=-1, fi is set to fi+1 (step S108), and the process returns to step S97.
If fi>Xmax in step S97, the process proceeds to step S109, where fi is set to 0 and fj is set to fj+1, and then it is determined whether fj>Ymax (step S110).
In step S110, if fj>Ymax is not satisfied, the process proceeds to step S98, and if fj>Ymax is satisfied, the process proceeds to step S111.
As a result of the above, the states shown in FIGS. 8(c) to (f) and FIGS. 23(c) and (d) are obtained, for example.
In step S111, it is determined whether a = 1, and if a = 1 is not true, the process proceeds to step S112 to determine whether the a-th section is in contact with pillars (whose coordinates are known) on all four sides and whether the numbers n of the pillars in contact are all the same.
In step S111, if a=1, it is determined that the a=1th section is outside the wall (step S115), and then the process proceeds to step S112.
If the answer is No in step S112, a is set to a+1 (step S113), i is set to i+1 (step S114), and the process returns to step S92.
If the answer is Yes in step S112, it is determined that the a-th section is inside a pillar (step S116), and then the process proceeds to step S113.
That is, if the computer determines that the four sides of the boundary line of an area (top, bottom, left, and right in FIG. 6) match the boundary lines of column B, and that the boundary lines of column B are the boundary lines of column B with the same number, the computer determines that the area is an area inside a column. In other words, an area where a=1 is not satisfied and does not satisfy the condition for an area inside a column is recognized as a divided area.
In other words, if it is determined in step S110 that fj > Ymax, the filling process for one area is completed, and if the answer is No in steps S111 and S112, the filled area is a divided area, and the divided area is assigned the number a and recognized.
If it is determined in step S93 that Stack[i][j]=0 is not met, i is set to i+1 (step S114), and the process returns to step S92.
Also, in step S92, if i>Xmax, i is set to 0 and j is set to j+1 (step S117), and then it is determined whether j>Ymax is true (step S118). If j>Ymax is not true, the process returns to step S93; if j>Ymax is true, the divided area recognition process (phase 6) is terminated.
This completes the division process (phases 1 to 6) of the movement target area A, and the process then proceeds to the creation process of the movement route (phases 7 to 11).

The divided region recognition process (phase 6) will be described with reference to the above-mentioned step S and to FIGS.
In addition, FIG. 8 shows an example in which two areas are extracted by painting processing, and each extracted area is assigned an individual number.
26 to 28 show examples in which a plurality of areas are extracted by painting, and each extracted area is assigned an individual number in ascending order.
First, in step S91, as shown in Figures 8(a) and 26(a), the values of the fill-in judgment and area number recording array file, i.e., the XY coordinate matrix Stack[Xmax][Ymax] indicating each XY coordinate position of the entire area to be moved A and the entire area including the periphery of the area to be moved A, are all set to 0.
Then, through steps S92, S93, S94 and S95, the state shown in FIG. 8(b) and FIG. 26(b) is reached.
Then, through steps S97 to S107A, the processes shown in FIGS. 8(c) to (f) and FIG. 26(c) are carried out.
In addition, steps S105A and S107A are processes for returning the coordinate position and searching when there is a recess as shown in Fig. 8(e) and (f). That is, in this case, in order to perform processing by returning the coordinate in the negative direction in the X direction or the negative direction in the Y direction, the returned coordinate position is temporarily stored as variables mi and mj in the filling management variable temporary storage register and then processed.
Then, after the number a has been assigned to all coordinates of any area (YES in step S110), a determination is made as to whether the area is an area outside the wall (area outside the area to be moved A) or an area inside the pillar, which is a divided area (steps S111, 112), after which the number of the next area is updated (step S113) and the process proceeds to fill in the next area (see Figures 8 (f) and (g), Figure 26 (d), Figures 27 (a) to (f), and Figures 28 (a) to (d)).
In step S113, a number is assigned to each area in ascending order. Note that Figures 26 to 28 show an example in which area a is assigned number 1, area b is assigned number 2, area c is assigned number 3, area d is assigned number 4, area e is assigned number 5, and area f is assigned number 6. In other words, an example in which each area is assigned a number in ascending order is shown.

Next, in the process of creating a travel route (phase 7 to phase 11), first, the process of creating an equally spaced straight line route (phase 7) is performed.
In the equally-spaced straight-line path creation process (phase 7), the computer sets a plurality of horizontal straight lines S, S... at equal intervals along the Y-axis direction within the movement target area A in accordance with the procedure of the equally-spaced straight-line path creation process program, and creates an equally-spaced straight-line path that is the basis of a zigzag movement planned route within a divided area, which will be described later. Fig. 9 shows an example in which a plurality of horizontal straight lines S, S... at equal intervals along the Y-axis direction are set within the movement target area A.
That is, the means for executing the equally spaced straight line path creation process (phase 7) functions as a horizontal straight line creation means for creating a plurality of horizontal straight lines S, S... parallel to the X axis that divide the movement target area A at equal intervals along the Y axis.

Next, in the intersection coordinate extraction process (phase 8), the computer follows the procedure of the intersection coordinate extraction process program to extract the intersection coordinates G, G... of the boundaries C, M, N, Q and the boundary of pillar B (obstacle area boundary) that divide each area (the area outside the wall (area outside the area A to be moved), the area inside the pillar, and all divided areas) with multiple straight lines S, S..., as shown in Figure 10.

That is, the computer performs the equally spaced straight line path creation process (phase 7) and the intersection coordinate extraction process (phase 8) as shown in the flowchart of FIG. 19, in accordance with the procedures of the equally spaced straight line path creation process program and the intersection coordinate extraction process program.
First, the boundary line number control variable m is initialized, that is, the boundary line number control variable m is set to 0 (step S121).
Next, the smallest y coordinate value in the search range (the y coordinate of the lowest end of the exterior wall) is identified, and this value is set as y (step S122).
Then, a straight line S that is parallel to the X-axis and has an intercept of y is defined (step S123).
Next, it is determined whether the m-th boundary line (including the periphery of the wall and the pillar) has an intersection with the line S (step S124).
If it is determined in step S124 that the mth boundary line has an intersection with the straight line S, the coordinates of the intersection are recorded in the intersection coordinate recording file (step S125), and then m is set to m+1 (step S126), and it is determined whether the value of m matches the total number of boundary lines (step S127).
If it is determined in step S124 that the m-th boundary line does not have an intersection with the line S, the process proceeds to step S126.
If the value of m does not match the total number of borders in step S127, the processes in steps S124 to S126 are repeated until the value of m matches the total number of borders.
In step S127, if the value of m matches the total number of boundary lines, y is set to y+the lane distance (step S128), and it is determined whether the value of y exceeds the upper limit of the search range (step S129).
In step S129, if the value of y does not exceed the upper limit of the search range, the processes in steps S118 to S118 are repeated until the value of y exceeds the upper limit of the search range.
In step S129, if the value of y exceeds the upper limit of the search range, the intersection extraction process is terminated and the process proceeds to the intersection coordinate extraction process for each area (phase 9).
That is, in the equally spaced straight line path creation process and the intersection coordinate extraction process, the computer performs the process while using storage means such as a boundary line number management variable register, a y coordinate recording file for each straight line S, and an intersection coordinate recording file.

In step S122, the "search range" in y←search range . . . refers to the movement target area A surrounded by C.
Moreover, "define straight line S" in step S123 refers to, for example, the straight line S shown in Fig. 9. Therefore, in the process of creating a proposed movement route candidate line in Fig. 19, the process of drawing straight lines S one by one in order from bottom to top in Fig. 9 and recording the coordinates of the intersections between the straight line S and each boundary line each time a straight line S is drawn is repeated. Note that straight lines S are also set on the horizontal lines at the bottom and top end positions of the movement target area boundary line C.
In addition, the "distance between rails" in step S128 refers to the distance between adjacent straight lines S, S in the vertical direction (Y-axis direction), and the value (length) of this "distance between rails" is determined in advance to an appropriate length (for example, 10 cm).
Therefore, the coordinates of the intersections between each of the straight lines S, S . . . that form the basis of the planned zigzag movement route within the divided area and all of the boundary lines are all recorded in the intersection coordinate recording file.
In this case, for example, in the intersection coordinate recording file, the intersections are numbered in ascending order of X and Y coordinates, and the X and Y coordinates of each intersection are recorded (see the circled numbers indicating the intersection X and Y coordinates in FIG. 12).

In the area-by-area intersection coordinate extraction process (phase 9), the computer extracts, for each area, the coordinates of intersections G, G... on the boundary lines C, M, N, Q and the boundary line of pillar B (obstacle area boundary line) that divide each area, in accordance with the procedures of the area-by-area intersection coordinate extraction process program.
FIG. 11 shows an example in which intersection coordinates G, G . . . on boundaries C, N that define a divided area E to which area number 6 has been assigned are extracted.

The computer performs an area-by-area intersection coordinate extraction process (phase 9) as shown in the flow chart of FIG. 20 in accordance with the procedure of the area-by-area intersection coordinate extraction process program.
First, variables are initialized: the intersection number management variable k is set to 0, and the area number management variable a is set to 1 (step S131).
Next, it is determined whether or not the value of k exceeds the number of intersections recorded in the intersection coordinate recording file in the intersection coordinate extraction process (step S132).
If it is determined in step S132 that the value of k does not exceed the number of intersections recorded in the intersection coordinate recording file, it is determined whether the value of a of area a exceeds the number of areas (step S133).
If the value of a does not exceed the number of areas in step S133, it is determined whether or not the kth intersection is adjacent to area a (step S134).
If it is determined in step S134 that the kth intersection is adjacent to area a, it is determined whether or not the same coordinates as the kth intersection have already been assigned to the intersection coordinate recording file for the ath area (step S135).
If it is determined in step S134 that the k-th intersection is not adjacent to area a, k is set to k+1 (step S137), and then the process returns to step S1132.
If it is determined in step S135 that the intersection coordinate recording file for the a-th area already has the same coordinates as the k-th intersection recorded therein, the process proceeds to step S137.
If it is determined in step S135 that the intersection coordinate recording file for the a-th area does not have coordinates identical to those of the k-th intersection recorded therein, the coordinates of the k-th intersection are recorded in the intersection coordinate recording file for the a-th area (step S136), and then the process proceeds to step S137.
If it is determined in step S132 that the value of k exceeds the number of intersections, k is set to 0 and a is set to a+1 (step S138), and then the process proceeds to step S133.
If it is determined in step S133 that the value of a exceeds the number of areas, the process of extracting intersection coordinates for each area (phase 9) is terminated, and the process proceeds to the process of creating a planned zigzag movement route within the divided area (phase 10).
That is, in the area-by-area intersection coordinate extraction process, the computer performs the process while using storage means such as the intersection number management variable register, the area number management variable register, the intersection coordinate recording file, and the intersection coordinate recording file for each area.

In the area-by-area intersection coordinate extraction process (phase 9), for example, by determining which area each intersection is adjacent to, starting from the intersection with the smallest XY coordinate value, the intersection number and the XY coordinate of the intersection are recorded in the intersection coordinate recording file for each area. In other words, the intersection coordinates are extracted for each area and recorded in the intersection coordinate recording file for each area (see FIG. 29(a)).
First, in step S131, the intersection number management variable k is set to 0 and the area number management variable a is set to 1, so that area a=1, i.e., the intersections that intersect with the boundary line C surrounding the movement target area A, are recorded in a predetermined order (for example, the intersection with the smallest XY coordinate is set to k=1, and the value of k is incremented by 1 in order from the intersection with the smallest X and Y coordinates). Then, for each area, it is checked whether the coordinates of the intersections recorded in the intersection coordinate recording file in the intersection coordinate extraction process are adjacent to each area (steps S132 to S134), and an intersection coordinate recording file for each area is created (step S136).
That is, in the area-by-area intersection coordinate extraction process (phase 9), each area is associated with each intersection (step S136).
That is, the coordinates of the intersection between the line dividing each area and the straight line S are extracted and recorded as the coordinates of the intersection for each area.
As described above, the means for executing the intersection coordinate extraction process (phase 8) and the area-specific intersection coordinate extraction process (phase 9) function as a first intersection recognition means for recognizing the intersections between the boundaries C, M, N, Q and pillar B dividing each area (movement target area boundary, boundary, obstacle area boundary) and each horizontal straight line S, S.... In other words, it functions as a first intersection recognition means for recognizing the intersections between the divided area boundary and the horizontal straight line.

In the process of creating a planned zigzag movement route within a divided area (phase 10), the computer follows the procedures of the process of creating a planned zigzag movement route within a divided area program to create a zigzag planned zigzag movement route H within each divided area E, E... by connecting adjacent coordinates G, G on a straight line S along the X-axis for each divided area E, E..., as shown in Figure 12, and connecting intersection coordinates G, G between adjacent straight lines S, S along the Y-axis.
The zigzag planned movement route H in the divided area is a route that repeats a route that moves in one direction in the X-axis direction and then turns back in the other direction opposite to the one direction in the X-axis direction. Note that, in the equally spaced straight line route creation process, when a plurality of vertical straight lines with equal intervals along the X-axis direction are set, a zigzag planned movement route in the divided area is created that repeats a route that moves in one direction in the Y-axis direction and then turns back in the other direction opposite to the one direction in the Y-axis direction.
In addition, the intersections recorded in the intersection coordinate recording file for each area are recorded with the intersection numbers being discontinuous. For example, in FIG. 12, when the intersection numbers are assigned in order from the intersection with the smallest XY coordinate value and it is determined which area each intersection is adjacent to, the intersection numbers are assigned as shown in the circles in FIG. 12. For example, in the intersection coordinate recording file for the area (divided area) assigned the number 2 in FIG. 12, the intersections with the intersection numbers 1, 2, 6, 7, 11, 12, 16, 17, and 18 are recorded in order as shown in FIG. 26(a). However, if the intersections are traced in the order of recording in FIG. 26(a), for example, a sawtooth route will result. Therefore, in the process of creating a zigzag movement route within a divided area (phase 10), as shown in Fig. 26(b), the order of recording of each intersection is rearranged so that the XY coordinates of each intersection are arranged in order from the start point to the end point of the route that forms a zigzag route in the sorted intersection coordinate recording file for each area. For example, as shown in Fig. 29(b), in the sorted intersection coordinate recording file for the area (divided area) given the number 2 in Fig. 12, each intersection is recorded in the order of intersection numbers 16, 18, 12, 11, 6, 7, 2, 1. Therefore, in the divided area, a zigzag movement route within a divided area is created that follows the intersection coordinates in the order recorded in the sorted intersection coordinate recording file for each area (divided area).

The computer performs a process (phase 10) of creating a planned zigzag movement route within a divided area as shown in the flowchart of FIG. 21, in accordance with the procedure of a program for creating a planned zigzag movement route within a divided area.
First, variables are initialized: area number management variable a is set to 1, sort management variable i is set to 1, and sort criterion change variable j is set to 1 (step S141).
The sort control variable i is a variable that controls where in the array the numerical values that have been rearranged by sorting are to be placed, and the sort criterion change variable j is a control variable that is used when changing the sorting criteria so that the root becomes a zigzag rectangular wave root rather than a sawtooth root.
In the process of creating a planned zigzag movement route within a divided area, the computer performs the process using storage means such as an area number management variable register, a sorting management variable register, a sorting criterion change variable register, an intersection coordinate recording file for each area, and a post-sort intersection coordinate recording file for each area.
Next, it is determined whether the value of a exceeds the upper limit of the number of areas (step S142).
If it is determined in step S142 that the value of a does not exceed the upper limit of the number of areas, it is determined whether the a-th area is a valid area, that is, whether it is not outside a wall or inside a pillar (step S143).
If it is determined in step S143 that the a-th area is a valid area, the intersection coordinates with the largest Y coordinate are searched for in the intersection coordinate recording file for this a-th area (step S144).
Then, in step S145, it is determined whether there are a plurality of intersection coordinates with the largest Y coordinate.
If it is determined in step S145 that there is only one intersection coordinate with the largest Y coordinate, the coordinate data searched in step S144 is moved to the i-th position of the sorted intersection coordinate recording file for the a-th area (step S146). That is, if i is "1", the intersection number and the X and Y coordinate values of the intersection with the largest Y coordinate are recorded in the first recording area of the sorted intersection coordinate recording file for the a-th area. That is, the intersection with the largest Y coordinate is recorded first.
In step S146, the i-th data recorded in the intersection coordinate recording file for the a-th area is moved to the i-th data in the sorted intersection coordinate recording file for the a-th area, and this i-th data is deleted from the intersection coordinate recording file for the a-th area.
Therefore, in the next step S144, the coordinate with the largest Y coordinate is searched for among the data in the intersection coordinate recording file for the a-th area from which the i-th data has been removed.
It is also possible to carry out processing using a processing record file which is a copy of the area intersection coordinate record file, without deleting the data from the area intersection coordinate record file, and then delete the data from the processing record file.
In addition, in step S145, intersection coordinates that are candidates for the start position of movement in each divided area are extracted, and in the subsequent step, the intersection coordinate recorded first in the intersection coordinate recording file after sorting is determined to be the intersection coordinate that will be the start position of movement in each divided area, and a zigzag route is created in each divided area by tracing a straight line S from the intersection coordinate that is the start position of movement to the intersection coordinate that is the end position of movement, and changing course at the intersection coordinate position.
If it is determined in step S145 that there are two coordinates with the largest Y coordinate, it is determined whether the value of the sorting criterion change variable j is odd (step S150), and if it is determined that the value of j is odd, the coordinate with the largest Y coordinate and the smallest X coordinate is searched for (step S151), and then j is set to j+1 (step S152).Then, the process proceeds to a process of transferring the searched coordinate data to the i-th position in the sorted intersection coordinate recording file for the a-th area (step S146).
Also, if it is determined in step S150 that the value of j is an even number, the coordinate with the largest Y coordinate and the largest X coordinate is searched for (step S153), and then j is set to j+1 (step S152), after which the process proceeds to step S146.
If it is determined in step S145 that there are three or more coordinates with the largest Y coordinate, the coordinate with the largest Y coordinate and the smallest X coordinate and the coordinate with the largest Y coordinate and the smallest X coordinate (intermediate intersection coordinates) are deleted (step S154). After that, the same process as when it is determined in step S145 that there are two coordinates with the largest Y coordinate is performed, and the process proceeds to step S146.
For example, in area 2 in Fig. 12, first in step S144, the Y coordinates of intersections numbered 16, 17, and 18 are found to be the largest, and then through steps S145 and S154, intersection number 17 is deleted. Then, since j = 1, the process proceeds to step S151, where the X and Y coordinates of intersection number 16 are found. After that, j is set to j + 1 (step S152), and intersection number 16 and its X and Y coordinates are recorded in the first recording area of the intersection coordinate recording file after sorting for area 2 (divided area) (see Fig. 29 (b)). Then, in step S144, the intersection coordinates of numbers 11 and 12 are searched for as having the largest Y coordinates, and if in step S145 it is determined that there are two coordinates with the largest Y coordinate, then in this case j=2, the process proceeds to step S153, where the intersection coordinates of number 12, which have the largest Y coordinate and the largest X coordinate, are searched for, and intersection number 12 and the X and Y coordinates of the intersection are recorded in the third recording area of the sorted intersection coordinate recording file for area 2 (divided area) (see Figure 29 (b)).
That is, when there are multiple coordinates with the largest Y coordinate, the criterion for searching for the coordinate with the smallest X coordinate or the coordinate with the largest X coordinate is switched based on the value of j, so that the route becomes a zigzag rectangular wave route rather than a sawtooth route.
After step S146, it is determined whether a straight line connecting the (i-1)th coordinate to the i-th coordinate in the sorted intersection coordinate recording file for area contacts an exterior wall or a pillar (step S147). If there is no contact, i is updated to i+1 (step S147E), and it is determined whether coordinate data remains in the intersection coordinate recording file for the a-th area (step S148).
If it is determined in step S147 that the straight line contacts an exterior wall or a pillar, the i-th coordinate data in the sorted intersection coordinate recording file for area is moved to the i+1th coordinate data, and the i+1th X coordinate and the i+1th Y coordinate are written in the i-th region (step S147A). Then, i is updated to i+2 (step S147B), and the process proceeds to step S148.
That is, in steps S147A and S147B, when the route comes into contact with an exterior wall or a pillar as shown in FIG. 30(a), the route is corrected so as not to come into contact with the exterior wall or the pillar as shown in FIG. 30(b).
Next, in step S148, if it is determined that coordinate data remains in the intersection coordinate recording file for the a-th area, the process returns to step S144.
If it is determined in step S148 that no coordinate data remains in the intersection coordinate recording file for the a-th area, the process proceeds to step S147C to determine whether the first and second Y coordinate values in the sorted intersection coordinate recording file for the a-th area are the same.
If it is determined in step S147C that the first and second Y coordinate values are not the same, the first recorded coordinate information is erased, and the i-th coordinate information is moved to the (i-1)th coordinate information (step S147D).
That is, as shown in FIG. 12, for example, in areas 3 and 11, the first Y coordinate and the second Y coordinate in the sorted intersection coordinate recording file are not the same, so the second intersection coordinate position (intersection 3s, 11s) is used as the starting point, and the recording order of the third and subsequent intersection coordinates in the sorted intersection coordinate recording file is moved up by one.
That is, in steps S147C and S147D, a process is performed to determine the intersection coordinates that will be the start position of movement in each divided area so that the route (path) connecting the intersection coordinates that are the start position of movement in each divided area to the next intersection coordinates is a route parallel to the X-axis.
If it is determined in step S147C that the first and second Y coordinate values are the same, the process proceeds to step S149, where a is set to a+1, i to 1, and j to 1, and the process returns to S142. That is, the sorting process of the currently processed area a ends, and the process moves to the sorting process of the next area.
If it is determined in step S143 that the a-th area is not a valid area, the process proceeds to step S149, where a is set to a+1, i to 1, and j to 1, and the process returns to step S142. That is, the process proceeds to sorting of the next area.
If it is determined in step S142 that the value of a exceeds the upper limit of the number of areas, the process of creating a zigzag movement planned route within the divided area (phase 10) is terminated, and the process proceeds to the movement cost calculation process (phase 11).
In other words, a route that follows the intersection coordinates recorded in the sorted intersection coordinate recording file for the ath area in the order in which they were recorded is created as the planned zigzag movement route within the divided area (see Figure 26 (b) and the planned zigzag movement route H within the divided area shown by the dotted line in area 2 of Figure 12).
That is, in the process of creating a zigzag movement route within the divided area (phase 10), for example, as shown in Fig. 12, a zigzag movement route H is created within the divided area that connects the planned start point (coordinate) 2s and the planned end point (coordinate) 2e in the area 2. In addition, the planned start point (coordinate) Ns and the planned end point (coordinate) Ne (N is an integer excluding 7, 10, 12, 16, and 18 from 2 to 19) of each area (areas excluding pillar areas 7, 10, 12, 16, and 18 from 2 to 19) are determined, and a zigzag movement route (first route for each divided area) H is created within the divided area that connects the planned start point (coordinate) Ns and the planned end point (coordinate) Ne.
As described above, the means for executing the process for creating a planned zigzag movement route within a divided area (phase 10) functions as a first route creation means for creating a first zigzag route for each divided area that proceeds along the Y axis formed by connecting the intersections on the boundary lines of each divided area with horizontal straight lines.

In the movement cost calculation process (phase 11), the computer calculates the movement cost of each of the planned zigzag movement routes (first routes) H, H... within each divided area created in phase 10, according to the procedures of the movement cost calculation process program. In other words, the movement cost is calculated for each of the planned zigzag movement routes H, H... within each divided area, taking into account the total straight distance, total turning angle, and number of turns.

The computer performs a movement cost calculation process (phase 11) as shown in the flowchart of FIG. 22 in accordance with the procedure of the movement cost calculation process program.
First, the area (division area) number and the total cost array file are initialized. That is, the area number management variable a is set to 1, and the total cost array CtHorizontal[amax] in the total cost array file for each area is set to [0,0,0,...] (step S201). In addition, the post-sort intersection coordinate management variable i is set to 1 (step S202).
In the movement cost calculation process, the computer performs the process while using storage means such as an area number management variable register, a sorted intersection coordinate recording file for each area, and a total cost array file for each area.
The total cost array file is a file that stores the cost of the travel route in each area, and the total cost array CtHorizontal is the total cost (travel efficiency evaluation value) of the first route in each area. Also, the sorted intersection coordinate management variable is a variable that manages the number of the corner (intersection) on the travel route in the area.
Next, the distance L between the i-th coordinate and the (i+1)-th coordinate in the sorted intersection coordinate recording file for the a-th area is calculated (step S203).
Then, the distance L is multiplied by the straight-line movement cost conversion constant Ks to calculate the cost Cs of straight-line movement (step S204), and the cost Cs of straight-line movement is added to the total cost array CtHorizontal[a] (step S205). After that, i is set to i+1 (step S206), and it is determined whether the i-th coordinate data is present in the sorted intersection coordinate recording file for the a-th area (step S207).
If the answer is Yes in step S207, the cost Cstop (constant) required for stopping is added to the total cost array CtHorizontal[a] (step S208). In other words, a temporary stop is required to move on to a turning action. The stopping time is considered to be constant regardless of the turning angle. Therefore, a constant cost is added here. The specific value depends on the stopping performance (acceleration performance) of the moving body 1.
Next, an angle θ between a vector extending from the (i-1)th coordinate to the i-th coordinate in the post-sort coordinate recording area for the a-th area and a vector extending from the i-th coordinate to the (i+1)th coordinate is calculated (step S209).
Then, θ and the turning movement cost conversion constant Kc are multiplied to calculate the linear movement cost Cc (step S210), and the linear movement cost Cc is added to the total cost array CtHorizontal[a] (step S211), after which the process returns to step S203.
If the answer is No in step S207, set a to a+1 (step S212), and then
It is determined whether the value of a exceeds the upper limit amax of the number of areas (step S213).
If the answer is No in step S213, the process returns to step S202, and if the answer is Yes in step S213, the movement cost calculation process (phase 11) is terminated and the process proceeds to the alternative route creation process (phases 12 to 16).
The straight movement cost conversion constant Ks and the turning movement cost conversion constant Kc are constants for converting the units of length and angle obtained from the XY coordinate information into dimensionless quantities.
In addition, the straight-line performance and cornering performance vary depending on the individual moving body 1, such as the distance between the left and right tires of the moving body 1 and the upper limit of centrifugal force that can be applied.
Therefore, the straight movement cost conversion constant Ks and the turning movement cost conversion constant Kc are set according to the difference in units obtained from the XY coordinate information, the individual differences (differences in performance) of the moving body 1, and the like.

The computer performs the alternative route creation process (phase 12 to phase 16) as shown in the flowchart of FIG. 23 in accordance with the procedure of the alternative route creation process program.
First, the straight lines S, S... parallel to the X-axis defined in the equally spaced straight line path creation process (phase 7) are replaced with straight lines perpendicular to the X-axis, i.e., parallel to the Y-axis, and this is set as phase 12 (step S230).
That is, phase 12 is a process in which a vertical line creating means creates a plurality of vertical lines parallel to the Y axis that divide the movement target area at equal intervals along the X axis.
Next, in the intersection coordinate extraction process (phase 8), the movement direction of the straight line is set perpendicular to the X-axis, and this is set as phase 13 (step S240).
Furthermore, the intersection coordinate extraction process for each area (phase 9) is executed as is, and this is set as phase 14 (step S250).
That is, phases 13 and 14 are processes in which the second intersection recognition means recognizes the intersections between the divided area boundary lines and the vertical lines.
Next, in the process of creating a zigzag movement route within the divided area (phase 10), the X-axis coordinates of the processing part of the conditional branch are replaced with Y-axis coordinates, and the Y-axis coordinates are replaced with X-axis coordinates. At this time, the results are saved in a recording file different from that of phase 10. This is called phase 15 (step S260).
That is, phase 15 is a process in which the second route creation means creates a zigzag second route for each divided area that proceeds along the X-axis formed by connecting the intersections on the boundaries of each divided area with vertical lines.
Finally, the total cost array CtHorizontal in the movement cost calculation process (phase 11) is replaced with the total cost array CtVertical, and the process is executed. At this time, the result is saved in a record file different from that in phase 11. The above is called phase 16 (step S270).
That is, phase 16 is a process in which the second movement efficiency calculation means calculates the movement efficiency when moving along the second route for each divided area.
Then, the process proceeds to route selection processing (phase 17).

In the route selection process (phase 17), the computer follows the procedures of the route selection process program to compare the travel efficiency when traveling along a first route and a second route within the same divided area, and selects the route with the better travel efficiency from the first route and the second route as the planned travel route within the divided area.

The computer performs a route selection process (phase 17) as shown in the flowchart of FIG. 24 in accordance with the procedure of the route selection process program.
First, variables are initialized, that is, the area number management variable a is set to 1 (step S281).
In the route selection process, the computer performs the process using storage means such as an area number management variable register, a file that records the total cost CtHorizontal[a] of the first route for each area, and a file that records the total cost CtVertical[a] of the second route for each area.
Next, the total cost CtHorizontal[a] of horizontal movement (when the first route is selected) in area a is compared with the total cost CtVertical[a] of vertical movement (when the second route is selected) (step S282).
If it is determined in step S282 that the total cost CtHorizontal[a] is lower, the sorted intersection coordinate record file for area number a created in phase 10 is made active (step S283). That is, in the area (divided area) a, the first route is selected as the planned travel route within the area (divided area) a.
In step S282, if it is determined that the total cost CtVertical[a] is lower or that the total cost CtVertical[a] and the total cost CtHorizontal[a] are equal, the sorted intersection coordinate record file for area number a created in phase 15 is made active (step S286). That is, in the area (divided area) a, the second route is selected as the planned travel route within the area (divided area) a.
After step S283 or step S286, a is set to a+1 (step S284), and it is determined whether or not the value of a has exceeded the upper limit amax of the number of areas (step S284).
If the answer is No in step S284, the process returns to step S282, whereas if the answer is Yes in step S284, the route selection process is terminated and the process proceeds to the process of creating a planned movement route between divided areas (phase 18).

In the inter-divided area planned movement route creation process (phase 18), the computer generates an inter-divided area planned movement route, which is a planned movement route from the nth divided area E to the n+1th divided area E, in accordance with the procedures of an intra-divided area zigzag movement planned route creation process program, as shown in Fig. 12. First, by the inter-divided area straight line movement planned route creation process, an inter-divided area straight line movement planned route I is created that connects in a straight line the planned movement end point (coordinate) 2e of the previous divided area (area) and the planned movement start point (coordinate) 2s of the subsequent divided area (area).
In other words, a planned straight-line movement route I between divided areas is created, which connects in a straight line the coordinate position of the intersection recorded at the end of the sorted intersection coordinate recording file for each nth divided area and the coordinate position of the intersection recorded at the beginning of the sorted intersection coordinate recording file for each n+1th divided area.
However, if connecting the planned end point (coordinate) 2e and the planned start point (coordinate) 2s of the movement in a straight line would result in contact (collision) with pillar B, a detour route is generated by a process for creating a detour route between divided areas using an arbitrary route search algorithm.

The computer performs a process (phase 18) of creating a planned route between divided areas as shown in the flowchart of FIG. 25, in accordance with the procedure of the program for creating a planned route between divided areas.
First, variables are initialized: the area number management variable a is set to 1, and the destination area management variable i is set to 1 (step S161).
In the process of creating a planned route for movement between divided areas, the computer performs the process using storage means such as an area number management variable register, a destination area management variable register, a sorted intersection coordinate recording file for each area, a route search cost calculation array file, and a route recording file for each area.
Next, it is determined whether the value of a exceeds the upper limit of the number of areas (step S162), and if the upper limit is not exceeded, it is determined whether the a-th area is a valid area (step S163), and if the a-th area is a valid area, it is determined whether the (a+i)th area is a valid area (step S164).
If it is determined in step S164 that the a+i-th area is a valid area, it is determined whether a straight line connecting the last coordinate in the sorted intersection coordinate recording file for the a-th area and the first coordinate in the sorted intersection coordinate recording file for the a+i-th area will contact an exterior wall or a pillar (step S165). That is, it is determined whether a straight line connecting the planned movement end point e of the smaller numbered area and the planned movement start point s of the larger numbered area will contact an exterior wall or a pillar.
If the answer is Yes in step S165 (if it is determined that the straight line comes into contact with an exterior wall or a pillar), the process proceeds to path search algorithm processing.
In the route search algorithm processing, first, the last coordinate in the sorted intersection coordinate recording file for the a-th area, i.e., the intersection coordinate position which is the planned end point e of movement of the a-th divided area (the starting point in the route search algorithm) is set as the current position (step S166).
Next, the cost calculation arrays of the route search algorithm are initialized, that is, cost C1[Xmax][Ymax]←[0,0,0,...] and cost C2[Xmax][Ymax]←[0,0,0,...] are initialized (step S167).
First, calculate the distance between the starting point and the eight surrounding directions (up, down, left, right, etc.) from the current position. For example, look up C1 around the position for which you want to find the cost, and add +1 to the smallest C1 (however, ignore C1 that has not changed since initialization). The calculated cost is assigned to C1 of the array number corresponding to that position (step S168A).
Next, the estimated distance from the current position to the first intersection coordinate (the goal point in the route search algorithm) in the sorted intersection coordinate record file for the a+ith area is calculated from the eight surrounding directions (up, down, left, right, etc.) For example, the straight-line distance between the position for which the cost is to be calculated and the goal is calculated, and the calculated cost is substituted for C2 of the array number corresponding to that position (step S168B).
A calculation completion flag is set for each of the eight directions surrounding the current position, up, down, left, right, and so on (step S169).
Among the coordinates for which the cost calculation completion flag is set, it is determined whether there is a location (coordinate) that has no exterior walls or pillars and has the lowest total cost (C1[*][**] + C2[*][**]) (step S170).
If no corresponding coordinates are found in step S170, an error is determined and the process ends.
In step S170, if there is only one corresponding coordinate, the process moves to that coordinate position and sets an arrival flag for that coordinate (step S171).
Also, in step S170, if there are multiple corresponding coordinates, one of the coordinates with the same value is selected according to a predetermined priority order, and then the process proceeds to step S174. The predetermined priority order is the one with the shortest estimated distance to the goal > the one with the longest distance from the start > the one closest to the origin coordinates (step S174). Then, the process proceeds to step S171.
Then, it is determined whether or not the first coordinate of the sorted intersection coordinate recording file for the a+ith area has been reached (step S172).
If it is determined that the first coordinate in the sorted intersection coordinate record file for the a+ith area has been reached (YES in step S172), it is determined whether or not there is a location with an reached flag and the highest cost among the eight surrounding directions (up, down, left, right, and so on) from the current position (step S173). That is, in step S173, a process is performed to return to the start point, and the history of the movement trajectory is searched.
If no corresponding coordinates are found in step S173, it is determined that an error has occurred and the process ends.
In step S173, if there is only one corresponding coordinate, the process moves to the coordinate with the highest cost, and a route determination flag is set for the destination coordinate (step S173A).
Then, it is determined whether or not the last coordinate in the a-th sorted intersection coordinate recording file has been reached (step S174).
Also, in step S173, if there are multiple corresponding coordinates, the process moves to the one with the closest physical distance (Euclidean distance) to the start among the coordinates with the same value, and at this time, a route determination flag is set for the destination coordinates (step S173B).Then, the process proceeds to step S174.
In step S174, if it is determined that the last coordinate in the sorted intersection coordinate recording file for the a-th area has been reached (YES in step S174), the recorded right movement trajectory is reversed and this is registered in the route recording file as the route of movement after the a-th area search (planned inter-division movement route I) (step S175).Then, the process proceeds to step S176.
If the answer is No in step S165 (if it is determined that the straight line does not come into contact with an exterior wall or a pillar), a straight line connecting the last coordinate in the sorted intersection coordinate recording file for the a-th area to the first coordinate in the sorted intersection coordinate recording file for the (a+i)th area is registered in the route recording file as the route for movement after searching the a-th area (step S178), and then the process proceeds to step S176, where a is updated to a+i and i to 1, and the process returns to step S162.
If it is determined in step S163 that the a-th area is not a valid area, the process proceeds to step S176, where a is updated to a+i and i to 1, and the process returns to step S162.
If it is determined in step S164 that the a+i-th area is not a valid area, i is set to i+1 (step S179), and then it is determined whether the value of a+i exceeds the upper limit of the number of areas (step S180). If it is determined in step S180 that the value of a+i does not exceed the upper limit of the number of areas, the process returns to step S164, and if it is determined in step S180 that the value of a+i exceeds the upper limit of the number of areas, the process of creating a planned route between divided areas (phase 11) is terminated.
If it is determined in step S162 that the value of a exceeds the upper limit of the number of areas, the process of creating a planned inter-divided area movement route (phase 11) is terminated.

According to the process of creating a planned movement route between divided areas (phase 18), a planned movement route between divided areas as shown in FIG. 12, for example, is created.
That is, for example, the end intersection coordinates of the a-th divided area are connected to the start intersection coordinates of the a+i-th divided area to generate a planned movement route I between divided areas a and a+i. In FIG. 12 , the arrow line 23 (I) is a planned movement route between divided areas connecting the planned movement end point (intersection coordinates) 2e of divided area 2 and the planned movement start point (intersection coordinates) 3s of divided area 3, the arrow line 34 (I) is a planned movement route between divided areas connecting the planned movement end point 3e of divided area 3 and the planned movement start point 4s of divided area 4, the arrow line 45 (I) is a planned movement route between divided areas connecting the planned movement end point 4e of divided area 4 and the planned movement start point 5s of divided area 5, and the arrow line 56 (I) is a planned movement route between divided areas connecting the planned movement end point 5e of divided area 5 and the planned movement start point 6s of divided area 6.
In addition, the straight arrow line 68 (I) is a planned movement route between divided areas connecting the planned end point 6e of movement in divided area 6 and the planned start point 8s of movement in divided area 8, the straight arrow line 89 (I) is a planned movement route between divided areas connecting the planned end point 8e of movement in divided area 8 and the planned start point 9s of movement in divided area 9, the straight arrow line 911 (I) is a planned movement route between divided areas connecting the planned end point 9e of movement in divided area 9 and the planned start point 11s of movement in area 11, and the straight line 1113 (I) that bypasses the pillar 12 is a planned movement route between divided areas connecting the planned end point 11e of movement in divided area 11 and the planned start point 12s of movement in divided area 13, and is a planned movement route between divided areas searched for by the route search algorithm processing.
In addition, arrow line 1314 (I) is a planned inter-divided area movement route connecting planned end point 13e of movement in divided area 13 and planned start point 14s of movement in divided area 14, arrow line 1415 (I) is a planned inter-divided area movement route connecting planned end point 14e of movement in divided area 14 and planned start point 15s of movement in divided area 15, arrow line 1517 (I) is a planned inter-divided area movement route connecting planned end point 15e of movement in divided area 15 and planned start point 17s of movement in divided area 17, and arrow line 1719 (I) is a planned inter-divided area movement route connecting planned end point 17e of movement in divided area 17 and planned start point 19s of movement in divided area 19.
In the example of Fig. 12, all the planned routes between divided areas are the planned straight-line movement routes I between divided areas determined by step S178, and there is no planned detour movement route between divided areas determined by the process of creating a detour movement route between divided areas. However, in an example in which it is determined that the planned straight-line movement route I between divided areas determined by step S178 comes into contact with an exterior wall or a pillar, a planned detour movement route between divided areas is created based on the process of creating a detour movement route between divided areas instead of the planned straight-line movement route I between divided areas. For example, if the pillar 16 in Fig. 12 is a larger pillar, there is a possibility that the arrow line 1415 (I) comes into contact with the pillar 16. In this case, a planned detour movement route between divided areas that bypasses the pillar 16 is created based on the route search algorithm process.

As a result, the mobile body 1 can move between the divided areas by following an optimal planned movement route between the divided areas that has been created in advance, and the mobile body can move between the divided areas efficiently.

The planned movement route creation device for a moving body and the planned movement route creation processing program according to the embodiment select the route with the best movement efficiency from the first route and the second route, so that it becomes possible to accurately create an efficient planned movement route for moving the moving body while avoiding obstacles in the target movement area according to the shape of each divided area.

Then, based on the planned movement route (planned movement information) created by the above-mentioned planned movement route creation device for the moving body, the moving body 1 can efficiently move independently within the target movement area A while avoiding the pillar (obstacle) B within the target movement area A.

That is, as shown in FIG. 31, a control means 50 of the moving body 1 controls the movement of the moving body 1 based on a planned movement route (planned movement information), and a movement control system for the moving body 1 can be constructed in which the movement of the moving body 1 is controlled using actual movement information of the moving body 1 (sequential position information of the moving body) and the planned movement route (planned movement information) acquired by, for example, an automatic tracking total station (hereinafter referred to as TS) as a movement information acquisition means.
In addition, as a method for controlling the movement of the moving body 1, for example, the movement control method disclosed in Patent Document 1 (JP Patent Publication No. 2020-154400), an invention by the present applicant, may be adopted.

An example of the moving body 1 will be described. In the following description, the directions of front, rear, up, down, left, and right are defined as those shown in FIG.
As shown in Figure 31, the movable body 1 comprises a base 10, a moving means 20 provided on the underside of the base 10, a target T2 such as a prism that serves as a collimator for the TS provided on the surface side of the base 10, a lifting device 40 provided on the base 10 for raising and lowering the front side of the movable body 1, a control means 50, and an imaging means (camera) not shown in the figure for photographing the floor surface F.
Furthermore, the imaging means is provided, for example, on the underside of the base 10 (the underside opposite the floor surface F) so as to extend across the left and right width of the moving body 1, and is configured so as to be able to capture an image of the floor surface F which faces the left and right width of the underside of the moving body 1 when the moving body 1 moves across the floor surface F.

The moving means 20 includes, for example, left and right front wheels 21L, 21R provided on the front lower part of the base 10, left and right rear wheels 22L, 22R provided on the rear lower part of the base 10, motors 23L, 23R as drive sources for the rear wheels 22L, 22R, and a drive control circuit not shown.
Encoders 25L, 25R are attached to the motor shafts of the motors 23L, 23R, respectively, as movement amount detection means for detecting the movement distance (movement amount) of the mobile unit 1 based on the rotation amount of the rear wheels 22L, 22R.

Target T2 is composed of a reflecting prism or the like that reflects the light emitted from TS. Target T2 is installed, for example, at a central position between the left and right sides on the front side of the upper surface of base 10.

When changing the movement direction (travel direction) of the movable body 1, the control means 50 extends the rod of the linear actuator (not shown) of the lifting device 40 from a retracted state to press the rolling body 45 against the floor surface F, thereby moving the front side of the base 10 upward and lifting the front wheels 21L, 21R of the movable body 1 off the floor surface F, and then controls the motors 23L, 23R of the left and right rear wheels 22L, 22R to rotate the left and right rear wheels 22L, 22R that are in contact with the floor surface F in opposite directions to each other.
In this case, by rotating one rear wheel in a direction that moves the moving body 1 forward and rotating the other rear wheel in a direction that moves the moving body 1 backward, the left and right rear wheels 22L, 22R and the rolling body 45 roll on the floor surface F with the rotation center line of the moving body 1 as the center of rotation, so that the moving body 1 smoothly rotates leftward or rightward on the floor surface F with the rotation center line as the center of rotation. Therefore, the horizontal orientation of the moving body 1 can be smoothly changed.

Note that, as the mobile body 1, an example has been given of a mobile body equipped with an imaging means (camera) that captures an image of a floor surface, but the mobile body may be a mobile body equipped with a specific processing function, such as a mobile body equipped with a vacuum cleaner that cleans floor surfaces, or a mobile body that does not have a specific processing function.

In the embodiment, the area outside the movement target area A, i.e., the outside wall area, is set to area 1, so that in the variable initialization of step S131 of the intersection coordinate extraction process for each area (phase 9) in FIG. 20, the variable initialization of step S141 of the zigzag movement planned route creation process within the divided area (phase 10) in FIG. 21, the variable initialization of step S201 of the movement cost process (phase 11) in FIG. 22, the variable initialization of step S281 of the route selection process (phase 17) in FIG. 24, and the variable initialization of step S161 of the movement route creation process between divided areas (phase 18) in FIG. 25, an example is shown in which the area number management variable a is set to 1 to start processing, but since area 1 is not a divided area, in the variable initialization of each of these processes, the area number management variable a may be set to 2 to start processing from area 2.

In the embodiment, a device equipped with a means for creating a planned movement route between divided areas is exemplified, but the device may not be equipped with a means for creating a planned movement route between divided areas. In other words, a movement route between divided areas may not be specifically determined.

Furthermore, in the embodiment, an example in which the movement target area is divided has been shown, but in the present invention, the device may be one in which the movement target area is not divided.
In other words, the device may create a first zigzag route that moves along the Y axis and a second zigzag route that moves along the X axis within a movable area that avoids obstacles, calculate the movement efficiency when moving along the first route and the movement efficiency when moving along the second route, and select the route with the better movement efficiency from the first route and the second route as the planned movement route within the movable area.
That is, the planned movement route creation device for a moving body according to the present invention comprises: a movement target area creation means for creating a movement target area surrounded by a movement target area boundary line that divides the movement target area based on XY coordinate information of the movement target area indicating the position of the movement target area; an obstacle area creation means for creating an obstacle area surrounded by an obstacle area boundary line that divides an obstacle present in the movement target area based on XY coordinate information indicating the position of an obstacle in the movement target area; a movable area recognition means for recognizing a movable area that avoids obstacles by using the XY coordinate information indicating the position of the movement target area and the XY coordinate information indicating the position of an obstacle in the movement target area; and a planned movement route creation means for creating a planned movement route for the moving body within the movable area, wherein the planned movement route creation means comprises a horizontal line creation means for creating a plurality of horizontal lines parallel to the X-axis that divide the movement target area at equal intervals along the Y-axis; a vertical line creation means for creating a plurality of vertical lines parallel to the Y-axis that divide the movement target area at equal intervals along the X-axis; and a predetermined area boundary line and an obstacle area boundary line and an intersection point between the horizontal line and the obstacle area boundary line. a first route creation means for creating a zigzag first route proceeding along a Y-axis formed by connecting the plurality of intersections recognized by the first intersection recognition means with horizontal straight lines within the movable area; a second route creation means for creating a zigzag second route proceeding along an X-axis formed by connecting the plurality of intersections recognized by the second intersection recognition means with vertical straight lines within the movable area; a first movement efficiency calculation means for calculating movement efficiency when moving along the first route; a second movement efficiency calculation means for calculating movement efficiency when moving along the second route; and a route selection means for comparing the movement efficiency when moving along the first route within the movable area with the movement efficiency when moving along the second route, and selecting the route having the better movement efficiency from the first route and the second route as the planned movement route within the movable area.
In this case, the planned movement route creation processing program in the present invention may be a program that causes a computer to function as the above-mentioned movement target area creation means, obstacle area creation means, movable area recognition means, horizontal line creation means, vertical line creation means, first intersection recognition means, second intersection recognition means, first route creation means, second route creation means, first movement efficiency calculation means, second movement efficiency calculation means, and route selection means.
With the above-described planned movement route creation device and planned movement route creation processing program, it becomes possible to accurately create an efficient planned movement route for moving a moving body while avoiding obstacles within a target movement area, in accordance with the shape of the target movement area.

In addition, the above describes an apparatus that creates an efficient planned movement route for moving a moving body while avoiding obstacles within a target area for movement, but in the present invention, the apparatus may be capable of accurately creating an efficient planned movement route according to the shape of a target area for movement, even within a target area for movement that does not contain obstacles.
That is, the planned movement route creation device for a moving body according to the present invention is a planned movement route creation device for a moving body that creates a planned movement route for moving a moving body within a movement target area, and includes a movement target area creation means for creating a movement target area surrounded by movement target area boundary lines that partition the movement target area based on XY coordinate information of the movement target area that indicates the position of the movement target area, and a planned movement route creation means for creating a planned movement route for the moving body within the movement target area, and the planned movement route creation means includes a horizontal line creation means for creating a plurality of horizontal lines parallel to the X axis that divide the movement target area at equal intervals along the Y axis, a vertical line creation means for creating a plurality of vertical lines parallel to the Y axis that divide the movement target area at equal intervals along the X axis, a first intersection recognition means for recognizing an intersection between the movement target area boundary line and the horizontal line, a second intersection recognition means for recognizing an intersection between the movement target area boundary line and the vertical line, and a first intersection recognition means for recognizing an intersection between the movement target area boundary line and the vertical line. The device may be a planned movement route creation device for a moving object, comprising: a first route creation means for creating a zigzag first route proceeding along a Y axis formed by connecting a plurality of intersections recognized by the point recognition means with horizontal straight lines within a movement target area; a second route creation means for creating a zigzag second route proceeding along an X axis formed by connecting a plurality of intersections recognized by the second intersection recognition means with vertical straight lines within the movement target area; a first movement efficiency calculation means for calculating movement efficiency when moving along the first route; a second movement efficiency calculation means for calculating movement efficiency when moving along the second route; and a route selection means for comparing the movement efficiency when moving along the first route within the movement target area with the movement efficiency when moving along the second route, and selecting the route having the better movement efficiency from the first route and the second route as the planned movement route within the movement target area.
In this case, the planned movement route creation processing program in the present invention may be a program that causes a computer to function as the above-mentioned movement target area creation means, horizontal line creation means, vertical line creation means, first intersection recognition means, second intersection recognition means, first route creation means, second route creation means, first movement efficiency calculation means, second movement efficiency calculation means, and route selection means.
The above-described planned travel route planning device and planned travel route planning processing program also enable accurate creation of an efficient planned travel route in accordance with the shape of a target travel area, which is the desired purpose.

Furthermore, in each embodiment, an example has been shown in which the floor surface inside a building is moved as the target area of movement, but the target area of movement may be the surface of a road, an open space, or the like outside the building.
Furthermore, obstacle B may be an obstacle other than a pillar, such as a partition wall, fixed equipment, heavy objects, etc.
Furthermore, the XY coordinate information of the target area to be moved, which indicates the position of the target area to be moved, and the XY coordinate information of the obstacle to be moved do not have to be XY coordinate information of corners, but may be any XY coordinate information that can confirm the position of the target area to be moved or the position of the obstacle.

In the above, an example was given in which a TS (total station) with an automatic tracking function was used as a means for acquiring actual movement information of a moving body in a moving body movement control system and transmitting it to the moving body, but the movement information acquisition means may be means other than a TS, for example, a moving body self-position recognition system such as a GPS or a laser positioning system.

1 Moving object, A Moving target area, B Pillar (obstacle),
C, M, N, Q: boundary lines (first, second, third boundary lines), E: divided area,
H: Zigzag movement planned route within the divided area (first route, second route),
I Planned route for travel between divided areas.

Claims (5)

A planned movement route creation device for a moving object that creates a planned movement route for moving the moving object while avoiding pillars in a movement target area,
a movement target area creating means for creating a movement target area surrounded by a movement target area boundary line that divides the movement target area based on XY coordinate information of the movement target area indicating the position of the movement target area;
a pillar region creating means for creating a pillar region surrounded by a pillar region boundary line that divides the pillars existing within the movement target region based on XY coordinate information indicating the positions of the corners of the pillars within the movement target region;
a movable area dividing means for dividing a movable area avoiding the pillars into a plurality of divided areas using XY coordinate information indicating the position of the movement target area and XY coordinate information indicating the positions of the corners of the pillars within the movement target area;
a division area planned movement route creation means for creating a planned movement route of a moving object within each of the plurality of division areas;
Equipped with
The movable area dividing means
a divided area creating means for creating a first boundary line connecting pillars to each other, a second boundary line connecting the pillars to the movement target area boundary line, and a third boundary line connecting the pillars to the first boundary line or the second boundary line, and dividing the movement target area with these boundaries to create a divided area surrounded by divided area boundary lines formed by these boundaries, the pillar area boundary line, and the movement target area boundary line;
a divided area recognition means for recognizing each of the plurality of divided areas by assigning identification information to each of the plurality of divided areas and each of the pillar areas;
Equipped with
The division area movement planned route creation means includes:
a horizontal line creating means for creating a plurality of horizontal lines parallel to an X axis that divides the movement target area at equal intervals along a Y axis;
a vertical line creating means for creating a plurality of vertical lines parallel to a Y axis that divides the movement target area at equal intervals along an X axis;
a first intersection recognition means for recognizing an intersection between a divided area boundary line and a horizontal line;
a second intersection recognition means for recognizing an intersection between a divided area boundary line and a vertical line;
a first route creation means for creating a zigzag first route for each divided area proceeding along a Y axis formed by connecting intersections on the boundaries of each divided area with horizontal straight lines;
a second route creation means for creating a zigzag second route for each divided area that proceeds along an X-axis formed by connecting intersections on the boundaries of each divided area with vertical straight lines;
a first movement efficiency calculation means for calculating a movement efficiency when moving along a first route for each divided area;
a second movement efficiency calculation means for calculating a movement efficiency when moving along a second route for each divided area;
a route selection means for comparing a travel efficiency when moving along a first route and a travel efficiency when moving along a second route within the same divided area, and selecting the route having better travel efficiency from the first route and the second route as a planned travel route within the divided area;
A planned movement route creation device for a moving object, comprising: The division area creation means includes:
a pillar grouping means for grouping a plurality of pillars existing within a movement target area into groups of pillars having similar X-coordinate information of their centers of gravity and pillars having similar Y-coordinate information of their centers of gravity ;
a column corner recognition means for recognizing the column corners by providing identification information to each of a plurality of corners of each column ;
a first connection line creating means for creating a first connection line as a first boundary line connecting a corner of one column and a corner of another column grouped together based on the X-coordinate information of the center of gravity of the columns being similar, and a first connection line as a first boundary line connecting a corner of one column and a corner of another column grouped together based on the Y-coordinate information of the center of gravity of the columns being similar;
a second connection line creating means for creating a second connection line as a second boundary line connecting a corner of the pillar to which the first connection line is not connected and the movement target area boundary line;
a third connection line creating means for creating a third connection line as a third boundary line connecting a corner of the column to which the first connection line and the second connection line are not connected and the already created first connection line or second connection line;
2. The device for generating a planned movement route for a moving body according to claim 1, further comprising: The device for creating a planned movement route for a moving body according to claim 1 or 2, characterized in that it is provided with a division area inter-division area planned movement route creation means for creating a planned movement route for a moving body between division areas. The inter-division area movement planned route creation means includes:
an inter-divided area straight line planned movement route creation means for creating an inter-divided area planned movement route by connecting an end point of an intra-divided area planned movement route of one divided area with a straight line to a start point of an intra-divided area planned movement route of the other divided area;
an inter-divided area detour planned movement route creation means for creating an inter-divided area detour planned movement route which is an inter-divided area planned movement route that does not come into contact with the movement target area boundary line or the pillar area boundary line when the inter-divided area straight line planned movement route created by the inter-divided area straight line planned movement route creation means comes into contact with the movement target area boundary line or the pillar area boundary line;
4. The device for creating a planned movement route for a moving body according to claim 3, further comprising: A program for creating a planned movement route for a moving object, the program creating a planned movement route for moving the moving object while avoiding pillars in a target movement area,
Computer,
a movement target area creating means for creating a movement target area surrounded by a movement target area boundary line that divides the movement target area based on XY coordinate information of the movement target area indicating the position of the movement target area;
a pillar region creating means for creating a pillar region surrounded by a pillar region boundary line that divides pillars existing within the movement target region based on XY coordinate information indicating the position of the pillar within the movement target region;
a divided area creating means for creating a first boundary line connecting pillars to each other, a second boundary line connecting the pillars to the movement target area boundary line, and a third boundary line connecting the pillars to the first boundary line or the second boundary line, and dividing the movement target area with these boundaries to create a divided area surrounded by divided area boundary lines formed by these boundaries, the pillar area boundary line, and the movement target area boundary line;
a divided area recognition means for recognizing each of the plurality of divided areas by assigning identification information to each of the plurality of divided areas and each of the pillar areas;
a horizontal line creating means for creating a plurality of horizontal lines parallel to the X-axis which divide the movement target area at equal intervals along the Y-axis;
a vertical line creating means for creating a plurality of vertical lines parallel to a Y axis which divide the movement target area at equal intervals along an X axis;
a first intersection recognition means for recognizing an intersection between a divided area boundary line and a horizontal straight line;
a second intersection recognition means for recognizing an intersection between a divided area boundary line and a vertical line;
a first route creation means for creating a zigzag first route for each divided area proceeding along a Y axis formed by connecting intersections on the boundaries of each divided area with horizontal straight lines;
a second route creation means for creating a zigzag second route for each divided area proceeding along an X-axis formed by connecting intersections on the boundaries of each divided area with vertical straight lines;
a route selection means for comparing a travel efficiency when moving along a first route and a travel efficiency when moving along a second route within the same divided area, and selecting the route having better travel efficiency from the first route and the second route as a planned travel route within the divided area;
A program for creating a planned movement route for a moving object to function as the above.

Images