Effectively Deploying Limited Security Resources--Fujitsu Develops AI Technology that Uses Game Theory

Security measures necessary in crowded places

Sports, concerts, amusement parks ...... a variety of events that attract a lot of people are held on holidays across Japan. According to a survey, Hiroshima Prefecture was ranked number one as the most popular tourist destination during Golden Week in 2016. Hiroshima Prefecture has popular sightseeing spots, such as Itsukushima Shrine and the Atomic Bomb Dome, and attracts more than 1.6 million tourists every year. Following Hiroshima Prefecture, Miyagi Prefecture and Fukuoka Prefecture were ranked number two and three respectively. Other than these prefectures, sightseeing spots in many areas were also crowded with tourists during Golden Week (*1)

Security measures, including crowd security and event security, are essential for events where many people gather. However, it is often not possible to completely monitor intrusion or escape routes of criminals with limited security resources. So it is necessary to effectively deploy security personnel to minimize anticipated damage, but the formulation of security plans has relied on the experience of experts and intuition. In recent years there has been a focus on the formulation of security plans utilizing artificial intelligence (AI).

(*1) Survey by Rakuten Travel http://travel.rakuten.co.jp/ranking/special/gw/

Effectively deploying limited security resources using game theory

Fujitsu Laboratories Ltd. and the University of Electro-Communications today announced the development of a technology that allows effective deployment of limited security resources according to the movement and psychological characteristics of criminals using AI. The technology applies game theory (*2), as a mathematical theory, which has attracted much attention in the AI field in recent years. In particular, technology which treats the criminals and the security side as opposing decision makers is called 'security game.' Fujitsu Laboratories has now developed technology that can rapidly formulate security plans for large scale road networks as a solution for the city-scale road network security problem—which is one of the problems tackled in security games. In addition, together with the University of Electro-Communications, it has provided theoretical support for this technology.

The city-scale road network security problem has the goal of catching criminals who are attempting to reach a target location by locating a limited number of checkpoints on the road network.

It is necessary to find the best solution by taking into account all movement patterns on both the criminal and security sides, however, the number of their movement patterns increases exponentially in response to the scale of the road network, which makes calculations difficult.

The technology developed makes it possible to reduce the number of movement patterns on the security side by limiting the number of candidate checkpoint positions. In addition, it is also possible to greatly reduce the number of movement patterns on the criminal's side by focusing only on the routes through the limited candidate checkpoints. This network contraction technology significantly reduced the processing volume for solving the problem. Fujitsu Laboratories also developed an algorithm that improves the solution by automatically selecting candidate checkpoints to be added, and confirmed that this algorithm was able to find the optimal solution for over 99% of problem scenarios in a simulation using a mock network of 30,000 roads.

(*2) Game theory involves mathematically capturing the behavior of groups in situations involving conflicting interests. It develops game players' behavioral patterns into models. This theory is applied to the analysis of economic phenomena or military simulations.

Formulating a security plan for Tokyo's 23 wards in just five minutes

Compared with existing methods, this technology makes it possible to find the optimal security plan 20 times faster, on average, for a road network with 100 nodes (intersections), and 500 times faster, on average, with 200 nodes. Even for a road network with 100,000 nodes, this technology finds a solution in only a few minutes. In a simulation deploying checkpoints at 50 locations in the 200,000 node road network covering Tokyo's 23 wards, an ordinary PC was able to successfully generate a security plan in five minutes.

This technology makes it possible to provide interactive planning support for security planning experts. Thus the power of AI contributes to the safe and secure social lives of people. Fujitsu Laboratories aims to commercialize this technology as part of Fujitsu's AI technology, Human Centric AI Zinrai ("Zinrai"), during fiscal 2017.