|
|
|
|
|
|
Mathematical AI technology works to derive optimal checkpoint deployment patterns for a road network of 200,000 nodes in just five minutes
Fujitsu Laboratories Ltd.,University of Electro-Communications |
KAWASAKI, Japan, May 10, 2016 - (JCN Newswire) - 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.
 | | 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. |
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. 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.
Now, 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.
Fujitsu Laboratories aims to commercialize this technology as part of Fujitsu Limited's AI technology, Human Centric AI Zinrai ("Zinrai"), during fiscal 2017. The University of Electro-Communications plans to proceed with the expansion of this technology beyond city-scale road networks.
Details of this technology will be announced at the International Conference on Autonomous Agents and Multiagent Systems 2016 (AAMAS 2016), one of the world's largest conferences in the AI and multiagent field, to be held in Singapore on May 9th.
Development Background
Security problems at places where people gather, such as cities and airports, could ideally be solved if all paths used by criminals could be sealed off, but because this is difficult to achieve with limited security resources in the vast majority of cases, there is a need for effective deployment of limited security resources according to the movement and psychological characteristics of criminals. The formulation of security plans has historically relied on the experience of experts and intuition, but in recent years, when there has been a demand for advanced security to face new threats, such as organized crime, the use of AI to formulate security plans has been attracting attention. In particular, technology using game theory, which treats both the criminal's side and the security side as opposing decision makers, called security games, is beginning to come into practical use as a tool to help experts make decisions.
Issues
The city-scale road network security problem is a security game problem with the goal of catching criminals at such locations as checkpoints when they are trying to either reach their target or escape. However, the number of movement patterns for the criminal (paths from the intrusion point to the target of their attack) grows exponentially in response to the scale of the road network (the number of roads). This has meant that it was previously impossible to solve problems with large numbers of nodes (intersections), representing the road network of a city, in a realistic amount of processing time, making application to real-world scenarios difficult.
About the Technology
Fujitsu Laboratories has now developed technology to solve this problem of city-scale road network security-one security game problem-that can rapidly formulate security plans for large scale road networks. In addition, together with the University of Electro-Communications, it has provided theoretical support for this technology.
Key features of the technology are as follows.
1. Network contraction technology
Fujitsu Laboratories has now developed a "contraction" technology that greatly 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(1), 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. In addition, by combining locations in the road network where security personnel are not deployed, it is also possible to greatly reduce the number of movement patterns on the criminal's side (Figure 1). The University of Electro-Communications and Fujitsu Laboratories have jointly demonstrated that with this technology the security effectiveness of optimal plans developed on the post-contraction road network is theoretically identical to that of optimal plans made on the pre-contraction road network. This successfully enabled great reductions in processing volume.
2. 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. By then focusing on nodes whose expected damage values have now significantly increased and adding roads that are checkpoint placement candidates, it can calculate the optimal combination in the same way. By repeating this process, approximately optimal solutions can be quickly calculated. In a simulation using a mock network of 30,000 roads, Fujitsu Laboratories and the University of Electro-Communications were able to confirm that this algorithm was able to find the optimal solution, where no other solution had higher security effectiveness, for over 99% of problem scenarios.
Effects
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. 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. 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.
Future Plans
Fujitsu Laboratories will work on bringing into practical implementation the formulation of security plans using mathematics technology. In addition, it will expand the areas in which this security plan formulation technology can be applied. Fujitsu Laboratories aims to commercialize these technologies as part of Zinrai, during fiscal 2017. The University of Electro-Communications plans to proceed with the expansion of this technology beyond city-scale road networks.
(1) Security effectiveness
Effectiveness in reducing the expected value of damage from an attack.
Contact:
Fujitsu Limited
Public and Investor Relations
Tel: +81-3-3215-5259
URL: www.fujitsu.com/global/news/contacts/
Fujitsu Laboratories Ltd.
ICT Systems Laboratories
Server Technologies Lab
E-mail: Retimer_ISSCC2015@ml.labs.fujitsu.com
Topic: Press release summary
Source: Fujitsu Ltd
Sectors: Electronics, Cloud & Enterprise, IT Individual
https://www.acnnewswire.com
From the Asia Corporate News Network
Copyright © 2024 ACN Newswire. All rights reserved. A division of Asia Corporate News Network.
|
|
|
|
|
|
|
|
