JP7722948B2 - Tour route creation device - Google Patents

Description

The present invention relates to a travel route creation device for creating a travel route for a mobile object to travel through multiple target areas.

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 movement schedule information with the actual movement information of the mobile object acquired by a movement information acquisition means (see Patent Document 1).

Japanese Patent Application Laid-Open No. 2020-154400

The above-mentioned method for controlling the movement of a moving body does not disclose how to create a circular route for efficiently moving the moving body between multiple target areas when there are multiple target areas for movement, and there was a problem in that there was a need to develop a circular route creation device for creating such a circular route.
In view of the above-mentioned problems, the present invention provides a travel route creation device capable of creating an efficient travel route for a mobile object to travel through a plurality of target travel areas.

The traveling route creation device according to the present invention is a traveling route creation device for recognizing position information of a plurality of movement target areas and creating a traveling route for a mobile body to travel around the plurality of movement target areas, and comprises: a traveling loop creation means for creating a traveling loop that goes around each of the movement target areas; a movement cost calculation means for calculating the movement cost when the mobile body moves along the route of the created traveling loop; and a traveling route creation means for deleting the route between the movement target areas that forms the created traveling loop and creating a traveling route that goes around each of the movement target areas, with the traveling target area to which the route end of the deleted route between the movement target areas was connected as the start area of the traveling route and the traveling target area to which the route start end of the deleted route between the movement target areas was connected as the goal area of the traveling route, and the traveling loop creation means for creating a traveling loop by setting traveling information for each of the movement target areas and a subsequent generation traveling route creation means for creating a traveling route by setting traveling information for each of the movement target areas. and a loop creation means, wherein the circulatory route creation means comprises an initial generation circulatory route creation means and a later generation circulatory route creation means, wherein the initial generation circulatory loop creation means creates a plurality of circulatory loops, wherein the initial generation circulatory route creation means changes the circulatory information for each movement target area for each of the plurality of initial generation circulatory loops created by the initial generation circulatory loop creation means to create a plurality of initial generation circulatory routes, wherein the later generation circulatory loop creation means extracts some initial generation circulatory routes with low movement costs from the plurality of initial generation circulatory routes and creates a later generation circulatory loop using the circulatory information of the extracted initial generation circulatory routes, and wherein the later generation circulatory route creation means changes the circulatory information for each movement target area for each later generation circulatory loop created by the later generation circulatory loop creation means to create a later generation circulatory route, and the circulatory information is combined information made up of information on the circulatory pattern within the own movement target area set for each movement target area and information on the next movement target area to move to.
Further, the number of generations of the subsequent generation is plural, and the current subsequent generation circular route creation means changes the circular information for each movement target area for each previous subsequent generation circular loop created by the previous subsequent generation circular loop creation means to create the current subsequent generation circular route, and the subsequent generation circular route creation means of the final generation determines the circular route with the smallest movement cost as the circular route from among the multiple circular routes created as the final generation.
The current next-generation circular route creation means defines one or more circular routes with small travel costs from among the previous plurality of next-generation circular loops created by the previous next-generation circular loop creation means as parents, and creates the current next-generation circular route by inheriting the circular information of the parent circular route.
Furthermore, the current next generation patrol route creation means is characterized in that, if, at the stage of creating the current next generation patrol route, there remain two or more movement target areas for which patrol information has not yet been set and the information of the next movement target area, which is the patrol information to be set for the movement target area for which patrol information has not yet been set, cannot be inherited from the parent, the current next generation patrol route creation means arbitrarily selects the next movement target area to be set for the movement target area for which patrol information has not yet been set from among the movement target areas for which patrol information has not yet been set.
In addition, cases where the information of the next moving target area, which is the patrol information to be set for a moving target area for which patrol information has not yet been set, cannot be inherited from the parent are characterized by cases where the information of the next moving target area, which is the patrol information of the parent that is to be inherited by a moving target area for which patrol information has not yet been set, is the moving target area for which patrol information was first set when creating the current next-generation patrol route, and cases where the information of the next moving target area, which is the patrol information of the parent that is to be inherited by a moving target area for which patrol information has not yet been set, has already been used in creating the current next-generation patrol route.
Furthermore, when the current next-generation circular route creation means determines that there is only one remaining target area for which no circular information has yet been set at the stage of creating the current next-generation circular route, it sets the information of the next target area for which circular information is set, which is the circular information of the one remaining target area for which circular information has first been set, as the target area for which circular information has first been set when creating the current next-generation circular route.
The current next-generation circulatory route creation means also includes a movement target area inter-route modification processing means for extracting a circulatory route with a small movement cost from among the previous plurality of next-generation circulatory routes created by the previous next-generation circulatory route creation means, and modifying the route between the movement target areas of the circulatory loop that was the basis for creating the extracted circulatory route, and the movement target area inter-route modification processing means includes a first step of arbitrarily selecting a different first movement target area and a second movement target area from among the movement target areas of the circulatory loop, a second step of recording information of the next movement target area that is set as circulatory information of the second movement target area as reserved information, a third step of searching for a movement target area that has information of the next movement target area that is set as circulatory information of the second movement target area as circulatory information, and determining whether or not the movement target area exists, and a third step of determining whether or not the movement target area exists based on the circulatory information of the first movement target area. The method is characterized by comprising a fourth step of setting a second target area for movement as information on the next area to be set; a fifth step of inverting the circulating pattern set in the circulating information of the second target area for movement if the processing of the fourth step is not the first time; a sixth step of changing the first target area for movement to the second target area for movement after the fourth step or the fifth step if the judgment result in the third step is positive, changing the second target area for movement to the target area searched in the third step, and then returning to the processing of the third step; and a seventh step of setting the pending information as the next target area for movement as the circulating information of the second target area for movement after the fourth step or the fifth step if the judgment result in the third step is negative, and inverting the circulating pattern set in the circulating information of the second target area for movement.
The current next-generation circular route creation means also includes a circular pattern modification processing means that extracts a circular route with a low travel cost from the previous plurality of next-generation circular routes created by the previous next-generation circular route creation means, and modifies the circular pattern within the movement target area of the circular loop that was the basis for creating the extracted circular route, and the circular pattern modification processing means randomly selects one movement target area from each movement target area of the circular loop, and modifies the information of the circular pattern, which is the circular information of the movement target area.
Furthermore, a travel route creation device according to the present invention is a travel route creation device for recognizing position information of a plurality of movement target areas and creating a travel route for a mobile body to travel around the plurality of movement target areas, and includes: a travel loop creation means for creating a travel loop that goes around each of the movement target areas; a travel cost calculation means for calculating the travel cost when a mobile body travels along the route of the created travel loop; and a travel route that goes around each of the movement target areas by deleting the inter-movement target area route with the highest travel cost from among the inter-movement target area routes that form the created travel loop, and creating a travel route that goes around each of the movement target areas, with the movement target area that connected the route end of the deleted inter-movement target area route as the start area of the travel route, and the movement target area that connected the route start end of the deleted inter-movement target area route as the goal area of the travel route. and a circular route creating means for creating a circular loop by setting circular information for each movement target area, the circular loop creating means comprising initial circular loop creating means for creating an initial circular loop by setting circular information for each movement target area, and circular loop updating means for creating a circular loop by changing the circular information of the initial circular loop, the circular route creating means comprising determination means for comparing the movement cost of a current circular route created based on the current circular loop created by the circular loop updating means with the movement cost of a previous circular route created based on the previous circular loop created by the circular loop updating means, and leaving the circular route with the smaller movement cost, and the circular information is combined information made up of information on a circular pattern within the current movement target area, which is set for each movement target area, and information on the next movement target area.
The movement target area is an area partitioned based on XY coordinate information, and the cyclic pattern within the movement target area is an X-direction cyclic pattern that zigzags along the X-axis, or a Y-direction cyclic pattern that zigzags along the Y-axis. The X-direction cyclic pattern is a first pattern in which the movement start position is the position of the minimum X-coordinate and the maximum Y-coordinate, a second pattern in which the movement start position is the position of the minimum X-coordinate and the minimum Y-coordinate, a third pattern in which the movement start position is the position of the maximum X-coordinate and the maximum Y-coordinate, and a fourth pattern in which the movement start position is the position of the maximum X-coordinate and the minimum Y-coordinate. The Y-direction cyclic pattern is a fifth pattern in which the movement start position is the position of the minimum X-coordinate and the maximum Y-coordinate, a sixth pattern in which the movement start position is the position of the maximum X-coordinate and the maximum Y-coordinate, a seventh pattern in which the movement start position is the position of the minimum X-coordinate and the minimum Y-coordinate, and an eighth pattern in which the movement start position is the position of the maximum X-coordinate and the minimum Y-coordinate.
According to the present invention, it is possible to provide a travel route creation device that can create an efficient travel route for a mobile object to travel through a plurality of target travel areas.

FIG. 10 is an explanatory diagram of the process of creating a movement target area and an obstacle area (phase 1). FIG. 10 is an explanatory diagram of the obstacle grouping process (phase 2). FIG. 10 is an explanatory diagram of obstacle angle recognition processing (phase 3). FIG. 10 is an explanatory diagram of the obstacle boundary line creation process (phase 4). FIG. 10 is an explanatory diagram of the division area division process (phase 5). FIG. 10 is an explanatory diagram of the division area division process (phase 5). FIG. 10 is an explanatory diagram of the divided area recognition process (phase 6). FIG. 10 is an explanatory diagram of the divided area recognition process (phase 6). FIG. 10 is an explanatory diagram of the equally spaced straight line path creation process (phase 7). FIG. 10 is an explanatory diagram of the intersection coordinate extraction process (phase 8). 10 is an explanatory diagram of the process of extracting intersection coordinates for each area (phase 9) and the process of creating a planned zigzag movement route within a divided area (phase 10). FIG. 10 is an explanatory diagram of a process for creating a zigzag movement route within a divided area (phase 10) and a process for creating a movement route between divided areas (phase 11). FIG. 10 is a flowchart showing the procedure of a process (phase 1) for creating a movement target area and an obstacle area. 10 is a flowchart showing the procedure of obstacle grouping processing (phase 2). 10 is a flowchart showing the procedure of obstacle angle recognition processing (phase 3). 10 is a flowchart showing the procedure of an obstacle boundary line creation process (phase 4); 10 is a flowchart showing the procedure of the division area division process (phase 5). 10 is a flowchart showing the procedure of a divided area recognition process (phase 6). 10 is a flowchart showing the procedure of the equally spaced straight line path creation process (phase 7) and the intersection coordinate extraction process (phase 8). 10 is a flowchart showing the procedure of the area-by-area intersection coordinate extraction process (phase 9); 10 is a flowchart showing the steps of a process (phase 10) for creating a planned zigzag movement route within a divided area. 11 is a flowchart showing the procedure of a movement cost calculation process (phase 11). 10 is a flowchart showing the procedure of another route creation processing (phases 12 to 16). 10 is a flowchart showing the procedure of a route selection process (phase 17). 10 is a flowchart showing the steps of a process (phase 18) for creating a planned travel route between divided areas. FIG. 10 is an explanatory diagram of the divided area recognition process (phase 6). FIG. 10 is an explanatory diagram of the divided area recognition process (phase 6). FIG. 10 is an explanatory diagram of the divided area recognition process (phase 6). 10 is an explanatory diagram of the process of extracting intersection coordinates for each area (phase 9) and the process of creating a planned zigzag movement route within a divided area (phase 10). FIG. FIG. 10 is an explanatory diagram of the process of creating a planned zigzag movement route within a divided area (phase 10). FIG. 1 is a perspective view showing an example of a moving body. FIG. 10 is a diagram illustrating a circulating pattern. 1 is a schematic flowchart of a GA process. 10 is a flowchart showing a process for creating an initial generation individual. 10 is a flowchart showing an individual evaluation process. 10 is a flowchart showing a crossover process. 1 is a flowchart showing a mutation process. FIG. 10 is a diagram showing an initial cyclic information array and an initial cyclic loop. An example of a cyclic information array is shown below. An illustration of an individual carrying lethal genetic information. An illustration of an individual carrying lethal genetic information. An explanatory diagram of basic crossover processing. FIG. 10 is an explanatory diagram of exceptional crossover processing. FIG. 10 is an explanatory diagram of exceptional crossover processing. FIG. 10 is an explanatory diagram of exceptional crossover processing. An illustration of the mutation process. An illustration of the mutation process. An illustration of the mutation process. An illustration of the mutation process. An illustration of the mutation process. An illustration of the mutation process. An illustration of the mutation process.

Prerequisite Technology First, before explaining an embodiment of the travel route creation device of the present invention, a planned travel route creation device, which is a prerequisite device (prerequisite technology) for the travel route creation device of the present invention, will be explained based on paragraphs 0007 to 0053 and Figures 1 to 31.
The planned movement route creation device, which is the prerequisite device for the patrol route creation device of the present invention, 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., a planned obstacle-avoiding movement route for a moving body moving within the target movement area.
The planned movement route creation device for a moving body includes a movement target area creation means, an obstacle area creation means, a movable area division means, an intra-divided area planned movement route creation means, and an inter-divided area planned movement route creation means.
In other words, 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) that indicates 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 demarcate 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 is a means for dividing 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 position of obstacles within the target area of movement.
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 means for creating a planned movement route of a moving object between 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 obstacle to the movement target area boundary line, and a third boundary line connecting the obstacle to the first boundary line or the second boundary line, and by dividing the movement target area with these boundary lines, creates a divided area surrounded by divided area boundary lines formed by these boundary lines, the obstacle area boundary line, and the movement target area boundary line.
The divided area recognition means is 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 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, and a route selection means.
The horizontal line creating means is 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.
The vertical line creating means is 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.
The first intersection recognition means is a means for recognizing an intersection between a divided area boundary line and a horizontal line.
The second intersection recognition means is a means for recognizing an intersection between a divided area boundary line and a vertical line.
The first route creation means is means for creating a zigzag first route for each divided area that proceeds along the Y axis formed by connecting intersections on the boundaries of each divided area with horizontal straight lines.
The second route creation means is means for creating 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 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 means for comparing the travel efficiency when traveling along a first route and the travel efficiency when traveling along a second route within the same divided area, and selecting the route with 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 with similar X coordinate information and obstacles with similar Y coordinate information; obstacle angle recognizing means for recognizing the obstacle corners by assigning identification information to each of 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 another 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 another 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 by 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 by the first connection line or the second connection line that has already been created.
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 an inter-divided area planned movement route that connects the end point of the planned movement route within one divided area with the start point of the 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 that is an inter-divided area planned movement route that does not come into contact with the movement target area boundary line or obstacle 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 obstacle area boundary line.

The planned movement route creation device, which is a prerequisite device for the travel route creation device according to the present invention, including 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, are realized by control means, and the control means that executes each of the means is composed of a processing program that indicates the procedure of the 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 premise device is a program that causes the 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 planned movement route creation means between divided areas.

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 FIGS.
The obstacle grouping means executes the obstacle grouping process (phase 2) shown in FIGS.
The obstacle angle recognition means executes the obstacle angle recognition process (phase 3) shown in FIGS.
The first connection line creating means executes the obstacle boundary line creating process (phase 4) shown in FIGS.
The second connection line creating means and the third connection line creating means execute the division area dividing 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 FIGS.
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 (phase 10) of creating a planned zigzag movement route within a divided area 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 creation means executes phase 15 shown in step S260 in FIG. 23, which is a process replacing the process for creating a planned zigzag movement 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, when 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 FIGS.
The planned straight-line movement route between divided areas creation means of the planned movement route between divided areas creation means executes the planned straight-line movement route between divided areas creation process (the part other than the route search algorithm part of Figure 25), and the planned detour movement route between divided areas creation means of the planned movement route between divided areas creates the route search algorithm part of Figure 25 as the planned detour movement route between divided areas creation process.

The moving body is a moving body 1 configured to be able to move on a target surface, such as a floor surface, within a target movement area based on a planned movement route created by a planned movement route creation device (see Figure 31).
The control means is mounted on the moving body 1, for example, as shown in FIG.
Therefore, in this case, the mobile body 1 is equipped with a control means 50 that creates a planned movement route for the mobile body 1 and controls the movement of the mobile 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 mobile body 1 may be configured not by a computer mounted on the mobile body 1, but by a computer such as a personal computer separate from the mobile body 1, and the above-mentioned processing program executed by the computer. In this case, as will be described later, the computer is input with XY coordinate information of the target movement area through which the mobile body 1 will be moved and XY coordinate information of obstacles within the target movement area, causing the computer to recognize the target movement area and obstacles and create a planned movement route. Then, by inputting the created planned movement route into the control means of the mobile body 1, the control means of the mobile body 1 can move the mobile body 1 within a movable area within the target movement area based on the planned movement route.

In the planned movement route creation process, first, for example, XY coordinate information of a corner of a wall at the boundary position between a floor area and a wall as a target area A for movement indoors, and XY coordinate information of a corner of a pillar (hereinafter referred to as pillar B) as an obstacle B present in the floor area as the target area A for movement are input into a computer in advance. Then, the computer converts the input XY coordinate information into XY coordinate information on a display screen D managed by the computer and records the converted information in 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 input to the computer in advance as the XY coordinate information of the movement target area A indicating the position of the movement target area, and the XY coordinate information of the corner of pillar B is input to the computer in advance as the XY coordinate information of the movement target area A indicating the position of the pillar (obstacle) B.
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 planned movement route that has been created and displays it, for example, on a display screen D (see Figure 12).

The above-mentioned XY coordinate information is the actual XY coordinate information in the movement target area A, and the 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 managed by the computer on the display screen D can be set to a fixed spacing on the actual movement target area A based on the 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 that is 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 that is 10 cm away in the positive direction of the Y-axis direction from position a are recorded and managed by the computer as XY coordinate values a = (1, 0), b = (1, 1) with reference to the reference point O on the display screen D.
Furthermore, the XY coordinate information of the corners of the walls that define the actual area A to be moved and the XY coordinate information of each corner of each actual pillar B, B... are recorded in the memory means by inputting, for example, the distance from a reference point O set outside the actual area A 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 pillar B, B... measured using a measuring means such as a rangefinder, or by inputting the values from a blueprint or the like.
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 area A to be moved 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 axes of the display screen D.
For example, if a certain corner is located 100 cm in the positive X-axis direction from the reference point O and 100 cm in the positive Y-axis direction from the reference point O, the XY coordinate values of the corner will be recorded as (10, 10). Note that if a certain corner is located 94 cm in the positive X-axis direction from the reference point O and 96 cm in the positive Y-axis direction from the origin, the XY coordinate values of the corner will be recorded as (9, 10), for example, after rounding.

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 plurality of pillars B, B, etc. within the movement target area A on a display screen D, for example, as shown in FIG. 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 plurality 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 the XY coordinate information of the corners of the wall 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 the XY coordinate information of the corners 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 creation process program and an obstacle area creation process program.
First, data (XY coordinate values of the corners of the walls (boundaries)) is extracted from a file recording 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, thereby creating a 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 the corners with straight lines.
Next, the column number control variable is initialized, i.e., the column number control variable n is set to 1 (step S2). The column number control variable is a variable for specifying the column to be checked, and is sequentially recorded and managed in the storage means.
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 that 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 that becomes the movement target area A and the wall, a pillar angle coordinate recording file that records the XY coordinates of the corners of each pillar B, B, etc. that exist 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 that forms 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).
That is, 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 follows the procedures of the obstacle grouping process program and groups pillars B with similar X coordinate values and pillars B with similar Y coordinate values, using the center coordinate of pillar B as the reference, as shown in Figure 2. Grouping is performed by assigning numbers. Therefore, each pillar B, B, etc. is assigned a number in the X-axis direction and a number in the Y-axis direction. That is, the number 1-1 is assigned to the leftmost pillar B (1) in Figure 2, and the number 4-3 is assigned to the rightmost pillar B (5) in Figure 2. For example, the number 4-3 assigned to the rightmost pillar B (5) in Figure 2 means that 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 is performed: the pillar number management variable n is set to 0, the comparison object 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 a pole number control variable register, a comparison object control variable register, a group number variable register, and a pole 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 control variable n is set to n+1 to update the columns to be grouped (step S13). It is then determined whether the nth column (e.g., the number in parentheses of column B in Figure 2) has already been assigned an 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 Figure 2) has already been assigned an X-axis direction group number gx. In the case of Figure 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 column has not been assigned an X-axis group number gx, the n-th column is assigned an X-axis group number gx (step S15). The group number is recorded in a column group number record file that records the group number of each column.
Thereafter, it is determined whether the value of n+p matches the number of columns (step S16).
The comparison control variable p refers to the column to be compared. For example, the columns to be compared with column B(1) in FIG. 2 are columns B(2), B(3), B(4), and B(5). 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. Therefore, the maximum value of n+p matches the number of columns. 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 pillars remaining to be compared, and the pillars to be compared are updated by setting p to p+1 (step S17). 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 is calculated (step S18), and then it is determined whether the absolute value of the difference ex is equal to or less than 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 less 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 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 column to be compared, 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 group number gx, the (n+p)th column is assigned the X-axis 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 in the X coordinate between the center of gravity of the nth column and the center of gravity of the (n+p)th column is less than or equal to the reference value E, the (n+p)th column is assigned the same X-axis group number gx as that assigned to the nth column.
Also, in step S19, if the absolute value of the difference ex is not equal to or less than the reference value E (No in step S19), the process returns to step S16 and performs a comparison process (steps S17 to S19) 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 the comparison with the nth column.
In addition, for the (n+p)th column for which it is determined in step S19 that the absolute value of the difference ex of the X coordinate of the center of gravity is not equal to or less than the reference value E, an X-axis direction group number will be assigned 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 all pillars have been assigned the X-axis direction group number gx, 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, the obstacle angle recognition process (phase 3).

In the obstacle angle recognition process (phase 3), the computer recognizes the corners of pillars B by assigning numbers to 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, as shown in FIG. 3, in accordance with the procedures of the obstacle angle recognition process program.
As shown in FIG. 3, for example, numbers 1 to 4 are assigned to the corners of each of the columns 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 where a line parallel to the X axis passing through the center coordinates of the round column and a line parallel to the Y axis passing through the center coordinates of the round column intersect are regarded as corners, and numbers are assigned to the four corners, respectively.

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, i.e., 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).
If it is determined in step S34 that there is only one corner of the n-th column with the largest Y-axis coordinate value (No in step S34), the corner with the largest Y-axis coordinate value for the n-th column is assigned corner number 1 (step S35; see, for example, columns B1 and B3 in FIG. 3), and then it is determined whether there are multiple corners with the largest X-axis coordinate value for the n-th column (step S37). The corner numbers are recorded in a column corner number record file that records the corner numbers of each column.
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 nth column (Yes in step S34), the corners with the largest Y-axis coordinate value for the nth column are compared, 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, for example, 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 ). That is, among the multiple corners with the largest X-axis coordinate value, corner number 2 is assigned to the corner with the largest Y-axis coordinate value, 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, for example, 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 of the nth column with the smallest Y-axis coordinate value (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 corner number 3 (step S42; see, for example, columns B2 and B4 in FIG. 3). That is, among the multiple corners with the smallest Y-axis coordinate value, corner number 3 is assigned to the corner with the largest X-axis coordinate value, and then the process proceeds to step S43.
In step S43, if it is determined that there is one corner of the nth pillar with the smallest X-axis coordinate value (No in step S43), corner number 4 is assigned to the corner of the nth pillar with the smallest X-axis coordinate value (step S44; see, for example, pillars 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 value 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 ). That is, among the multiple corners with the smallest X-axis coordinate value, corner number 4 is assigned to the corner with the smallest Y-axis coordinate value, and then the process returns to step S32.
If it is determined in step S32 that the value of n matches the number of pillars, it is recognized that numbers have been assigned to the corners of all pillars B, B, etc., and the obstacle corner recognition process (phase 3) is terminated, and the process proceeds to the obstacle boundary line creation process (phase 4).

In the obstacle-to-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 inter-pillar boundary line (inter-obstacle boundary line (first boundary line)), as shown in FIG. 4, in accordance with the procedures of the obstacle-to-obstacle boundary line creation process program. For example, an inter-pillar 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) numbered 3-1 and pillar B(3) numbered 3-3, which belong to the same 3rd group in the X-axis direction, are connected by an inter-pillar boundary line M, pillar B(1) numbered 1-1 and pillar B(4) numbered 3-1, which belong to the same 1st group in the Y-axis direction, are connected by an inter-pillar boundary line M, and pillar B(3) numbered 3-3 and pillar B(5) numbered 4-3, which belong to the same 3rd group in the Y-axis direction, are connected by an inter-pillar boundary line M. In other words, for each pillar, the optimal pillar for connecting the boundary lines is selected, and the pillars are connected by a 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 executes the obstacle boundary line creation process (phase 4) shown in the flowchart of FIG. 16 in accordance with the procedure of the obstacle boundary line creation process program.
First, variable initialization processing 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, i.e., s is set to Null (step S53). Furthermore, n is set to n+1 (step S54), and then 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 destination candidate registration variable register, pillar corner coordinate recording file, and pillar corner number recording file.
The connection candidate registration variable s is a variable that temporarily records connection candidates.
In step S55, if no boundary line is connected to the nth pillar in the positive X-axis direction (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 pillars (No in step S56), this means that pillars remain 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 pillar and the X-axis direction group number of the n+pth pillar are the same (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 pillar is not in the positive X-axis direction as viewed from the nth pillar, the process returns to step S56.
If it is determined in step S59 that the center of gravity of the (n+p)th pillar is in the positive X-axis direction as viewed from the nth pillar, it is determined whether 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.
In step S60, if s=Null is not satisfied, 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 (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 then the process returns to step S56.
If L*>L is not satisfied in step S64, 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, the process returns to step S52. If not, 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, the boundary line M extends rightward from the second corner of pillar B(1) to connect to the fourth corner of pillar B(4)), and then the process returns to step S52.
If it is determined in step S52 that the value of n matches the number of pillars, the process of connecting to the boundary line in the positive X-axis direction is terminated, and then the process of connecting to the boundary line in the negative X-axis direction, the process of connecting to the boundary line in the positive Y-axis direction, and the process of connecting to the boundary line in the negative Y-axis direction are each performed in the same manner as the process of connecting to the boundary line in the positive X-axis direction (however, the connection to the boundary line in the X-axis direction is performed using corner number 2 and corner number 4, and the connection to the boundary line in the Y-axis direction is performed using corner number 1 and corner number 3) (step S69).
Then, when 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 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=2th 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=3th column in step S58. Columns B(1) and B(3) also do not have the same X-axis group number, so in step S57, column B(1) is compared with column B(4) as the n+p=4th column in step S58. Columns B(1) and B(4) have the same X-axis group number, so in step S59 and step S60, the distance L* between the centers of gravity of columns B(1) and B(4) is calculated, and then the number of column B(4), n+p=4, is stored as the connection destination candidate variable s. After that, in step S57, column B(1) is compared with column B(5), which is the (n+p)th column, in step S58. Since columns B(1) and B(5) do not have the same X-axis 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 by a boundary line.
4, there are no more than three columns with the same X-axis group number. However, if, for example, there is a column B(6) not shown in the figure that has the same X-axis group number as columns B(1) and B(4), then in step S63, the distance L between the centers of gravity of column B(1) and column B(6) is calculated. Then, in step S64, if the distance L between the centers of gravity of columns B(1) and B(6) is smaller than the distance L* between the centers of gravity of columns B(1) and B(4), the number of column B(6), n+p=6, is stored as the connection destination candidate variable s. Then, in step S67, the second corner of column B(1) and the fourth corner of column B(6) are connected by a boundary line in step S68.

In the divided area division process (phase 5) using the second connection line creation means and the third connection line creation means, the computer follows the procedures of the divided area division process program to create 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, and divides the movement target area A into a plurality of divided areas E, E... (see Figure 6) which are a plurality of movable areas separated by boundaries C, M, N, Q.
In other words, in the obstacle boundary line creation process (phase 4), a boundary line N (second boundary line) is created that connects the corner of pillar B that was not connected by pillar-to-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 was not connected by pillar-to-pillar boundary line M (first boundary line) to the pillar-to-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) 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 pillars remaining to be compared, so the pillar corner number control variable is initialized, i.e., the pillar corner number control variable c is set to 1 (step S73), and further, the pillar number control 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 c is not 1 in step S76, it is determined whether c is 2 (step S77).
If c is not 2 in step S77, it is determined whether c is 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, extend boundary line N in the positive Y-axis direction from corner number 1 until it touches a wall, a pillar, or a boundary line (step S82; see, for example, pillars B(1), B(2), and B(3) in FIG. 5). Then, proceed to step S80.
If c=2 in step S77, the boundary line N is extended in the positive X-axis direction from corner number 2 until it touches 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 a wall, a pillar, or a boundary line (step S84; see, for example, pillars B(1), B(2), and B(4) in FIG. 5). Then, the process proceeds to step S80.
That is, after the process of extending boundary lines from each corner number is completed (steps S82, S83, S84, S79), the column corner number management 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 processing of the next pillar to be compared.
If c=5 is not satisfied in step S81, the process returns to step S75, and the processes from step S75 to step S84 are repeated.
If the value of n matches the number of columns in step S72, the divided area classification 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, etc. 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 (areas outside the wall (areas outside the movement target area A), areas inside the pillar B (obstacle areas), 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 using a filling process, 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, etc. 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 determination and area number recording array file, an X-axis search management variable register, a Y-axis search management variable register, an area number management variable register, an X-axis fill management variable register, a Y-axis fill management variable register, a fill management file, and a fill 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 judgment and area number record 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 and the Y-axis direction search management variable register are set to 0, and all values of the X and Y coordinate positions in the fill judgment and area number record array file are maintained at 0, and the area number management variable register is set to 1, so that the area outside the movement target area A is filled with "1".
First, it is determined whether i>Xmax holds (step S92), and if i>Xmax does not hold, it is determined whether Stack[i][j]=0 holds (step S93).
In step S93, if Stack[i][j]=0, Stack[i][j] is set to -1 (step S94), resulting in the states shown in, for example, Figures 8(b), (f), 23(b), (d), 24(b), (d), (f), and 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).
Fill management refers to the management of the values of each X and Y coordinate position in a fill management file separate from the fill determination and area number record array file, so that areas that have already been assigned area numbers are not filled when the fill process is performed for each area. That is, the values of each X and Y coordinate position in the fill determination and area number record array file, Stack[i][j], are replaced with the values of each X and Y coordinate position in the fill management file, Stack[fi][fj] (see, for example, Figure 23(d)). This prevents the search for the values of each X and Y coordinate position of areas that have already been assigned area numbers, thereby speeding up the fill process.
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 the coordinate (fi+1, fj) exists, there is no wall, pillar, or boundary line between the coordinate (fi, fj) and the point, and Stack[fi+1][fj] is 0 (step S100). 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 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, no wall, pillar, or boundary line passes between the coordinate (fi, fj) and 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 Stack[fi-1][fj] is set to -1 (step S105). Thereafter, the process proceeds to step S105A, where mi is set to fi-1 (except when fi=0), and then 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 the coordinate (fi, fj+1) exists, there is no wall, pillar, or boundary line between the coordinate (fi, fj) and 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 positive 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 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, no wall, pillar, or boundary line passes between the coordinate (fi, fj) and 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), 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 the answer to step S103 is No, that is, if a wall, pillar, or boundary line passes 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 Stack[fi][fj]=-1 is not satisfied in step S98, 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 it is then 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 8(f) and 23(c) and 23(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 four directions of the a-th section are in contact with pillars (whose coordinates are known) 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=1st 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 area is determined to be 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 Stack[i][j]=0 is not satisfied in step S93, 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 (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 process of dividing the movement target area A (phases 1 to 6), and the process then moves on to the process of creating a movement route (phases 7 to 11).

The divided area recognition process (phase 6) will be described with reference to the above-mentioned step S and FIGS.
In addition, FIG. 8 shows an example in which two areas are extracted by painting 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 determination 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 8(f) and FIG. 26(c) are carried out.
8(e) and 8(f), 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 X direction or the negative Y direction, the returned coordinate position is temporarily stored as variables mi and mj in the fill management variable temporary storage register, and processing is performed.
Then, after the number a is assigned to all coordinates of any area (if YES in step S110), it is determined whether the area is an area outside the wall (area outside the area A to be moved) or an area inside the pillar, which is a divided area (steps S111, S112), and then the number of the next area is updated (step S113), and the process proceeds to fill in the next area (see Figures 8(f), (g), Figure 26(d), Figures 27(a) to (f), Figures 28(a) to (d)).
In step S113, numbers are 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, these show an example in which numbers are assigned to each area in ascending order.

Next, in the process of creating a travel route (phases 7 to 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 procedures of the equally spaced straight line path creation process program, and creates an equally spaced straight line path that will serve as the basis for a planned zigzag movement route within the divided area, which will be described later. Figure 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 line creation means for creating multiple horizontal 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 steps of the intersection coordinate extraction process program to extract the intersection coordinates G, G... of the boundary lines C, M, N, Q, and boundary line of pillar B (obstacle area boundary line) that divide each area (outside the wall area (area outside the target area A), inside the pillar area, 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 peripheries of the walls and pillars) 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 line S, the coordinates of that 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.
In step S127, if the value of m does not match the total number of boundary lines, the processes of steps S124 to S126 are repeated until the value of m matches the total number of boundary lines.
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 of steps S123 to S128 are repeated until it does.
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 intersection coordinate extraction process, the computer performs the process 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.
Furthermore, "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 candidate planned movement route in Fig. 19, straight lines S are drawn one by one in order from bottom to top in Fig. 9, and each time a straight line S is drawn, the process of recording the coordinates of the intersections between the straight line S and each boundary line 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.
Furthermore, the "lane distance" 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 "lane distance" is determined in advance to an appropriate length (for example, 10 cm).
Therefore, the coordinates of the intersections of each of the lines S, S . . . that form the basis of the planned zigzag movement route within the divided area with all of the boundary lines are all recorded in the intersection coordinate recording file.
In this case, for example, the intersection coordinate recording file records the X and Y coordinates of each intersection, with the intersections numbered in ascending order of X and Y coordinates (see the circled numbers indicating the X and Y coordinates of the intersections in FIG. 12).

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

The computer performs the area-by-area intersection coordinate extraction process (phase 9) as shown in the flowchart 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 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).
In step S133, if the value of a does not exceed the number of areas, it is determined whether the k-th 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 the exact same coordinates as those of the kth intersection have already been assigned to the intersection coordinate recording file for area a (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 S132.
If it is determined in step S135 that the coordinates identical to those of the kth intersection have already been recorded in the intersection coordinate recording file for the ath area, the process proceeds to step S137.
If it is determined in step S135 that the coordinates identical to the kth intersection are not recorded in the intersection coordinate recording file for the ath area, the coordinates of the kth intersection are recorded in the intersection coordinate recording file for the ath 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 using storage means such as an intersection number management variable register, an area number management variable register, an intersection coordinate recording file, and an intersection coordinate recording file for each area.

In the area-by-area intersection coordinate extraction process (phase 9), the intersection numbers and X and Y coordinates of each area are recorded in an area-by-area intersection coordinate recording file by determining which area each intersection is adjacent to, for example, starting with the intersection with the smallest X and Y coordinate values. In other words, the intersection coordinates are extracted for each area and recorded in the area-by-area intersection coordinate recording file (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 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 X and Y coordinates is set to k=1, and the value of k is increased by 1 for intersections 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 the area (steps S132 to S134), and an intersection coordinate recording file for each area is created (step S136).
That is, in the process of extracting intersection coordinates for each area (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) functions as a first intersection recognition means for recognizing the intersections between the boundaries C, M, N, Q and the boundaries of the pillar B that divide each area (movement target area boundaries, boundaries, obstacle area boundaries) 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 boundaries and horizontal straight lines.

In the process for creating a planned zigzag movement route within a divided area (phase 10), the computer follows the steps of the process for creating a planned zigzag movement route within a divided area program, and creates a zigzag planned zigzag movement route H within each divided area E, E, etc. by connecting adjacent coordinates G, G on a straight line S along the X axis for each divided area E, E, etc., 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 within the divided area is a route that repeatedly moves in one direction along the X-axis and then turns back in the opposite direction to the one direction along the X-axis. Note that, when a plurality of vertical straight lines that are equally spaced along the X-axis are set in the equally spaced straight line route creation process, a planned zigzag movement route within the divided area is created that repeatedly moves in one direction along the Y-axis and then turns back in the opposite direction to the one direction along the Y-axis.
Furthermore, the intersections recorded in the intersection coordinate recording file for each area are recorded with their intersection numbers recorded in a discontinuous manner. For example, in FIG. 12 , when the intersections are numbered in order from the intersection with the smallest XY coordinate value and the area to which each intersection is adjacent is determined one by one, 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 region) numbered 2 in FIG. 12 , the intersections numbered 1, 2, 6, 7, 11, 12, 16, 17, and 18 are recorded in order, as shown in FIG. 26( a). However, if the intersections were traced in the order in which they were recorded in FIG. 26( a), a sawtooth-shaped route would result. Therefore, in the process for creating a zigzag movement planned route within a divided area (phase 10), the order in which the intersections are recorded is rearranged so that the X and Y coordinates of each intersection are arranged in order from the start point to the end point of the route forming the zigzag path in the sorted intersection coordinate recording file for each area, as shown in Figure 26(b). For example, as shown in Figure 29(b), in the sorted intersection coordinate recording file for the area (divided area) assigned number 2 in Figure 12, the intersections are recorded in the order of intersection numbers 16, 18, 12, 11, 6, 7, 2, and 1. Therefore, in the divided area, a zigzag movement planned route within the divided area is created that traces the intersection coordinates in the order in which they are recorded in the sorted intersection coordinate recording file for each area (divided area).

The computer performs a process (phase 10) for 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: the area number management variable a is set to 1, the sort management variable i is set to 1, and the 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 numbers whose order has been rearranged by sorting are 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 criteria change variable register, an intersection coordinate recording file for each area, and an intersection coordinate recording file after sorting 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 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 coordinate with the largest Y coordinate is 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 multiple 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 found in step S144 is moved to the i-th position in the sorted intersection coordinate recording file for the a-th area (step S146). That is, if i is "1", the number and X and Y coordinate values of the intersection having the intersection coordinate 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 perform processing using a processing record file that 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 coordinates recorded first in the sorted intersection coordinate recording file are determined to be the intersection coordinates that will be the start position of movement in each divided area, and a zigzag path is created in each divided area by tracing a straight line S from the intersection coordinates that will be the start position of movement to the intersection coordinates that will be the end position of movement, 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 the process of transferring the searched coordinate data to the ith position in the sorted intersection coordinate record file for the ath area (step S146).
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 of Figure 12, first in step S144, intersections 16, 17, and 18 are found to have the largest Y coordinates, and then steps S145 and S154 are carried out to delete intersection 17. Then, because j = 1, the process proceeds to step S151 to search for the X and Y coordinates of intersection 16. Then j is set to j + 1 (step S152), and intersection 16 and its X and Y coordinates are recorded in the first recording area of the sorted intersection coordinate recording file for area 2 (divided area) (see Figure 29(b)). Then, in step S144, the intersection coordinates of numbers 11 and 12 are searched for as the coordinates with the largest Y coordinates. If it is determined in step S145 that there are two coordinates with the largest Y coordinates, then, since j=2 in this case, 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 that 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 line connecting the (i-1)th coordinate to the i-th coordinate in the sorted intersection coordinate recording file for the area will contact an exterior wall or a pillar (step S147). If no contact is found, 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 line contacts an exterior wall or a pillar, the i-th coordinate data in the sorted intersection coordinate record file for area is moved to the i+1th coordinate data, and then the i+1th X coordinate and the i+1th Y coordinate are written to 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, if the route comes into contact with an exterior wall or a pillar as shown in FIG. 30(a), the route is corrected so that it does not 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 ath 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 ath 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-1th coordinate information (step S147D).
That is, as shown in FIG. 12, for example, in areas 3 and 11, the values of 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 (intersections 3s and 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.
In other words, in steps S147C and S147D, the process determines 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 will be 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 step S142. That is, the sorting process for area a currently being processed ends, and the process moves on to the sorting process for 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 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 planned zigzag movement route within a 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 area a in the order of recording will be 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).
12, for example, a zigzag planned movement route H within the divided area is created that connects a planned movement start point (coordinate) 2s and a planned movement end point (coordinate) 2e within area 2. In addition, a planned movement start point (coordinate) Ns and a planned movement end point (coordinate) Ne (N is an integer excluding 7, 10, 12, 16, and 18 from 2 to 19) for each area (areas excluding pillar areas 7, 10, 12, 16, and 18 from 2 to 19) are determined, and a zigzag planned zigzag movement route H within the divided area (first route for each divided area) is created that connects the planned movement start point (coordinate) Ns and the planned movement 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 moves 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 costs of the planned zigzag movement routes (each first route) H, H... within each divided area created in phase 10, in accordance with the procedures of the movement cost calculation process program. In other words, for each planned zigzag movement route H, H... within each divided area, the movement cost is calculated taking into account the total straight distance, total turning angle, and number of turns.

The computer performs the 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 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). Also, 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 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 for each area. The post-sort 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 for straight-line movement (step S204), and the cost Cs for 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 record 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 transition 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 object 1.
Next, the angle θ formed by the vector pointing from the (i-1)th coordinate to the i-th coordinate in the sorted coordinate recording area for the a-th area and the vector pointing 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 cost Cc for linear movement (step S210), and the cost Cc for linear movement 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.
Furthermore, the straight-line running performance and cornering performance will differ 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 depending on 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 (phases 12 to 16) as shown in the flowchart of FIG. 23 in accordance with the procedures 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 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 moving direction of the straight line is set perpendicular to the X axis, and this is executed, which is set as phase 13 (step S240).
Furthermore, the process of extracting intersection coordinates 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 vertical lines.
Next, in the process of creating a planned zigzag movement route within the divided area (phase 10), the X-axis coordinates of the conditional branch processing part 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 separate from that for phase 10. This is 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 results are saved in a record file separate from that in phase 11. This is referred to as 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 the route selection process (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 that divided area.

The computer performs the 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 activated (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 activated (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 the value of a exceeds 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, and 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 travel route between divided areas (phase 18).

In the inter-divided area planned movement route creation process (phase 18), the computer follows the procedures of the intra-divided area zigzag movement planned route creation process program to generate an inter-divided area planned movement route, which is a planned movement route from the nth divided area E to the (n+1)th divided area E, 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 the planned movement end point (coordinate) 2e of the previous divided area (area) with the planned movement start point (coordinate) 2s of the next divided area (area) in a straight line.
In other words, a planned straight-line movement route I between divided areas is created, which connects the coordinate position of the intersection recorded at the end of the sorted intersection coordinate recording file for each nth divided area with 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 a straight line connecting the planned end point (coordinate) 2e and the planned start point (coordinate) 2s of the movement would result in contact (collision) with pillar B, a detour route is generated using a process for creating a detour route between divided areas that applies an arbitrary route search algorithm.

The computer performs the planned inter-divided area travel route creation process (phase 18) as shown in the flowchart of FIG. 25, in accordance with the procedure of the program for the process of creating a planned inter-divided area travel route.
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 travel 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 it does not exceed the upper limit, 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 record file for the ath area and the first coordinate in the sorted intersection coordinate record 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 that is the planned end point e of movement for 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 for the path search algorithm are initialized: cost C1[Xmax][Ymax]←[0,0,0,...], cost C2[Xmax][Ymax]←[0,0,0,...] (step S167).
First, calculate the distance between the current position and the starting point in the eight directions (up, down, left, right, and so on). For example, look at the C1s around the position for which you want to find the cost, and add +1 to the smallest C1 (however, ignore C1s that have not changed since initialization). The calculated cost is assigned to the C1 of the array element 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 path search algorithm) in the sorted intersection coordinate record file for the a+ith area is calculated from the eight directions above, below, left, and right as viewed from the current position. 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 assigned to C2 of the array element number corresponding to that position (step S168B).
A calculation completion flag is set for each of the eight directions, up, down, left, right and around the current position (step S169).
Among the coordinates for which the cost calculation 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).
If there are multiple coordinates that match in step S170, one of the coordinates with the same value is selected based on a predetermined priority order, and then the process proceeds to step S174. The predetermined priority order is: shortest estimated distance to the goal > longest distance from the start > 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+i)th 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 there is a location in the eight directions (up, down, left, right, and around) from the current position where the reached flag is set and the highest cost is present (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, an error is determined 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 confirmation flag is set for the destination coordinate (step S173A).
Then, it is determined whether or not the last coordinate of the a-th sorted intersection coordinate recording file has been reached (step S174).
If there are multiple coordinates that match in step S173, the robot moves to the coordinate with the same value that has the closest physical distance (Euclidean distance) to the start, and a route confirmation flag is set for the destination coordinate (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 record 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 record file as the route of movement after the a-th area search (planned inter-divided area 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 then 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. 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 inter-divided area travel route (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 travel route (phase 11) is terminated.

According to the process for creating a planned movement route between divided areas (phase 18), a planned movement route between divided areas such as that shown in FIG. 12 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 area a and divided area a+i. In FIG. 12 , arrow line 23 (I) is a planned movement route between divided areas connecting the planned movement end point (intersection coordinates) 2e in divided area 2 and the planned movement start point (intersection coordinates) 3s in divided area 3, arrow line 34 (I) is a planned movement route between divided areas connecting the planned movement end point 3e in divided area 3 and the planned movement start point 4s in divided area 4, arrow line 45 (I) is a planned movement route between divided areas connecting the planned movement end point 4e in divided area 4 and the planned movement start point 5s in divided area 5, and arrow line 56 (I) is a planned movement route between divided areas connecting the planned movement end point 5e in divided area 5 and the planned movement start point 6s in divided area 6.
In addition, arrow line 68 (I) is a planned route of movement between divided areas connecting planned end point 6e of movement in divided area 6 and planned start point 8s of movement in divided area 8, arrow line 89 (I) is a planned route of movement between divided areas connecting planned end point 8e of movement in divided area 8 and planned start point 9s of movement in divided area 9, arrow line 911 (I) is a planned route of movement between divided areas connecting planned end point 9e of movement in divided area 9 and planned start point 11s of movement in area 11, and straight line 1113 (I) that bypasses pillar 12 is a planned route of movement between divided areas connecting planned end point 11e of movement in divided area 11 and planned start point 12s of movement in divided area 13, and is a planned route of movement between divided areas searched for by the route search algorithm processing.
In addition, arrow line 1314 (I) is a planned inter-divided area travel route connecting planned end point 13e of travel in divided area 13 and planned start point 14s of travel in divided area 14, arrow line 1415 (I) is a planned inter-divided area travel route connecting planned end point 14e of travel in divided area 14 and planned start point 15s of travel in divided area 15, arrow line 1517 (I) is a planned inter-divided area travel route connecting planned end point 15e of travel in divided area 15 and planned start point 17s of travel in divided area 17, and arrow line 1719 (I) is a planned inter-divided area travel route connecting planned end point 17e of travel in divided area 17 and planned start point 19s of travel in divided area 19.
12, all planned routes of movement between divided areas are planned straight-line movement routes I between divided areas determined in step S178, and there are no planned detour movement routes between divided areas determined in 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 in step S178 will come 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 pillar 16 in FIG. 12 is a larger pillar, there is a possibility that arrow line 1415(I) will come into contact with pillar 16. In this case, a planned detour movement route between divided areas that bypasses pillar 16 is created based on the path search algorithm process.

As a result, the mobile object 1 can move between divided areas by following a pre-created optimal planned route between divided areas, allowing the mobile object to move between divided areas efficiently.

The planned travel route creation device and planned travel route creation processing program described above select the route with the best travel efficiency from the first route and the second route, making it possible to accurately create an efficient planned travel route for moving a moving object while avoiding obstacles within the target travel area, depending on 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 pillars (obstacles) B within the target movement area A.

That is, as shown in Figure 31, a control means 50 of the moving body 1 controls the movement of the moving body 1 based on the planned movement route (planned movement information), and a movement control system for the moving body 1 can be constructed that controls the movement of the moving body 1 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.
As a method for controlling the movement of the moving body 1, for example, the movement control method disclosed in Patent Document 1 (JP 2020-154400 A), an invention by the present applicant, may be adopted.

An example of the moving body 1 will be described below. In the following description, the directions of front, rear, up, down, left, and right will be defined as those shown in FIG.
As shown in Figure 31, the mobile 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 provided on the surface side of the base 10 for collimating the TS, an elevating device 40 provided on the base 10 for raising and lowering the front side of the mobile body 1, a control means 50, and an imaging means (camera) not shown for photographing the floor surface.
Furthermore, the imaging means is provided, for example, on the underside of the base 10 (the underside facing the floor surface) 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 facing across the left and right width of the underside of the moving body 1 when the moving body 1 moves on the floor surface.

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.
In addition, encoders 25L and 25R are attached to the motor shafts of the motors 23L and 23R, respectively, as movement amount detection means for detecting the movement distance (movement amount) of the mobile body 1 based on the rotation amount of the rear wheels 22L and 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 top surface of base 10.

When changing the direction of movement (direction of travel) of the moving body 1, the control means 50 extends the rod of the linear actuator (not shown) of the lifting device 40 from a retracted state and presses the rolling body (not shown) against the floor surface, thereby moving the front side of the base body 10 upward and lifting the front wheels 21L, 21R of the moving body 1 off the floor surface, 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 in opposite directions to each other.
In this case, by rotating one rear wheel in the direction of rotation that moves the mobile unit 1 forward and rotating the other rear wheel in the direction of rotation that moves the mobile unit 1 backward, the left and right rear wheels 22L, 22R and the rolling elements roll on the floor surface around the rotation center line of the mobile unit 1, so that the mobile unit 1 rotates smoothly left or right on the floor surface around the rotation center line. Thus, the horizontal orientation of the mobile unit 1 can be smoothly changed.

Note that, although the mobile body 1 is exemplified as a mobile body equipped with an imaging means (camera) that captures images of the floor surface, the mobile body may also be a mobile body equipped with a specific processing function, such as a mobile body equipped with a vacuum cleaner that cleans the floor surface, or a mobile body that does not have a specific processing function.

In addition, in the above-mentioned prerequisite device, the area outside the movement target area A, i.e., the outside-wall area, is set to Area 1. Therefore, in the variable initialization of step S131 of the area-by-area intersection coordinate extraction process (phase 9) in Figure 20, the variable initialization of step S141 of the process for creating a planned zigzag movement route within a divided area (phase 10) in Figure 21, the variable initialization of step S201 of the movement cost process (phase 11) in Figure 22, the variable initialization of step S281 of the route selection process (phase 17) in Figure 24, and the variable initialization of step S161 of the process for creating a planned movement route between divided areas (phase 18) in Figure 25, the area number management variable a is set to 1 to start processing. However, because Area 1 is not a divided area, the area number management variable a may be set to 2 in the variable initialization of each of these processes, and processing may start from Area 2.

The above-mentioned planned travel route creation device, which is a prerequisite device for the travel route creation device according to the present invention, assigns an area number to each divided area (each target travel area) according to a predetermined rule, and creates a planned travel route by connecting the divided areas (target travel area) in ascending order, starting with the divided area with the smallest number, with a planned travel route between the divided areas. In other words, a travel route that travels around each divided area is created.
However, this planned travel route creation device simply connects two divided areas with the closest numbers, starting with the divided area with the smallest number, with a planned travel route between divided areas, and does not evaluate whether the route that goes around each divided area is an efficient route.
Therefore, in the present invention, as will be described below, a travel route creation device is realized that can create an efficient travel route for a mobile object to travel through a plurality of target travel areas.

Embodiment A tour route creation device according to an embodiment of the present invention is a tour route creation device that recognizes the position information of a plurality of target areas and creates a tour route for a mobile body to tour the plurality of target areas.The tour route creation device is a tour route creation device that recognizes the position information of a plurality of target areas and creates a tour route for a mobile body to tour the plurality of target areas using a genetic algorithm (GA).

In the present invention, the multiple target areas to be moved are multiple independent target areas to be moved, or multiple divided areas as described above, and in the following explanation, the "target areas to be moved" will be referred to as "areas."

The circular route creation device according to the embodiment includes a circular loop creation means for creating a circular loop that goes around each area, a movement cost calculation means for calculating the movement cost when a mobile body travels along the route of the created circular loop, and a circular route creation means for deleting the inter-area route with the highest movement cost from among the inter-area routes that form the created circular loop, and creating a circular route that goes around each area, with the area that connected the end of the deleted inter-area route as the start area of the circular route and the area that connected the beginning of the deleted inter-area route as the goal area of the circular route.
The travel cost calculation means calculates the travel cost of moving a mobile object along the circular loop created by the circular loop creation means, the travel cost of moving a mobile object along an inter-area route connecting the previous and next areas in the circular loop created by the circular loop creation means, and the travel cost of moving a mobile object along the circular route created by the circular route creation means.In other words, the travel cost calculation means is a means for calculating the travel cost of the route of the circular loop, such as the circular loop, the inter-area route connecting the previous and next areas of the circular loop, and the circular loop obtained by subtracting the travel cost of the inter-area route with the highest travel cost from the travel cost of the circular loop.Note that the travel cost is a travel cost that takes into account the total straight distance, total turning angle, and number of turns, as described in the above-mentioned prerequisite device.
The cyclic loop creating means includes an initial generation cyclic loop creating means for creating a cyclic loop by setting cyclic information for each area, and a later generation cyclic loop creating means.
The tour route creating means includes an initial generation tour route creating means and a later generation tour route creating means.
The initial generation cyclic loop creating means creates a plurality of cyclic loops.
The initial generation circulating route creating means changes the circulating information for each area for each of the initial generation circulating loops created by the initial generation circulating loop creating means, and creates a plurality of initial generation circulating routes.
Further, the later generation circular loop creating means extracts some early generation circular routes with small travel costs from among the plurality of early generation circular routes, and creates a later generation circular loop using the circular information of the extracted early generation circular routes.
The next-generation circular route creating means changes the circular information for each area for each next-generation circular loop created by the next-generation circular loop creating means, and creates a next-generation circular route.
The number of the next generation is plural, and the current next generation circular route creation means changes the circular information for each area for each previous next generation circular loop created by the previous next generation circular loop creation means, and creates the current next generation circular route.
The next-generation tour route creation means for the final generation determines the tour route with the smallest travel cost from among the multiple tour routes created for the final generation. The final tour route becomes the tour route calculated by the GA process.

Each of the above-mentioned means is configured by a processing program that indicates the procedure of the processing that each means executes, and hardware resources such as a computer that realizes information processing according to the processing program.
In other words, the route generation processing program that realizes the processing of the route generation device is a program that causes a computer to function as each of the above-mentioned means.
The tour route creation device is configured by installing the above-mentioned tour route creation processing program in a computer such as a personal computer equipped with a display screen and display control means.

As described above, an area is a region partitioned based on XY coordinate information.
Furthermore, the predetermined circulation pattern within the area is, for example, an X-direction circulation pattern that moves zigzag along the X-axis, or a Y-direction circulation pattern that moves zigzag along the Y-axis.
As shown in FIG. 32, for example, the plurality of predetermined cyclic patterns within an area are, in an X-direction cyclic pattern, a Z pattern (first pattern) in which the movement start position (starting end (entrance)) is the position of the minimum X coordinate and the maximum Y coordinate, a Z' pattern (second pattern) in which the movement start position is the position of the minimum X coordinate and the minimum Y coordinate, an S pattern (third pattern) in which the movement start position is the position of the maximum X coordinate and the maximum Y coordinate, and an S' pattern (fourth pattern) in which the movement start position is the position of the maximum X coordinate and the minimum Y coordinate.
In addition, the Y-direction cyclic patterns include a W pattern (fifth pattern) in which the start position of movement is the position of the minimum X coordinate and the maximum Y coordinate; a W' pattern (sixth pattern) in which the start position of movement is the position of the maximum X coordinate and the maximum Y coordinate; an M pattern (seventh pattern) in which the start position of movement is the position of the minimum X coordinate and the minimum Y coordinate; and an M' pattern (eighth pattern) in which the start position of movement is the position of the maximum X coordinate and the minimum Y coordinate.
Furthermore, when each of the multiple patrol patterns is set in each area, the travel cost when moving a mobile object along each of the patterns is calculated in advance by, for example, a travel cost calculation means and recorded in a database.

The patrol information is, for example, as shown in FIG. 39, combination information configured of information on a patrol pattern within the area set for each area and information on the area to proceed to next.
39, the patrol information for area 1 is "2-M," where "M" is information about the patrol pattern within area 1 (self), and "2" is information about the next area to proceed to. That is, the patrol pattern within area 1 is set to M pattern (seventh pattern) based on the patrol information for area 1, and the area to proceed to after area 1 is 2, so a route connecting the end point (exit) of M pattern, which is the patrol pattern for area 1, and the start point (entrance) of Z pattern, which is the patrol pattern for area 2, is set as the inter-area route.
That is, the circular loop is created based on the circular information, and the inter-area route with the highest travel cost is deleted from among the inter-area routes of the circular loop to create the circular route.

FIG. 33 shows an outline of the flow of a route creation process by the route creation device according to the embodiment, that is, a route creation process using a genetic algorithm (GA) (hereinafter referred to as GA process).
In the GA processing, the above-mentioned cyclic information will be appropriately replaced with genetic information for explanation.
In the embodiment, the number of subsequent generations is set to, for example, 100 or more.
That is, as shown in FIG. 33, the GA process executes an initial generation individual creation process (step S401) for creating multiple individuals of the initial generation, an individual evaluation process (step S402), a generation confirmation process (step S403), a parent selection process (step S404) for selecting multiple individuals with excellent genetic information as parents, and a subsequent generation individual creation process (step S404) for creating subsequent generation individuals using the genetic information of the parents.
The flow of the GA process can be briefly explained as follows based on FIG.
First, a plurality of individuals, i.e., a plurality of cyclic loops, are created by the initial generation individual creation process (step S401). In this case, for each area, as shown in Fig. 38(a), combination information consisting of information on the cyclic pattern within the area itself and information on the area to proceed to next, i.e., genetic information (cyclic information), is randomly set to create individuals that will become cyclic loops (initial cyclic information array).
In the individual evaluation process (step S402), each individual travel route is evaluated. That is, a travel route is created by deleting the maximum inter-area route with the highest travel cost in the travel loop, and the travel cost of the travel route is calculated.
In the generation confirmation process (step S403), it is confirmed whether the current generation has reached a predetermined number of generations.
If the current generation has not reached a predetermined number of generations (for example, 100 or more) (No in step S403), multiple individuals (for example, four individuals) with excellent movement costs are selected as parents from the individuals of the current generation (initial generation or later generation) (step S404).
An excellent individual selected from the individuals of the current generation is used as a parent to create an individual of the next generation using the genetic information of that parent (step S405).
Thereafter, steps 402 to 405 are repeated, and if the determination in step S403 is Yes, the GA process is terminated.

That is, the GA process involves the creation of initial-generation individuals, the evaluation of individuals, the generation confirmation process, the parent selection process, and the creation of subsequent-generation individuals. That is, each of these processes is executed by a processing program that indicates the procedure for each of these processes and a computer that realizes information processing by the processing program.
The following will explain in detail the contents of the initial generation individual creation process, individual evaluation process, generation confirmation process, parent selection process, and subsequent generation individual creation process.
That is, in the GA processing, the cyclic pattern setting means and cyclic order setting means perform the initial generation individual creation processing, generation confirmation processing, subsequent generation individual creation processing, individual evaluation processing, and excellent individual extraction processing. That is, each of these processes (initial generation individual creation processing, generation confirmation processing, subsequent generation individual creation processing, individual evaluation processing, and excellent individual extraction processing) is executed by a processing program indicating the procedure for each of these processes, and a computer that realizes information processing by the processing program.

First, the computer performs the initial generation individual creation process (phase 1) as shown in the flowchart of FIG. 34, in accordance with the procedure of the initial generation individual creation process program.
In the GA process, an "individual" refers to a cyclic loop or a cyclic route.
First, the individual identification variable p is initialized and the area number information amax is acquired (step S411). That is, the area number management variable a is set to 1, and the area number information amax is set to the number of areas (for example, in the case of the above-mentioned base technology (the case of multiple divided areas in FIG. 12), the number information amax is set to "16", and in the case of FIG. 38(a), the number information amax is set to "6").
Then, the genetic information array G[1 to 20][1 to amax][1 to 2] is initialized to be empty (step S412).
Next, a loop for creating initial generation individuals is entered (step S413). For example, 20 initial generation individuals are created. That is, p<=20 (i.e., p≦20).
First, the area number control variable a is initialized, that is, the area number control variable a is set to 1 (step S414).
Then, a value between areas 2 and amax and not yet included in the genetic information array G[p][1 to amax][1] is randomly assigned to the genetic information array G[p][a][1] (step S415), and a numerical value representing the cyclic pattern is randomly assigned to the genetic information array G[p][a][2] (step S416).
Then, a is set to G[p][a][1] (step S417).
Then, it is determined whether two or more empty elements remain in the genetic information array G[p][1 to amax][1] (step S418). That is, if there are two or more areas in the genetic information (cyclic information) of a single individual for which no information about the next area has been set (Yes in step S418), steps S415 to S417 are repeated. If there is only one area in the genetic information of a single individual for which no information about the next area has been set (No in step S418), the genetic information array G[p][a][1] for that area is set to 1 (step S419), and a value representing the cyclic pattern is randomly assigned to the genetic information array G[p][a][2] for that area (step S420). That is, the area number of the area to be advanced to last is set to 1, and the cyclic pattern for that area is randomly set.
Then, p is set to p+1 (step S421).
That is, steps S413 to S421 are repeated a number of times to create a number of individuals (for example, 20 individuals) of the initial generation.
That is, the "initial generation individual creation loop" shown in FIG. 34 is executed.

The genetic information sequence G[1-20][1-amax][1-2] will be explained.
[1-20] are variables for identifying individuals to be created in the initial-generation individual creation process, and [1-amax] are variables for identifying areas. G[p][a][1] is set with information about the area to which the a-th area of the p-th individual of the initial generation will next advance. Furthermore, G[p][a][2] is set with information about the intra-area movement route pattern of the a-th area of the p-th individual of the initial generation. That is, a recording area is constructed in which cyclic information (genetic information) for each area constituting the individuals (cyclic loops) to be created is set, and multiple cyclic information sequences forming multiple individuals are recorded in the recording area in the form of a genetic information array G[1-pmax][1-amax][1-2]. For example, if the number of individuals in the initial generation is 20, the 20 cyclic information sequences forming the 20 individuals are recorded in the form of a genetic information array G[1-20][1-amax][1-2].

In the genetic information array G[1-20][1-amax][1-2], [1-amax] is the number of each area, G[a][1] is the address of the memory area where information on the next area from area a is recorded, and G[a][2] is the address of the memory area where information on the cyclic pattern within area a is recorded.
That is, [a] is information indicating the area number, G[a][1] records information (genetic information (cyclic information)) of the area number to proceed to next from area [a], and G[a][2] records information (genetic information (cyclic information)) of the cyclic pattern within area [a].
Therefore, hereinafter, G[a][1] means information on the number of the next area to proceed from area [a], and G[a][2] means information on the cyclic pattern within area [a].
In other words, the cyclic information array G[1 to amax][1 to 2] for each individual is a group of information recorded at the address G[1 to amax][1 to 2], i.e., a combination of genetic information as shown in Figure 38(a), and this cyclic information array forms a cyclic loop for each initial generation individual.
For example, when the number of areas is six, each of the cyclic information sequences constituting the genetic information sequence G set in phase 1 becomes an initial cyclic information sequence as shown in FIG. 38(a).
That is, the initial cyclic information array G[1 to amax][1 to 2] shown in FIG. 38(a) is as follows:
Area number 2 is recorded in address [1][1], which records information about the number of the area to proceed to next from area [1], and pattern Z is recorded in address [1][2], which records information about the cyclic pattern within area [1]. In other words, "2-Z" is set as the cyclic information for area number 1.
Furthermore, area number 3 is recorded in address [2][1], which records information on the number of the area to proceed to next from area [2], and Z pattern is recorded in address [2][2], which records information on the cyclic pattern within area [2]. In other words, "3-Z" is set as the cyclic information for area number 2.
Furthermore, area number 4 is recorded in address [3][1], which records information on the number of the area to proceed to next from area [3], and pattern Z is recorded in address [3][2], which records information on the cyclic pattern within area [3]. In other words, "4-Z" is set as the cyclic information for area number 3.
Furthermore, area number 5 is recorded in address [4][1], which records information on the number of the area to proceed to next from area [4], and Z pattern is recorded in address [4][2], which records information on the cyclic pattern within area [4]. In other words, "5-Z" is set as the cyclic information for area number 4.
Furthermore, area number 6 is recorded in address [5][1], which records information on the number of the area to proceed to next from area [5], and pattern Z is recorded in address [5][2], which records information on the cyclic pattern within area [5]. In other words, "6-Z" is set as the cyclic information for area number 5.
Furthermore, area number 1 is recorded in address [6][1], which records information on the number of the area to proceed to next from area [6], and Z pattern is recorded in address [6][2], which records information on the cyclic pattern within area [6]. In other words, "1-Z" is set as the cyclic information for area number 6.
The initial cyclic loop created based on the initial cyclic information array is an initial cyclic loop as shown in FIG.
In FIG. 38(b), p is a pat- tern and r is an inter-area route.

That is, in the GA process, a plurality of initial cyclic loops (initial individuals) specified by the cyclic information sequence are generated as initial generation individuals, and crossover and mutation processes are performed to generate a plurality of individuals for each subsequent generation.
Roughly speaking, GA processing involves multiple initial cyclic loops, i.e., generating initial generation individuals, and then generating next generation individuals by selecting excellent parent individuals from the initial generation individuals and performing crossover and mutation processes using the parent individuals. Similarly, when generating the current generation of individuals, excellent parent individuals are selected from the previous generation of individuals and performing crossover and mutation processes using the parent individuals to generate the current generation of individuals, and this process is repeated a predetermined number of generations.
That is, the initial generation individual creation process is a process of creating multiple, for example 20, initial cyclic information arrays G[1 to amax][1 to 2] of the initial cyclic information array G[1 to amax][1 to 2] shown in Figure 38(a) described above, and storing them as genetic information arrays G[1 to 20][1 to amax][1 to 2], that is, a process of repeating the processes of steps S413 to S421 in Figure 34 20 times to generate (create) 20 initial generation individuals.
Furthermore, when the processing for a predetermined number of generations is completed, a circulating route is determined based on a circulating loop of the optimal genetic information storing sequence Gbest[1 to amax][1 to 2] that remains at the end.
The crossover process and mutation process will be described later.

Next, the computer performs the individual evaluation process (including generation confirmation process) (phase 2) as shown in the flowchart of FIG. 35, in accordance with the procedure of the individual evaluation process program (including generation confirmation process program).
After the processing of phase 1, the optimal cost variable and the optimal genetic information storage array are initialized (step S430). That is, the optimal cost variable Cbest is set to 0, and the optimal genetic information storage array Gbest[1 to amax][1 to 2] is made empty.
Next, it is determined which generation the individual to be evaluated is from (step S431). That is, a generation confirmation process is performed.
If the individual to be evaluated is an individual from the first generation (initial generation), the individual variables and cost management array are initialized (step S432). That is, the individual variable p is set to 1, and the cost management array C[1 to amax] is set to 0.
Then, the process enters into an individual evaluation loop (step S433), for example, in which 20 individuals that are initial generation individuals are evaluated.
First, the area number management variable a, the area full-circle search completion flag f, and the inter-area movement maximum cost management variable Cmax are initialized (step S434). That is, the area number management variable a is set to 1, the area full-circle search completion flag f is set to 0, and the inter-area movement maximum cost management variable Cmax is set to 0.
Next, it is determined whether the area full search completion flag is set (step S435), that is, whether the area full search completion flag f is 1 or not.
If the area full search completion flag f is not 1 (No in step S435), the travel cost for traveling around the ath area using the travel pattern specified by the genetic information array G[p][a][2] is downloaded from the database and added to the travel cost C[p] (step S436).
Next, it is determined whether the genetic information sequence G[p][a][2] indicates the first area where processing has started (step S437).
Thereafter, the process proceeds to the process of creating an inter-area route and calculating travel costs.
If the answer is No in step S437, the process then proceeds to step S440 to create an inter-area route and calculate a travel cost.
That is, if the answer is Yes in step S437, that is, if the value of G[p][a][2] (the number of the next area to proceed to) is the area number where processing began, then the search area (each area) has been circumnavigated, and after setting the area circumnavigation completed flag f to 1, it is determined whether it is possible to move in a straight line from the ath area to the first area (step S439), and the process proceeds to the creation of an inter-area route and the calculation of travel costs.

If the answer is No in step S437, it is determined whether it is possible to move in a straight line from the a-th area to the area set in the genetic information array [p][a][2] (step S440). If it is possible to move in a straight line (Yes in step S440), the movement cost Ctravel for moving in a straight line from the finish point in the a-th area to the start point in the genetic information array G[i][a][1] is calculated (step S441).
Furthermore, if it is not possible to move in a straight line (No in step S440), a route from the finish point in the ath area to the start point in the genetic information array G[p][a][1]th area is calculated using a route search algorithm (for example, the A* algorithm described in the prerequisite technology), and the travel cost Ctravel of that route is calculated based on that route (step S442).
After step S441 or step S442, it is determined whether Ctravel>Cmax (step S443).
If Ctravel > Cmax is not satisfied (No in step S443), the travel cost from the goal point of the ath area to the start point of the G[p][a][1]th area is added to the travel cost C[p] (step S444), and then G[p][a][1] is set to a (step S446).
If Ctravel > Cmax (Yes in step S443), Cmax is set to Ctravel, and the area number set in G[p][a][1] is set as the travel start area number S (step S445), and then the process proceeds to step S444.
That is, the inter-area route having a travel cost remaining in Cmax after the determination in step S443 becomes the maximum inter-area route of the individual (circulating loop).
If the determination in step S439 is Yes, the process proceeds to step S442, and if the determination in step S439 is No, the process proceeds to step S441.
After the inter-area route creation process and travel cost calculation process have been performed as described above, the process returns to step S435.

If the area full search completion flag f is 1 (Yes in step S435), C[i] is set to C[i] - Cmax (step S447), and then it is determined whether Cbest is in the initial state or whether the optimal travel cost Cbest > C[i] (step S448). Note that C[i] on the right in step S447 is the travel cost of the circular loop, and C[i] on the left in step S447 is the travel cost of the circular route.
If Cbest is in the initial state or the optimal cost variable Cbest>C[i] (Yes in step S448), the travel cost C[i] of the travel route is set to the optimal cost variable Cbest, and the optimal genetic information storage array Gbest[1 to amax][1 to 2] is set to G[p][1 to amax][1 to 2], and then p is set to p+1 (step S450).
That is, in steps S447 to S449, C[i] is the travel cost of the tour route created based on each individual (tour loop) created.
If the travel cost C[i] of the newly created circular route is smaller than the optimal travel cost Cbest of the circular routes created so far, in step S449, the travel cost C[i] is rewritten to the optimal travel cost Cbest, and an update process is performed in which the genetic information storage array G[p][1 to amax][1 to 2] of the circular loop (individual) that was the basis for the circular route with the travel cost C[i] is rewritten to the optimal genetic information storage array Gbest[1 to amax][1 to 2]. That is, in step S449, the circular loop (individual) that was the basis for the optimal circular loop (circular loop with the smallest travel cost) for each generation is recorded.
If Cbest is not in the initial state or the optimal cost variable Cbest>C[i] is not satisfied (No in step S448), the process proceeds to step S450 to move on to the evaluation of the next individual p.
The processes from step S433 to step S450 are repeated until the process of creating inter-area routes and calculating travel costs for all individuals in a generation, for example, 20 individuals per generation, is completed. Then, it is determined whether the generation is the final generation (step S451).
If it is not the final generation (No in step S451), for example, four individuals are sorted in ascending order of cost from the movement costs C[1-20] of the 20 individuals (cyclic loops) created for each generation, and the information of those individuals is transferred to their respective movement costs C[1-4] and genetic information arrays G[1-4][1-2] (step S452). That is, the four individuals with the lowest costs are selected as parents for creating individuals of the next generation, and the movement costs C[1-4] and genetic information arrays G[1-4][1-2] of those parents are recorded.
If it is the final generation (Yes in step S451), the GA is terminated. At this termination point, the circular route having a travel cost calculated by subtracting Cmax from the travel cost of the circular loop based on the genetic information (circulation information) recorded in the optimal genetic information storage array Gbest[1 to amax][1 to 2] is the circular route created as a result of the search by the GA. That is, in step S453, the information on the circular loop that recorded Gbest, i.e., the route information recorded in the optimal circular information array Gbest[1 to amax][1 to 2], the trajectory information of the inter-area route when traveling based on this route information, and the travel start area number recorded in S are saved in a file. The content saved in this file is the final circular route determined by the GA, and the information on this circular route and the travel cost Cbest of the circular route are displayed on the display screen D, allowing the user to confirm the final circular route determined by the GA.

The computer performs crossover processing (phase 3-1) as a process for creating successive generation individuals, as shown in the flowchart of FIG. 36, in accordance with the procedure of the crossover processing program.
First, the individual identification variable is initialized, that is, the individual identification variable p is set to 5 (step S460).
The genetic information sequence G[1-20][1-amax][1-2] is inherited from phase 2 (step S461).
The genetic information array G[5-20][1-amax][1-2] is initialized to empty (step S462). That is, of the 20 individuals inherited from phase 2, for example, information on 16 individuals with high migration costs is deleted (the 16 individuals of the previous generation are killed).
Next, a loop is entered in which, for example, 12 offspring are created by crossover processing, where p<=16 (i.e., p≦16) (step S463).
The number of offspring individuals in the next generation is, for example, 20 (total number of offspring individuals in the next generation) - 4 (parent individuals in the next generation), or 16. In the crossover process, 12 offspring individuals are created, and in the mutation process (phase 3-2) described below, 4 offspring individuals are created.

Two individuals are selected from four parent individuals. The selection method is performed according to a predetermined procedure (step S464). Two individuals can be selected randomly from the four parent individuals, but there is a possibility that the same parent individual will be selected, making it difficult to achieve diversity. Therefore, for example, combinations of two individuals are selected from the four parent individuals, and one of these combinations is selected from any of the parent individual combinations. Here, to create 12 child individuals, 12 combinations of parent individuals are obtained.
The genetic information of one of the selected parent individuals is copied to array P1[1 to amax][1 to 2], and the genetic information of the other parent individual is copied to array P2[1 to amax][1 to 2] (step S465).
Then, the area number control variable is initialized, that is, the area number control variable a is set to 1 (step S466).
Also, the flag for determining whether or not the inheritance from the parent P1 is to be initialized, that is, flag f1 is set to 0, and the flag for determining whether or not the inheritance from the parent P2 is to be initialized, that is, flag f2 is set to 0 (step S467).
This completes the pre-processing for moving on to the crossover process, and then the process proceeds to step S468, where it is determined whether or not the crossover process for the genetic information of the pth individual where a=1 has been performed one or more times. That is, it is determined whether or not the genetic information of the pth individual has reached a state where it can go around the area and return, that is, whether or not the pth cyclic loop that goes around each area has been created based on the genetic information. If the determination in step S468 is No, the process proceeds to the crossover process. Note that the crossover process refers to the process of inheriting the cyclic information of the parent individual when creating a child individual (subsequent generation cyclic loop) (process B2 described below), or the process of randomly setting the cyclic information when the cyclic information of the parent individual cannot be inherited (processes B4 and B3 described below).

In the crossover process, the process first proceeds to process block B1, which prevents the inheritance of lethal genetic information.
In processing block B1, it is first determined whether or not two or more empty elements remain in the genetic information array G[p][1 to amax][1 to 2] (step S469).
If the determination in step S469 is Yes, it is determined whether P1[a][1] = 1 or whether the same value as P1[a][1] is already recorded in G[p][1 to amax][1] (destination area information, which is genetic information set for each area) that is being created (step S470).
If the determination in step S470 is No, it is determined whether P2[a][1] = 1 or whether the same value as P2[a][1] is already recorded in G[p][1 to amax][2] (information on the cyclic pattern, which is genetic information set in each area) that is being created (step S471).
If the determination in step S471 is No, the process proceeds to basic crossover processing block B2.
If the determination in step S470 is Yes, in order to avoid setting the same information as genetic information, it is determined that inheritance from parent P1 is not possible, flag f1 is set to 1, and then the process proceeds to step S471.
If the judgment in step S471 is Yes, in order to avoid setting the same information as genetic information, it is determined that inheritance from parent P2 is not possible, flag f2 is set to 1, and then the process proceeds to step S472 of basic crossover processing block B2.
That is, steps S480, S483, and S484 prevent the inheritance of lethal genetic information that leads to cecal gland formation or multiple loops. In other words, the crossover process ensures that a genetic information sequence that always forms one loop is created.

In the basic crossover processing block B2, first, in step S472, it is determined whether flag f1 = 0 and flag f2 = 0. In other words, it is determined whether the trait can be inherited from either parent.
If the determination in step S472 is No, it is determined whether flag f1 = 1 and flag f2 = 0. That is, it is determined whether only parent P1 is inheritable (step S473).
If the determination in step S473 is No, it is determined whether flag f1 = 0 and flag f2 = 1. That is, it is determined whether only parent P2 is inheritable (step S474).
In the basic crossover processing block B2, if the determination in step S472 is Yes, numerical values from 1 to 100 are prepared, one is extracted from the prepared values, and it is determined whether the extracted numerical value is 51 or greater (step S485). It is also possible to prepare the numerical values 1 and 0, and determine whether the extracted numerical value is 1.
That is, if the determination in step S472 is Yes, inheritance is possible from either parent P1 or parent P2, and the parent from which inheritance is to be made is selected randomly in step S485.
If the determination in step S485 is Yes, genetic information is inherited from parent P1. That is, G[p][a][1] is replaced with P1[a][1], and G[p][a][2] is replaced with P1[a][2] (step S486). Then, a is replaced with G[p][a][1] (step S478), and the process returns to step S467.
If the determination in step S485 is No, genetic information is inherited from parent P2. That is, G[p][a][1] is replaced with P2[a][1], and G[p][a][2] is replaced with P2[a][3] (step S487). Then, a is replaced with G[p][a][1] (step S478), and the process returns to step S467.

If the determination in step S469 is No, that is, if there is only one empty element remaining in the genetic information array G[p][1 to amax][1 to 2], the destination area G[p][a][1] of that one empty area is set to 1 (step S480) to prevent a dead end or multiple loops, and a genetic information array G[p][1 to amax][1 to 2] that forms one loop is created, and the cyclic pattern G[p][a][2] of that one empty area is inherited from parent P1 or parent P2 (process B3).
Also, if the judgment in step S474 is No, flag f1 = 1 and flag f2 = 1, and inheritance is not possible from either parent P1 or parent P2, so the destination area G[p][a][1] of the area currently undergoing crossover processing is randomly set to an area other than the areas already set (process B4).
That is, if the judgment in step S474 is No, proceed to step S475, where a value other than the value already existing in G[p][1 to amax][1] is randomly selected from areas 2 to amax and assigned to G[p][a][1] (step S475), and then proceed to step S476 in processing block B3, where the cyclic pattern G[p][a][2] of the area currently undergoing crossover processing is inherited from parent P1 or parent P2 (processing B3).

When moving from processing block B4 (step S475) to exceptional crossover processing block B3, first proceed to step S476, prepare numbers from 1 to 100, extract one from the number, and determine whether the number is equal to or greater than 51. Alternatively, prepare the numbers 1 and 0, and determine whether the extracted number is 1.
If the determination in step S476 is No, the genetic information of the cyclic pattern is inherited from the parent P1. That is, G[p][a][2] is replaced with P1[a][2] (step S477). Then, a is replaced with G[p][a][1] (step S478), and the process returns to step S467.
If the determination in step S476 is Yes, the genetic information of the cyclic pattern is inherited from parent P2. That is, G[p][a][2] is replaced with P2[a][2] (step S479). Then, a is replaced with G[p][a][1] (step S478), and the process returns to step S467.

When moving from processing block B1 to exceptional crossover processing block B3 via step S480, first proceed to step S481 to determine whether P1[a][1] = 1 and P2[a][1] = 1, or whether P1[a][1] ≠ 1 and P2[a][1] ≠ 1.
That is, if the destination area of area a of parent P1 is 1 and the destination area of area a of parent P2 is 1, that is, if the destination areas of areas a of parents P1 and P2 are both 1, or if the destination areas of area a of parent P1 are not both 1, then the patrol pattern G[p][a][1] of the child's area a is set to the patrol pattern of area a of parent P1 or the patrol pattern of area a of parent P2. Which patrol pattern is used is determined randomly in step S476.
If the determination in step S481 is No, it is determined whether P1[a][1] = 1 (step S482), and if P1[a][1] = 1, proceed to step S477, and if P1[a][1] = 1 is not, proceed to step S479.
If the determination in step S481 is Yes, the process proceeds to step S476.
If the determination in step S468 is Yes, p is set to p+1, and then the process proceeds to Phase 3-2.

The flow of the crossover process in FIG. 36 will be described.
In creating a child individual, first, the process proceeds to steps S468, S469, S470, S471, and S472, and if step S472 returns Yes, then step S485 is passed on to the child individual's genetic information for area 1 (area 1 circulation pattern, next destination area from area 1) from parent P1 or parent P2 (basic crossover (step S486 or step S487)). Then, the area number management variable a is set to the next destination area G[p][a][1], which is the genetic information for area 1 of the child individual (step S478).
Also, if the answer is Yes in step S469 and the process proceeds to step S474, and genetic information cannot be inherited from either parent P1 or parent P2 (No in step S474), an area that has not yet been set as a destination area is randomly selected from areas 2 to amax (amax = 10 in Figure 42) and set as the next destination area G[p][a][1] (step S475 (exceptional crossover)), and the process proceeds to step S476, where the circulation pattern [p][a][2] of area a is inherited from parent P1 or parent P2 (step S477 or step S479 (exceptional crossover)).
If the determination in step S469 is No, that is, if only one empty element remains in the genetic information array G[p][1-amax][1-2], G[p][a][1] is set to 1 (step S480) to prevent the occurrence of lethal genetic information that would lead to multiple loops. After that, the area circulation pattern G[p][a][2] with the child's destination area set to 1 is inherited from parent P1 or parent P2 (processing block B3).
Furthermore, the processes in steps S470, S483, S471, and S484 are performed to prevent the generation of lethal genetic information that would cause cecal flare-ups.
In other words, the new generation circular route creation means sets the circular information when creating a circular loop so that the circular loop does not form multiple loops or so that the circular loop does not form a dead end line.
In other words, the current next-generation circular route creation means defines one or more of the circular routes with the lowest travel costs from among the previous multiple next-generation circular loops created by the previous next-generation circular loop creation means as parents, and creates the current next-generation circular route by inheriting the circular information of the parent circular route (see processes B1 to B4 in Figure 36).
Furthermore, if, at the stage of creating the current next-generation circular route, there remain two or more areas for which circular information has not yet been set, and the information for the next area to be set, which is the circular information to be set for the areas for which circular information has not yet been set, cannot be inherited from the parent, the current next-generation circular route creation means arbitrarily selects the next area to be set for the areas for which circular information has not yet been set from among the areas for which circular information has not yet been set (see process B4 (step S475) in Figure 36).
In addition, the above-mentioned cases where the information of the next area to proceed, which is the patrol information to be set for an area for which patrol information has not yet been set, cannot be inherited from the parent are when the information of the next area to proceed, which is the patrol information of the parent that is to be inherited for an area for which patrol information has not yet been set, is the area for which patrol information was first set when creating the current next-generation patrol route, and when the information of the next area to proceed, which is the patrol information of the parent that is to be inherited for an area for which patrol information has not yet been set, has already been used in creating the current next-generation patrol route (see steps S470, S483, S471, and S484 of processing B1 in Figure 36).
Furthermore, when the current next-generation circular route creation means determines that there is only one area remaining for which no circular information has yet been set at the stage of creating the current next-generation circular route, it sets the circular information for that remaining area, which is the information for the next area to proceed to, as the area for which circular information was first set when creating the current generation circular route (see steps S469 and S480 of processing B1 in Figure 36).

A supplementary explanation will be given for the processing block B1.
Here, lethal genetic information refers to genetic information (circulating information) that results in the formation of individuals that cannot complete a full circuit of the entire area, such as individuals with multiple loops or individuals with appendicitis.

For example, the individual shown in Figure 40 has two loops: 1-3-6-1 and 2-10-5-4-9-8-7. An individual with such genetic information cannot achieve the original goal of traveling around each area.
The individual shown in Figure 41 has two pieces of genetic information (7-Z, 7-Z') that specify that the next area to go to is 7. In addition, there is no genetic information that specifies that the next area to go to is 7. In other words, the individual returns to 6-4-9-8-7-2-10-5-1-3-7, and the route from the 7-2-10-5-1-3 loop to 7-8-9-4-6 becomes a dead-end line. Even an individual with this kind of genetic information cannot achieve the original goal of going around each area once.

A supplementary explanation will be given of the basic crossover processing block B2.
In basic crossover processing, the next crossover operation is performed in the area (area number) specified in the "next area" in the adopted genetic information.
Figure 42 shows an example in which the genetic information gi of the child's area 1 is inherited from the genetic information 3-Z of the parent 1. In this case, the adopted genetic information is (3-Z), so the operation area for the next crossover is area 3. Figure 42 also shows an example in which the genetic information gi of the child's area 3 is inherited from the genetic information 4-Z' of the parent 2.
That is, in processing block B2 of Figure 36, when genetic information is inherited from either parent 1 or parent 2, area a where the next crossover operation will be performed is set to G[p][P][1], which is the "next area to proceed to" in the inherited genetic information (step S478).
If genetic information cannot be inherited from either parent 1 or parent 2,
G[p][P][1], which is the area where the next crossover operation will be performed, is set randomly (step S475, processing block B4).

The exceptional crossover processing blocks B3 and B4 will now be explained in more detail.
In cases where normal crossover may result in lethal genetic information, processing is performed based on the following rules to avoid this.

Pattern A: If the genetic information for the destination area number of one of the parents has already been determined, it is prohibited to obtain genetic information from that parent (steps S470, S483, S471, S484).
In Figure 43, when crossing the genetic information of child area 8, if the genetic information of area 8 of parent 2 is taken, the destination area of that genetic information, "9," has already been determined as the destination area in the genetic information of child area 4 (step S471). Therefore, the genetic information of area 8, which is the crossover target area ca, is prohibited from being taken from the genetic information of parent 2 (step S484). If genetic information from parent 2 were taken as the genetic information of area 8, which is the crossover target area ca, the child would become an individual with lethal genetic information that would result in multiple loops. Therefore, in this case, the genetic information of area 8 of this child is inherited as genetic information 7-Z' from parent 1 (steps S474 and S486).

Pattern B: If both parents have already determined the genetic information for the destination area number, the genetic information for the next area number is prohibited from being inherited from the parents (No in step S474), and an area number is selected at random from the free area (step S475). The genetic information for the cyclic pattern is inherited at random from either parent.
In Figure 44, the genetic information for this child has already been determined for the corresponding locations in both area 2 and area 8. Therefore, the destination area for area 7, which is the crossover target area ca, is selected at random from the numbers of the areas where the genetic information for the next area number is in the empty state ea (in this example, only 3 applies, so 3 is determined).
The rotation pattern is chosen randomly from the genetic information in this region possessed by the parents (in this example, Z or S).
In other words, in this situation, the child will have genetic information of 3-Z or 3-S in area 7, which is the crossover target area ca.

Pattern C: In the crossover target area ca, if both parents have already determined the genetic information for the area number of the destination area and there is no free space, inheritance from the parents is prohibited and 1 is selected. The genetic information for the cyclic pattern is inherited randomly from one of the parents.
In Figure 45, the genetic information for the corresponding locations of area 4 and area 7 of this child itself has already been determined. In addition, there are no vacant areas. In this situation, "1" is set as the genetic information for the next area number in area 6, which is the crossover target area ca. The cyclic pattern is also selected randomly from the genetic information for this area held by the parent (determined as S' in this example). In other words, in this situation, the genetic information of 1-S' is set in area 6, which is the crossover target area ca of this child.

Next, the computer performs mutation processing (phase 3-2) according to the procedure of the mutation processing program, as shown in the flowchart of Fig. 37. Note that this mutation processing is performed to prevent the loss of diversity.
First, the individual identification variable is initialized, that is, the individual identification variable p is set to 17 (step S500).
Then, the genetic information sequence G[1 to 20][1 to amax][1 to 2] is inherited from phase 3-1 (step S501).
Next, a loop is entered in which four mutations are generated, where p<=20 (step S502).
First, copies are made of individuals that were determined to have low movement costs in phase 2. That is, G[p][1 to amax][1 to 2] is replaced with G[p-16][1 to amax][1 to 2] (step S503). That is, when p = 20, copies (clones) of four individuals are made.
Next, numerical values from 1 to 100 are prepared, one is extracted from the number, and it is determined whether the number is 51 or greater (step S504). It is also possible to prepare the numerical values 1 and 0, and determine whether the extracted number is 1.

Here, G[p][P2][1] and G[p][P1][1] will be explained.
In step S501, it is assumed that genetic information sequences G[p-16][1 to amax][1 to 2] (i.e., G[1 to 4][1 to amax][1 to 2]) of four individuals are inherited from the genetic information sequences G[1 to 20][1 to amax][1 to 2] that make up a plurality of individuals. If the cyclic information sequence of one of these four genetic information sequences G[p-16][1 to amax][1 to 2] is the cyclic information sequence shown in Figure 38(a), for example, a cyclic loop such as that shown in Figure 38(b) is created by the cyclic information sequence, and mutation processing is performed on the cyclic information sequence.

If the determination in step S504 is No, one value is randomly selected from area numbers 1 to amax and assigned to P1 (step S505), and one value is randomly selected from area numbers 1 to amax and assigned to P2 (step S506).
Then, the process proceeds to step S507, where it is determined whether P1 and P2 are the same, whether G[p][P2][1] and P1 are the same, or whether G[p][P1][1] and P2 are the same.
If the answer is Yes in step S507, the process returns to step S506 and P2 is selected again.
If the answer is No in step S507, the process proceeds to step S508, where Ptmp is set to G[p][P2][1].
Next, the process proceeds to step S509, where an area number a that satisfies G[p][1 to amax][1]=P2 is searched for, and it is determined whether or not such an area number a has been found.
If the answer is No in step S509, m is set to -1 (step S510).
If the answer is Yes in step S509, m is set to a (step S511). In other words, if there is another area that has the area assigned to P2 as the next destination, the number a of that other area is assigned to m.
After step S510 or step S511, the process proceeds to step S512, where G[p][P1][1] is set to P2.
Then, it is determined whether this processing block is being taken for the first time (step S513).
If the answer is Yes in step S513, the process proceeds to step S514, where it is determined whether m=-1.
If the answer is No in step S513, the cyclic pattern set in G[p][P2][1] is reversed (step S515), and then the process proceeds to step S514.
If the answer is No in step S514, the process proceeds to step S516, where P1 is set to P2 and P2 is set to m, and then the process returns to step S509.
If the answer is Yes in step S514, proceed to step S517, set G[p][P2][1] to Ptmp, then proceed to step S518, invert the cyclic pattern set in G[p][P2][2], then set p to p+1 (step S519), and if P=20 is cleared, proceed to step S431 of phase 2.
That is, if the determination in step S504 is No, the inter-area route is modified in GA.
That is, the current next-generation circular route creation means comprises inter-area route modification processing means for extracting a circular route with a low travel cost from among the previous plurality of next-generation circular routes created by the previous next-generation circular route creation means, and modifying the route between the areas of the circular loop that was the basis for creating the extracted circular route, and the inter-area route modification processing means includes a first step (steps S505 and S506) of arbitrarily selecting a different first area and a different second area from each area of the above-mentioned circular loop, a second step (step S508) of recording information of the next area to be advanced to that is set as the circular information of the second area as reserved information, a third step (step S509) of searching for an area that has information of the next area to be advanced to that is set as the circular information of the second area as circular information, and determining whether or not said area exists, and a third step (step S509) of selecting the second area as the information of the next area to be advanced to that is set as the circular information of the first area. The method includes a fourth step (step S512) of setting an area, a fifth step (step S515) of reversing the cyclic pattern set in the cyclic information of the second area if this is not the first time that the processing of the fourth step is being performed, a sixth step (step S516) of changing the first area to the second area and changing the second area to the area searched in the third step after the fourth step or the fifth step if the judgment result in the third step is yes (No in step S514), and then returning to the processing of the third step, and a seventh step (steps S517 and S518) of setting the pending information as the next area to be advanced in the cyclic information of the second area and reversing the cyclic pattern set in the cyclic information of the second area if the judgment result in the third step is no (Yes in step S514) after the fourth step or the fifth step.

Next, the process of modifying the cyclic pattern when the determination in step S504 is Yes will be described.
If the determination in step S504 is Yes, one value is randomly selected from area numbers 1 to amax and assigned to P1 (step S520), and any cyclic pattern other than the existing cyclic patterns is randomly assigned to G[p][P][2] (step S521). In other words, if a cyclic pattern that is the same as the cyclic pattern already set in G[p][P][2] is randomly selected, reselections are made at random until a different cyclic pattern is found.
Thereafter, in step S519, p is set to p+1, and the process proceeds to step S431 in phase 2.
That is, the current next-generation circular route creation means is equipped with a circular pattern modification processing means that extracts a circular route with a low travel cost from the previous plurality of next-generation circular routes created by the previous next-generation circular route creation means, and modifies the circular pattern within the area of the circular loop that was the basis for creating the extracted circular route, and the circular pattern modification processing means is configured to randomly select one area from each area of the above-mentioned circular loop, and modify the circular pattern information that is the circular information for that area.

Then, in step S431, it is determined which generation the process is for.
If it is determined in step S431 that the data is "first generation (initial generation)", the process proceeds to step S432.
Furthermore, if the determination in step S431 is "another generation (other than the first generation)," then in step S453, the individual identification variable is initialized, i.e., p is set to, for example, 5, the cost management array is initialized, i.e., C[1 to amax][1 to 2] is set to 0, and the genetic information array G[5 to 20][1 to amax][1 to 2] is inherited from phase 3, and then the process proceeds to step S433.

Next, the inter-area route modification process (steps S500 to S519) in the mutation process (phase 3-2) of FIG. 37 will be described in more detail with reference to FIGS.
For example, it is assumed that a cyclic loop as shown in FIG. 46(a) is created based on the cyclic information array shown in FIG. 39 (step S503).
Then, in step S505, "2" is selected as the area number for the swapping process and assigned to P1. In this case, as shown in Figure 46(a), the state of the variables is "5" for G[P1][1] (the area to proceed to next from area 2) and "Z" for G[P1][2] (the cyclic pattern within area 2) (see Figure 39).
Next, in step S506, "3" is selected as the area number for the swapping process and assigned to P2. In this case, as shown in Figure 46(b), the state of the variables is "6" for G[P2][1] (the area to proceed to next from area 3), and "S" for G[P2][2] (the cyclic pattern within area 3) (see Figure 39).
Next, in step S508, Ptmp is set to 6 as the destination area G[P2][1] of area 3, which is P2. In other words, Ptmp is set to "6" (see FIG. 46(c)).
Then, in step S509, a search is made to see if there is an area that has the area indicated by variable P2 as its destination. If there is, the area number is entered into m (step S510). In this case, area 4 exists as an area that has area 3 indicated by variable P2 as its destination (see FIG. 39), so m is set to "4" (see FIG. 47(a)).
Next, in step S512, the destination area G[P1][1] of P1 "area 2" is set to P2. In this case, as shown in FIG. 47(b), G[P1][1] is set to "3." In this case, since P1 is "2" and G[P1][1] is "3," the inter-area route connecting area 2 and area 5 is canceled, and instead, the end point of area 2 and the start point of area 3 are connected by an inter-area route (see FIG. 47(b)).
Next, the process proceeds to step S513, and since this is the first time that step S512 has been performed, the process proceeds to step S514. In this case, m=4, not -1, so the process proceeds to step S516.
In step S516, P1 is set to P2, and P2 is set to m. In this case, as shown in Figure 48(a), P1 is set to "3" and P2 is set to "4".
Then, the process returns to step S509 to search for an area that has the area indicated by variable P2 as its destination. If an area exists, the area number is entered into m (step S510). In this case, area 5 exists as an area that has area 4 indicated by variable P2 as its destination (see FIG. 39), so m is set to "5" (see FIG. 48(b)).
Then, proceeding to step S512, the destination area G[P1][1] of P1 "area 2" is set to P2. In this case, as shown in Figure 48(c), G[P1][1] is set to "4". In this case, P1 is "3" and G[P1][1] is "4", so the inter-area route connecting area 3 and area 5 is cancelled, and instead, the end point of area 3 and the start point of area 4 are connected by an inter-area route (see Figure 48(c)).
Thereafter, the process proceeds to step S513, and since the process of step S512 is not the first time, the process proceeds to step S515. In this case, the cyclic pattern of area 3, which is P1, is inverted. That is, as shown in FIG. 49(a), the cyclic pattern of area 3 is converted from the "S" pattern (see FIG. 39) to the "S'" pattern (see FIG. 49(a)). In this case, since P1 is "3" and G[P1][1] is "4", the end point of area 3, whose cyclic pattern has been changed, and the start point of area 4 are reconnected by an inter-area route. Furthermore, since P2 is "4" and G[P2][1] is "3", the end point of area 4 and the start point of area 3, whose cyclic pattern has been changed, are reconnected by an inter-area route. Furthermore, the start point of area 3, whose cyclic pattern has been changed, and the end point of area 2 are reconnected by an inter-area route.
Then, the process proceeds to step S514. In this case, m=5, and the process proceeds to step S516.
In step S516, P1 is set to P2, and P2 is set to m. In this case, as shown in Figure 49(b), P1 is set to "4" and P2 is set to "5".
After that, the process returns to step S509 to search for an area that has the area indicated by variable P2 as its destination. If an area exists, the area number is entered into m (step S510). In this case, as shown in Figure 49(c), there is no area that has area 5 indicated by variable P2 as its destination (the inter-area route between area 2 and area 5, which was area 2's destination in Figure 47(b), has already been canceled), so the process proceeds to step S511 and m is set to -1.
Then, the process proceeds to step S512, where the destination area G[P1][1] of P1 "area 4" is set to P2. In this case, as shown in FIG. 50(a), G[P1][1] is set to "5." In this case, since P1 is "4" and G[P1][1] is "5," the inter-area route connecting area 4 and area 3 is canceled, and instead, the end point of area 4 and the start point of area 5 are connected by an inter-area route (see FIG. 50(a)).
Thereafter, the process proceeds to step S513, and since the process of step S512 is not the first time, the process proceeds to step S515. In this case, the cyclic pattern of area 4, which is P1, is inverted. That is, as shown in FIG. 50(b), the cyclic pattern of area 4 is converted from the "M" pattern (see FIG. 39) to the "M'" pattern (see FIG. 50(b)). In this case, since P1 is "4" and G[P1][1] is "5", the end point of area 4, whose cyclic pattern has been changed, and the start point of area 5 are reconnected by an inter-area route. Also, since P2 is "5" and G[P2][1] is "4", the end point of area 5 and the start point of area 4, whose cyclic pattern has been changed, are reconnected by an inter-area route. Also, the end point of area 3 and the start point of area 4 are reconnected by an inter-area route.
Then, the process proceeds to step S514. In this case, m=-1, and the process proceeds to step S517.
In step S517, G[P2][1] is set to Ptmp. In this case, as shown in Figure 50(c), G[P2][1] is set to 6 and P2 = 5, so the destination of area 5 is changed to area 6, and the end point of area 5 and the start point of area 6 are connected by an inter-area route.
Finally, the process proceeds to step S518, where the cyclic pattern of G[P2][2] is reversed. In this case, as shown in FIG. 51, G[P2][2] (= the cyclic pattern of area 5) is converted from the "Z" pattern (see FIG. 39) to the "Z'" pattern. In this case, because P1 is "4" and G[P1][1] is "5," the end point of area 4 and the start point of area 5, whose cyclic pattern has been changed, are connected by an inter-area route. Also, because P2 is "5" and G[P2][1] is "6," the end point of area 5, whose cyclic pattern has been changed, and the start point of area 6 are connected by an inter-area route.
As a result of the above, a cyclic loop that loops through all areas is created, as shown in FIG.
Thereafter, the process proceeds to step S431 of phase 2, and in step S447 a circular route is created from which the inter-area route with the highest travel cost has been deleted.

The contents of the inter-area route modification process (steps S500 to S519) in the mutation process (phase 3-2) can be summarized as follows based on FIG.
As shown in Figure 52(a), suppose the area selected at random the first time (the area set as P1) is 2, and the area selected at random the second time (the area set as P2) is 3. In this case, the inter-area routes to be swapped are the inter-area routes from each area to the next area. That is, the inter-area route from area 2 to area 5 and the inter-area route from area 3 to area 6.
Then, as shown in Figure 52(b), the destination of Area 2, which was selected the first time, is changed to Area 3, which was selected the second time. In other words, the destination of Area 2 is changed from Area 5 to Area 3. As a result, Area 2 and Area 3 are connected by an inter-area route, and the inter-area route connecting Area 2 and Area 5 disappears.
Next, as shown in Figure 52(c), the tour pattern and inter-area route of areas 5, 4, and 3 on the way from area 5, the original destination of area 2 selected the first time, to area 3 selected the second time, are reversed. In this case, since only one destination area can be specified for one area, the original inter-area route from area 3 selected the second time to the next area 6 disappears.
Finally, as shown in FIG. 52(d), a route is set from area 5, the original destination of area 2 selected the first time, to area 6, the original destination of area 3 selected the second time, and the process ends.

In other words, to summarize the contents of the inter-area route modification process (steps S500 to S519) in the mutation process (phase 3-2), the process comprises the following steps: a processing step of setting the inter-area route from the area selected the first time (the area set as P1) to the next area and the inter-area route from the area selected the second time (the area set as P2) to the next area as the inter-area routes to be replaced; a processing step of changing the destination of the area selected the first time to the area selected the second time, and eliminating the inter-area route connecting the area selected the first time with the area that was originally the destination of that area; a processing step of reversing the area tour pattern and inter-area route on the way from the area that was the original destination of the area selected the first time to the area selected the second time, and eliminating the inter-area route connecting the area selected the second time with the area that was originally the destination of that area; and a processing step of setting a route from the original destination area of the area selected the first time to the original destination area of the area selected the second time.

As described above, according to the tour route creation device of the embodiment, the tour route is updated using tour information, making it possible to create an efficient tour route for a mobile object to tour multiple areas.
In addition, by performing crossover and mutation processes on the circular loops, it is possible to add diversity to the circular loops created in subsequent generations, making it possible to create efficient circular routes.

The route creation device may have the following configuration.
That is, the circular route creation device is for recognizing position information of a plurality of areas and creating a circular route for a mobile body to travel around the plurality of areas, and includes a circular loop creation means for creating a circular loop that goes around each area, a movement cost calculation means for calculating the movement cost when a mobile body travels along the route of the created circular loop, and a circular route creation means for deleting the inter-area route with the highest movement cost from among the inter-area routes that form the created circular loop, and creating a circular route that goes around each area, with the area that connected the end of the deleted inter-area route as the start area of the circular route and the area that connected the start end of the deleted inter-area route as the goal area of the circular route. In a circular route creation device having a circular route creation means for creating a circular route, the circular loop creation means may be configured to include initial circular loop creation means for creating an initial circular loop by setting circular information for each area, and circular loop update means for creating a circular loop by changing the circular information of the initial circular loop, and the circular route creation means may be configured to include determination means for comparing the travel cost of a current circular route created based on the current circular loop created by the circular loop update means with the travel cost of a previous circular route created based on the previous circular loop created by the circular loop update means, and for keeping the circular route with the smaller travel cost.
According to the tour route creation device, the tour information described above is used to update the tour loop, and tour routes with lower travel costs are successively retained, making it possible to create efficient tour routes for a mobile object to tour multiple areas.

Furthermore, according to the circular route creation device of the embodiment, the next generation circular route creation means performs an inter-area route modification process (steps S500 to S519) in the mutation process, thereby making it possible to add diversity to the modified (updated) circular loop, thereby making it possible to create an efficient circular route.
Furthermore, by the next generation circular route creation means performing a circular pattern modification process (steps S520, S521) as a mutation process, it is possible to add diversity to the modified (updated) circular loop, thereby enabling the creation of efficient circular routes.

In addition, by changing the number of generations, it is possible to provide a tour route creation device that can realize a tour route creation process that meets requests such as shortening the time required to obtain a tour route or obtaining a more efficient tour route.

In addition, in the embodiment, eight types of patrol patterns within an area are exemplified, but it is also possible to use, for example, only the first and second patterns, only the third and fourth patterns, only the fifth and sixth patterns, or only the seventh and eighth patterns.

Furthermore, in the embodiment, an example has been shown in which the floor surface within a building is moved as the area (movement target region), but the area may also be a surface such as a road or vacant lot outside the building.
Furthermore, obstacle B may be an obstacle other than a pillar, such as a partition wall, fixed equipment, or heavy object.
Furthermore, the XY coordinate information of the area indicating the position of the area and the XY coordinate information of the obstacle indicating the position of the obstacle do not have to be the XY coordinate information of the corners, but may be any XY coordinate information that can confirm the position of the area or the position of the obstacle.

Furthermore, the multiple areas (movement target areas) may be multiple adjacent areas as shown in Figure 12, or multiple areas spaced apart from each other as shown in Figure 37, etc.

According to the patrol route creation device of the embodiment, for example, when a floor inspection is performed using a mobile body 1 equipped with an imaging means (camera) to photograph the floor surface, an efficient patrol route can be provided for the mobile body 1 to patrol multiple areas, thereby making it possible to perform an efficient floor inspection.
Furthermore, even when the mobile body 1 is made to patrol a plurality of areas for purposes other than floor surface inspection, an efficient patrol route can be provided for the mobile body 1 to patrol a plurality of areas.

In addition, in the above example, a TS (total station) with an automatic tracking function was used as the movement information acquisition means for acquiring actual movement information of a mobile object and transmitting it to the mobile object in the mobile object movement control system. However, the movement information acquisition means may also be means other than a TS, such as a mobile object self-positioning system such as a GPS or laser positioning system.

1. Moving object.

Claims (10)

A travel route creation device for recognizing position information of a plurality of target areas for movement and creating a travel route for a mobile object to travel through the plurality of target areas for movement, comprising:
a cyclic loop creating means for creating a cyclic loop that goes around each of the movement target areas;
a travel cost calculation means for calculating a travel cost when a mobile object travels along the route of the created circular loop;
a circular route creation means for creating a circular route that goes around each of the movement target areas by deleting the route between the movement target areas that has the highest movement cost from among the routes between the movement target areas that form the created circular loop, and setting the movement target area to which the route end of the deleted route between the movement target areas is connected as the start area of the circular route, and setting the movement target area to which the route start point of the deleted route between the movement target areas is connected as the goal area of the circular route;
the cyclic loop creating means comprises an initial generation cyclic loop creating means and a subsequent generation cyclic loop creating means for creating a cyclic loop by setting cyclic information for each movement target area;
the tour route creation means includes an initial generation tour route creation means and a later generation tour route creation means;
The initial generation cyclic loop creating means creates a plurality of cyclic loops;
the initial generation circulatory route creation means changes the circulatory information for each movement target area for each of the initial generation circulatory loops created by the initial generation circulatory loop creation means, thereby creating a plurality of initial generation circulatory routes;
the later-generation tour loop creation means extracts some initial-generation tour routes with low travel costs from among the plurality of initial-generation tour routes, and creates a later-generation tour loop using tour information of the extracted initial-generation tour routes;
the next-generation circular route creation means changes the circular information for each movement target area for each next-generation circular loop created by the next-generation circular loop creation means to create a next-generation circular route;
A travel route creation device characterized in that the patrol information is combined information consisting of information on the patrol pattern within the own target travel area set for each target travel area and information on the next target travel area to proceed to. The number of generations in the subsequent generations is multiple,
the current next-generation circulatory route creation means changes the circulatory information for each movement target area for each previous next-generation circulatory loop created by the previous next-generation circulatory loop creation means, and creates the current next-generation circulatory route;
2. The tour route creation device according to claim 1, wherein the subsequent-generation tour route creation means determines, as the tour route, one of the plurality of tour routes created as the final generation that has the smallest travel cost. The route creation device of claim 2, characterized in that the current next-generation route creation means defines one or more routes with the lowest travel cost from among the previous multiple next-generation loops created by the previous next-generation loop creation means as parents, and creates the current next-generation route by inheriting the route information of the parent route. The tour route creation device of claim 3, characterized in that, if, at the stage of creating the current next-generation tour route, there remain two or more movement target areas for which tour information has not yet been set, and the information for the next movement target area, which is the tour information to be set for the movement target area for which tour information has not yet been set, cannot be inherited from the parent, the current next-generation tour route creation means arbitrarily selects the next movement target area to be set for the movement target area for which tour information has not yet been set from among the movement target areas for which tour information has not yet been set. The travel route creation device described in claim 4, characterized in that the information of the next target area, which is the travel information to be set for a travel target area for which no travel information has yet been set, cannot be inherited from the parent when the information of the next target area, which is the parent travel information to be inherited by a travel target area for which no travel information has yet been set, is the travel target area for which travel information was first set when creating the current next-generation travel route, and when the information of the next target area, which is the parent travel information to be inherited by a travel target area for which no travel information has yet been set, has already been used in creating the current next-generation travel route. The tour route creation device of claim 3, characterized in that, when the current next-generation tour route creation means determines that there is only one remaining target area for which tour information has not yet been set during the stage of creating the current next-generation tour route, the information on the next target area for which tour information has been set, which is the tour information for that remaining target area, is set as the target area for which tour information was first set when creating the current next-generation tour route. the current next-generation circular route creation means comprises a movement target area inter-route modification processing means for extracting a circular route with a low movement cost from the previous plurality of next-generation circular routes created by the previous next-generation circular route creation means, and modifying the route between the movement target areas of the circular loop that was the basis for creating the extracted circular route;
The inter-movement target area route modification processing means comprises:
a first step of arbitrarily selecting a first movement target area and a second movement target area from among the movement target areas of the cyclic loop;
a second step of recording information of the next moving target area set as patrol information of the second moving target area as pending information;
a third step of searching for a movement target area having, as its circulating information, information on the next movement target area set as the circulating information of the second movement target area, and determining whether or not the movement target area exists;
a fourth step of setting a second target area as information on a next area to be moved to, which is set in the patrol information of the first target area;
a fifth step of reversing the circulating pattern set in the circulating information of the second movement target area when the processing of the fourth step is not performed for the first time;
a sixth step of changing the first movement target area to a second movement target area after the fourth step or the fifth step if the determination result in the third step is yes, and then returning to the processing of the third step after changing the second movement target area to the movement target area found in the third step;
A travel route creation device as described in any one of claims 2 to 6, characterized in that if the judgment result in the third step is negative, after the fourth step or after the fifth step, the pending information is set as the next travel target area in the travel information of the second travel target area, and the travel pattern set in the travel information of the second travel target area is reversed. The circular route creation device of any one of claims 2 to 6, characterized in that the current next-generation circular route creation means includes a circular pattern modification processing means that extracts a circular route with a low travel cost from the previous multiple next-generation circular routes created by the previous next-generation circular route creation means and modifies the circular pattern within the movement target area of the circular loop that was the basis for creating the extracted circular route, and the circular pattern modification processing means randomly selects one movement target area from each movement target area of the circular loop and modifies the circular pattern information, which is the circular information of that movement target area. A travel route creation device for recognizing position information of a plurality of target areas for movement and creating a travel route for a mobile object to travel through the plurality of target areas for movement, comprising:
a cyclic loop creating means for creating a cyclic loop that goes around each of the movement target areas;
a travel cost calculation means for calculating a travel cost when a mobile object travels along the route of the created circular loop;
a circular route creation means for creating a circular route that goes around each of the movement target areas by deleting the route between the movement target areas that has the highest movement cost from among the routes between the movement target areas that form the created circular loop, and setting the movement target area to which the route end of the deleted route between the movement target areas is connected as the start area of the circular route, and setting the movement target area to which the route start point of the deleted route between the movement target areas is connected as the goal area of the circular route;
The means for creating a circular loop is
an initial cyclic loop creating means for creating an initial cyclic loop by setting cyclic information for each movement target area;
a cyclic loop update means for creating a cyclic loop in which cyclic information of the initial cyclic loop is changed;
The means of creating a tour route are:
a determining means for comparing a travel cost of a current circular route created based on a current circular loop created by the circular loop update means with a travel cost of a previous circular route created based on a previous circular loop created by the circular loop update means, and selecting a circular route with a smaller travel cost;
A travel route creation device characterized in that the patrol information is combined information consisting of information on the patrol pattern within the own target travel area set for each target travel area and information on the next target travel area to proceed to. The movement target area is an area partitioned based on XY coordinate information,
The cyclic pattern within the movement target area is an X-direction cyclic pattern that moves zigzag along the X-axis, or a Y-direction cyclic pattern that moves zigzag along the Y-axis,
The X-direction cyclic patterns are a first pattern in which the movement start position is the position of the minimum X coordinate value and the maximum Y coordinate value, a second pattern in which the movement start position is the position of the minimum X coordinate value and the minimum Y coordinate value, a third pattern in which the movement start position is the position of the maximum X coordinate value and the maximum Y coordinate value, and a fourth pattern in which the movement start position is the position of the maximum X coordinate value and the minimum Y coordinate value,
10. The device for creating a travel route according to claim 1, wherein the Y-direction travel pattern is a fifth pattern in which the start position of the travel is a position with a minimum X coordinate and a maximum Y coordinate; a sixth pattern in which the start position of the travel is a position with a maximum X coordinate and a maximum Y coordinate; a seventh pattern in which the start position of the travel is a position with a minimum X coordinate and a minimum Y coordinate; and an eighth pattern in which the start position of the travel is a position with a maximum X coordinate and a minimum Y coordinate.