GAME THEORY MODEL FOR PATROLLING AN AREA THAT ACCOUNTS FOR DYNAMIC UNCERTAINTY

• US 20140279818A1
• Filed: 03/17/2014
• Published: 09/18/2014
• Est. Priority Date: 03/15/2013
• Status: Abandoned Application

• Current Assignee: University of Southern California
• Original Assignee: University of Southern California
• Inventors: Yin, Zhengyu, Tambe, Milind, Kraus, Sarit, Jiang, Albert Xin, Zhang, Chao
• Application Number:
  US14/216,449
• Publication Number:
  US 20140279818A1
• Time in Patent Office: Days
• US Class Current: 706/52
• CPC Class Codes: G06N 5/048 Fuzzy inferencing
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem

Abstract

Game theory models may be used for producing a strategy and schedule for patrolling an area like a rail transportation system. In some instances, the model may account for events that cause a patrol unit to deviate from a patrol schedule and route. For example, a patrol schedule may be generated for one or more patrol units using a Bayesian Stackelberg game theory model based on a map of the public transportation system, a schedule of the transports, a list of the one or more patrolling units, a probability distribution for the occurrence of the passenger not paying to ride the transports, a list of the one or more possible events that would delay the patrol units, and a probability distribution for the occurrence of the one or more possible events that would delay the patrolling units represented by a Markov-decision process.

Claims

1. A non-transitory, tangible, computer-readable storage medium containing a program of instructions that cause a computer system running the program of instructions to:

receive a map of a public transportation system to be patrolled, a schedule of transports for the public transportation system, a list of one or more patrolling units available for patrolling the public transportation system, a probability distribution for an occurrence of a passenger not paying to ride the transports of the public transportation system, a list of one or more possible events that would delay the patrolling units during a patrol, a probability distribution for an occurrence of the one or more possible events that would delay the patrolling units; and

generate a patrol schedule for each patrolling unit using a Bayesian Stackelberg game theory model based on the map of the public transportation system, the schedule of the transports, the list of the one or more patrolling units, the probability distribution for the occurrence of the passenger not paying to ride the transports, the list of the one or more possible events that would delay the patrolling units, the probability distribution for the occurrence of the one or more possible events that would delay the patrolling units, wherein the probability distribution for the occurrence of the one or more possible events that would delay the patrolling units is represented by a Markov-decision process.

2. The medium of claim 1, wherein the probability distribution for the occurrence of the one or more possible events that would delay the patrolling units include at least one of:

missing a scheduled transport, responding to a call to a different location in the transportation system, issuing a citation for an illegal behavior, and responding to an emergency.

3. The medium of claim 1, wherein the schedule of the transports incorporates a probability of delays of the transports.

4. The medium of claim 1, wherein the probability distribution for the occurrence of the passenger not paying to ride the transports is dependent on a time of a day and the day of the week.

5. The medium of claim 1, wherein the probability distribution for the occurrence of the one or more possible events that would delay the patrolling units is dependent on a time of a day and the day of the week.

6. The medium of claim 1, wherein the public transportation system is a passenger train system.

7. A non-transitory, tangible, computer-readable storage medium containing a program of instructions that cause a computer system running the program of instructions to:

receive a map of an area to be patrolled, a list of patrolling units available for patrolling the area, a description of maneuverability of each of the patrolling units, a description of a possible attack or attacks, a list of routes for an attacker corresponding to each possible attack, a probability distribution for each possible attack and corresponding routes for the attacker, a list of one or more possible events that would delay the patrolling units during a patrol, a probability distribution for an occurrence of the one or more possible events that would delay the patrolling units; and

generate a patrol schedule for each patrolling unit using a Bayesian Stackelberg game theory model based on the map of the area, the list of patrolling units, the description of maneuverability of each of the patrolling units, the description of the possible attack or attacks, the list of routes for the attacker corresponding to each possible attack, the probability distribution for each possible attack and corresponding routes for the attacker, the list of the one or more possible events that would delay the patrolling units, the probability distribution for the occurrence of the one or more possible events that would delay the patrolling units, wherein the probability distribution for the occurrence of the one or more possible events that would delay the patrolling units is represented by a Markov-decision process.

8. The medium of claim 7, wherein the Bayesian Stackelberg game theory model allows for the attacker to observe the patrolling units.

9. The medium of claim 7, wherein the one or more possible events that would delay the patrolling units include at least one of:

missing a scheduled transport along a patrol schedule, responding to a call to a different location in the system, and responding to an emergency.

10. The medium of claim 7, wherein the area is an outdoor area and the attacker includes at least one of:

a poacher, an illegal fisherman, or a person illegally cutting down trees.