This research webpage needs to be updated. Our main research directions include (please see our publications):
Computational game theory and its application to security
Game Theory for Security
Terrorism is a major security issue to countries all around the world. In the post 9/11 world, terrorism has become more severe and more sophisticated in terms of the planning and the technologies involved. High profile infrastructures and important public events are being increasingly targeted, calling for enhanced protection with more efficient use of limited security resources.
Pioneered by Teamcore research group, a new research direction, known as security games, adopts a game-theoretic perspective to assist with developing efficient algorithms for computing optimal allocation of security resources against strategic adversaries, and then analyzed and solved with the help of computational techniques. Our research focus includes security games with
dynamic payoffs, dealing with uncertainties in security games, and application of security games in cyber security and wildlife protection.
Understanding spatiotemporal dynamics of adversarial behavior is a critical but unaddressed aspect of the security game. In real life, adversaries may roam around, identify and attack various types of establishment in different locations. The targets may themselves also be moving entities with changing values. Their works leave a trace of activities in both spatial and temporal dimensions which should be duly captured and analyzed. We consider such dynamics. Doing so enables us to exploit the ability to dynamically allocate, reallocate and transfer resources.
Standard game-theoretic assumptions, such as perfect rationality and complete information, suffer from being too idealized for practical uses. This is unfortunately also true for many existing security game models, which unrealistically assumed well-shaped adversaries who are rational, observant, informative, and equip infinite computation capabilities. In reality, human adversaries rarely exhibit these features. Ignoring real human behaviors leads to very poor performance of our solutions. This has motivated us to consider more realistic settings of security games, such as finite observation and limited computational capability.
Over the past decade, the amount of money spent on cyber defense has exploded from less than $10 billion to roughly $70 billion. The classic methods failed to defend against unknown threats such as those based on zero-day vulnerabilities or new threats and cannot provide the necessary defense solution. Artificial Intelligence (AI) has been increasingly playing an important role in cyber crime detection and prevention. We combine game theoretic reasoning and machine learning approaches to efficiently identify potential risks with consideration of human behavior and reasoning about how human being interact with cyber systems.
Qingyu Guo,Bo An, Yevgeniy Vorobeychik, Long Tran-Thanh, Jiarui Gan, Chunyan Miao. Coalitional security games. Proceedings of the 15th International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS'16), pp.159-167. [PDF] [Appendix]
Yue Yin, Bo An. Efficient resource allocation for protecting coral reef ecosystems. Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI'16), accepted. [PDF]
Qingyu Guo, Bo An, Yair Zick, Chunyan Miao. Optimal interdiction of illegal network flow. Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI'16), accepted. [PDF] [Appendix]
Yue Yin, Yevgeniy Vorobeychik, Bo An, Noam Hazon. Optimally protecting elections. Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI'16), accepted. [PDF]
Mengchen Zhao, Bo An, Christopher Kiekintveld. Optimizing personalized email filtering thresholds to mitigate sequential spear phishing attacks. Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI'16), pp.658-665, 2016. [PDF] [Appendix]
Zhen Wang, Yue Yin, Bo An. Computing optimal monitoring strategy for detecting terrorist plots. Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI'16), pp.637-643, 2016. [PDF] [Appendix]
Fei Fang, Thanh H. Nguyen, Rob Pickles, Wai Y. Lam, Gopalasamy R. Clements, Bo An, Amandeep Singh, Milind Tambe, Andrew Lemieux. Deploying PAWS: Field optimization of the protection assistant for wildlife security. Proceedings of the 28th Annual Conference on Innovative Applications of Artificial Intelligence (IAAI'16), pp.3966-3973, 2016. Winner of Deployed Innovative Application Award. [PDF]
Yue Yin, Haifeng Xu, Jiarui Gan, Bo An, Albert Jiang. Computing optimal mixed strategies for security games with dynamic payoffs. Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI'15), pp.681-687, 2015. [PDF] [Appendix]
Jiarui Gan, Bo An, Yevgeniy Vorobeychik. Security games with protection externality. Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI'15), pp.914-920, 2015. [PDF][Appendix]
Yue Yin, Bo An, Manish Jain. Game-theoretic resource allocation for protecting large public events. Proceedings of the 28th AAAI Conference on Artificial Intelligence (AAAI'14), pp.826-834, 2014. [PDF]
Milind Tambe, Albert Jiang, Bo An, Manish Jain. Computational game theory for security: Progress and challenges. AAAI Spring Symposium on Spring Symposium on Applied Computational Game Theory, March 2014. [PDF]
Bo An, Matthew Brown, Yevgeniy Vorobeychik, Milind Tambe. Security games with surveillance cost and optimal timing of attack execution. Proceedings of the 12th International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS'13), pp.223-230, 2013. [PDF]
Computational sustainability is an interdisciplinary field aiming at applying computational techniques to address environmental, economic, and social problems arising from the needs of sustainable development. While human beings play a central role in many such problems, how to coordinate human-human and human-environment relations become the key topic to focus on and is where our interest lies. Our projects include policy-making and planning of the large scale decentralized transportation systems, e.g., pricing of the taxi market, planning (placement and pricing) of the electric vehicle system.
Taxi system is a highly decentralized transportation system with a large number of taxi drivers. Unlike other modes of public transportation such as bus and metro, taxis do not follow fixed timetable or routes. Taxi drivers work for their individual profits regardless of the system-level efficiency, making taxi systems inefficient and hard to optimize. One example is the peak-time dilemma in Beijing taxi market where taxi drivers avoid working in peak hours because of terrible traffic condition at this period.
To properly manage and regulate taxi market requires in-depth understanding and consideration of taxi drivers' behavior. For this reason, we focus on using game-theoretic approaches to building more realistic models that well capture taxi drivers' rationality, autonomy, profit-driven behavior, and other key features. Developing scalable algorithms to address the computational challenges encountered in this framework is also a focus of our work.
EV Charging Stations Placement and Management
Electric Vehicles (EVs) are welcoming a rapid development along with progress of relevant technologies in recent years. As an eco-friendly substitute for the traditional fuel-engined vehicle, EV is seen as a promising solution to the energy crisis and environmental pollution around the globe. Many countries and cities have proposed plans to promote EV usage or are preparing to do so, providing a foreseeable picture that EV will become the major vehicle of the private transportation sector in the near future.
Notwithstanding the progress, challenges still remain. Limited battery capacity and long charging time raise mileage anxiety that largely impair EV users' driving experience. A well planned and managed network of specialized EV charging stations, which provide more than 10 times faster charging speed than domestic charging, is therefore critical to the successful promotion of EV. To achieve this, we use congestion games to model EV driversity driving and charging behavior in consideration of the mutual impact between EVs and the whole road transportation system. We focus on equilibrium analysis and designing efficient optimization algorithms to obtain robust practical solutions for comprehensive real-world scenarios.
Yanhai Xiong, Jiarui Gan, Bo An, Chunyan Miao, Soh Yeng Chai. Optimal pricing for efficient electric vehicle charging station management. Proceedings of the 15th International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS'16), pp.749-757. [PDF]
Jiarui Gan, Bo An, Chunyan Miao. Optimizing efficiency of taxi systems: Scaling-up and handling arbitrary constraints. Proceedings of the 14th International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS'15), pp.523-531, 2015. [PDF]
Yanhai Xiong, Jiarui Gan, Bo An, Chunyan Miao, Ana Bazzan. Optimal electric vehicle charging station placement. Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI'15), pp.2662-2668, 2015. [PDF]
Jiarui Gan, Bo An, HaizhongWang, Xiaoming Sun, Zhongzhi Shi. Optimal pricing for improving efficiency of taxi systems. Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI'13), pp.2811-2818, 2013. [PDF]