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

An information processing device, comprising:

• a deadlock risk level calculator configured to calculate a deadlock risk level of occurrence of a deadlock for mobile vehicles traveling in a traveling area,
• the traveling area including a plurality of traveling paths and a plurality of intersections connecting the traveling paths,
• the mobile vehicles being incapable of pass each other in the traveling paths,
• the deadlock being a state in which at least one mobile vehicle among the mobile vehicles cannot move to any intersection among the intersections;
• and
• a display configured to display the deadlock risk level,
• wherein the deadlock risk level calculator calculates the deadlock risk level based on positions and directions of the mobile vehicles traveling in the traveling area at a certain time.

A deadlock detection method, comprising:

• selecting a mobile vehicle or a combined mobile vehicles from among mobile vehicles, based on:
• a traveling path configuration graph including a plurality of edges representing the traveling paths and a plurality of vertices representing intersections connecting the traveling paths, and mobile vehicles being not allowed to pass each other in the traveling paths;
• and,
• first state information including a state of mobile vehicles associated with the traveling path configuration graph, the state including positions and directions of the mobile vehicles,
• going forward the selected mobile vehicle or the selected combined mobile vehicles to go forward on the traveling path configuration graph and
• 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,
• iterating a process of the selecting, the going and combining;
• determining that a deadlock occurs if not all the mobile vehicles have been combined by the combining calculator, and
• determining that no deadlock occurs if all the mobile vehicles have been combined,
• wherein the deadlock is a state in which at least one mobile vehicle unable to go forward to any intersection exists.

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:

• selecting a mobile vehicle or combined mobile vehicles from among mobile vehicles, based on:
• a traveling path configuration graph including a plurality of edges representing the traveling paths and a plurality of vertices representing intersections connecting the traveling paths, and mobile vehicles are not allowed to pass each other in the traveling paths,
• first state information including a state of mobile vehicles associated with the traveling path configuration graph, the state including positions and directions of the mobile vehicles,
• going forward the selected mobile vehicle or the selected combined mobile vehicles to go forward on the traveling path configuration graph and
• 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,
• repeating a process of the selecting, the going and combining;
• determining that a deadlock occurs if not all the mobile vehicles have been combined by the combining calculator, and
• determining that no deadlock occurs if all the mobile vehicles have been combined,
• wherein the deadlock is a state in which at least mobile vehicle unable to go forward to any intersection exists.