Testing multi-agent systems for unwanted behavior

点击翻译按钮获取中文摘要

Computer systems that adapt themselves or interact with other systems provide new challenges to software testing methods. While such systems offer the possibility for more autonomy (and less need for human administration) and the possibility for emergent behaviors that provide abilities that are not possible for a single system, these same possibilities can also result in negative and unexpected effects. A system might adapt in the wrong way, or we might have emergent misbehavior when several systems try to interact with each other. This research proposal is about new testing methods that are able to find such unwanted behavior of a system or a group of systems (a multi-agent system). This will help to ensure that we can make use of the advantages of multi-agent systems without special safety concerns. In contrast to "conventional" testing methods that test if a system shows the right response in given scenarios, our testing method is able to find scenarios in which a system is showing an unwanted behavior. Using our approach, we were already successful in finding unwanted behavior in the FIFA-99 soccer game (namely user actions that always resulted in scoring a goal against the computer player), in a group of rescue agents written by students in a multi-agent system class (namely creating behaviors of agents interacting with the students' agents in such a manner that the students' agents froze), and in harbour patrol and interception policies (namely behaviors for terrorist boats that resulted in them achieving a given objective despite the defenders correctly following the policies). With the proposed research program, we investigate extensions to our basic method that expand our basic process to allow for the introductions of subgoals, that allow the integration of various knowledge about testing, the application area and the tested system, and that create the possibility to have previous test runs influence the next test run. This research will enable us to develop an extended general framework for testing multi-agent systems for multi-agent specific problems together with guidelines on how to instantiate this framework for concrete multi-agent systems.