Deadlock detection device, information processing device, deadlock detection method, and non-transitory computer readable medium

A deadlock detection method, comprising:

• storing, in a hardware storage, a traveling path configuration graph including a plurality of edges representing traveling paths and a plurality of vertices representing intersections connecting the traveling paths, and mobile vehicles being allowed to move in a traveling area including the traveling paths and the intersections but being not allowed to pass each other in the traveling paths;
• acquiring a plurality of first state information each including a state of the mobile vehicles at a first timing in the traveling area, the state including positions and directions of the mobile vehicles, the acquired state of the mobile vehicles being associated with the traveling path configuration graph;
• selecting a mobile vehicle or combined mobile vehicles from among the mobile vehicles based on each of the first state information;
• going forward the selected mobile vehicle or the selected combined mobile vehicles along the edges of the traveling path configuration graph under a rule that the mobile vehicles are not allowed to pass each other in the edges;
• combining the selected mobile vehicle or the selected combined mobile vehicles to another mobile vehicle or another combined mobile vehicles at a back of the other mobile vehicle or the other combined mobile vehicles on the traveling path configuration path;
• iterating a process of the selecting, the going and combining;
• determining that a deadlock occurs if not all the mobile vehicles have been combined on the traveling path configuration path;
• determining that no deadlock occurs if all the mobile vehicles have been combined on the traveling path configuration path, wherein the deadlock is a state in which at least one mobile vehicle unable to go forward to any intersection exists;
• creating a plurality of second state information indicating a plurality of next states of mobile vehicles transitionable from the state of mobile vehicles in the first state information if the deadlock is determined to not occur among the plurality of first state information;
• iterating the process of the selecting, the going and the combining for each of the second state information to determine whether the deadlock occurs;
• not creating the second state information indicating a plurality of next states of mobile vehicles transitionable from the state of mobile vehicles in the first state information if the deadlock is determined to occur among the plurality of first state information;
• and
• operating the plurality of mobile vehicles under a traveling plan created based on the first state information for which the deadlock is determined to not occur and the second state information for which the deadlock is determined to not occur.

A non-transitory computer readable medium having a computer program stored therein which when executed by a computer, causes the computer to perform processes comprising:

• reading out, from a hardware storage, a traveling path configuration graph including a plurality of edges representing traveling paths and a plurality of vertices representing intersections connecting the traveling paths, and mobile vehicles being allowed to move in a traveling area including the traveling paths and the intersections but being not allowed to pass each other in the traveling paths;
• acquiring a plurality of first state information each including a state of the mobile vehicles at a first timing in the traveling area, the state including positions and directions of the mobile vehicles, the acquired state of the mobile vehicles being associated with the traveling path configuration graph;
• selecting a mobile vehicle or combined mobile vehicles from among the mobile vehicles based on each of the first state information;
• going forward the selected mobile vehicle or the selected combined mobile vehicles along the edges of the traveling path configuration graph under a rule that the mobile vehicles are not allowed to pass each other in the edges;
• combining the selected mobile vehicle or the selected combined mobile vehicles to another mobile vehicle or another combined mobile vehicles at a back of the other mobile vehicle or the other combined mobile vehicles on the traveling path configuration path;
• iterating a process of the selecting, the going and combining;
• determining that a deadlock occurs if not all the mobile vehicles have been combined on the traveling path configuration path;
• determining that no deadlock occurs if all the mobile vehicles have been combined on the traveling path configuration path, wherein the deadlock is a state in which at least one mobile vehicle unable to go forward to any intersection exists;
• creating a plurality of second state information indicating a plurality of next states of mobile vehicles transitionable from the state of mobile vehicles in the first state information if the deadlock is determined to not occur among the plurality of first state information;
• iterating the process of the selecting, the going and the combining for each of the second state information to determine whether the deadlock occurs;
• not creating the second state information indicating a plurality of next states of mobile vehicles transitionable from the state of mobile vehicles in the first state information if the deadlock is determined to occur among the plurality of first state information;
• and
• operating the plurality of mobile vehicles under a traveling plan created based on the first state information for which the deadlock is determined to not occur and the second state information for which the deadlock is determined to not occur.