Plans To Commercialize This Technology As Part of Its AI Technology

Fujitsu Laboratories Ltd. and the University of Electro-Communications today announced the development of a high-speed algorithm that uses mathematical game theory as an artificial intelligence technology to aid in the development of security planning.

This will work to solve city-scale road network security problems, such as where best to position checkpoints when trying to catch a criminal, said the company.


For security measures at locations where people gather, it is often not possible to completely seal off all intrusion or escape routes with limited security resources, so it is necessary to effectively deploy security personnel and to minimize anticipated damage, said Fujitsu.

The formulation of security plans has relied on the experience of experts and intuition, but in recent years there has been a focus on game theory, which mathematically describes both offence and defense, as a technology to support expert decision-making. However, it has been difficult to apply game theory to a city-scale security problem of catching criminals at checkpoints in real-world cities because the processing volume expands exponentially with the scale of the road network.

Using Fujitsu Laboratories’ proprietary network contraction technology, Fujitsu Laboratories and the University of Electro-Communications have developed an algorithm to rapidly solve city-scale road network security problems. Compared with previous technology, this makes it possible to find the theoretically optimal security plan 20 times faster, on average, for a 100-node problem, and 500 times faster, on average, for a 200-node problem. For 200,000-node problems, on the scale of Tokyo’s 23 wards, where formulating a plan would have taken several days with previous technology, this technology can generate a security plan in approximately five minutes, enabling interactive planning support.

Key features:

  • Network contraction technology

Fujitsu ‘s “contraction” technology simplifies a network by using calculations in line with candidate checkpoint positions. A road network has locations where a checkpoint would have high security effectiveness, and other locations where it would be low. Given this, it is possible to reduce, or “contract,” the number of movement patterns on the security side by eliminating from candidate locations those with low security effectiveness.

  • High speed, high accuracy algorithm

The newly developed algorithm first selects from checkpoint placement candidates based on the nodes with the highest likelihood of sustaining damage from criminal activity, and then rapidly calculates the optimal arrangement of checkpoint locations and the density of checkpoints in an area based on minimizing the total expected damage value using the network contraction technology.

  • Effect

Compared with existing methods, this technology is able to find the optimal security plan at speeds that are 20 times faster, on average, with 100 nodes, and 500 times faster, on average, with 200 nodes, according to Fujitsu. Even in cases of road networks on the 100,000 node scale, for which existing methods might find a solution in a few days, with this technology a solution can be found in minutes, the company said. In a simulation deploying checkpoints at 50 locations in the 200,000 node road network that includes Tokyo’s 23 wards, an ordinary PC was able to successfully generate a security plan in five minutes, added Fujitsu.