Security games, and important class of Stackelberg games, are used in deployed decision-support tools in use by LAX police and the Federal Air Marshals Service. The algorithms used to solve these games find optimal randomized schedules to allocate security resources for infrastructure protection. Unfortunately, the state of the art algorithms either fail to scale or to provide a correct solution for large problems with arbitrary scheduling constraints. We introduce ASPEN, a branch-and-price approach that overcomes these limitations based on two key contributions: (i) A column-generation approach that exploits a novel network flow representation, avoiding a combinatorial explosion of schedule allocations; (ii) A branch-and-bound algorithm that generates bounds via a fast algorithm for solving security games with relaxed scheduling constraints. ASPEN is the first known method for efficiently solving massive security games with arbitrary schedules.

Consider the following problem: a human-robot team is actively In this paper, we explore the issues involved in engineering engaged in an urban search and rescue (USAR) scenario an automated planner to guide a robot towards maximizing inside a building of interest. The robot is placed inside net benefit accompanied with goal achievement in such this building, at the beginning of a long corridor; a sample scenarios. The planning problem that we face involves partial layout is presented in Figure 1. The human team member satisfaction (in that the robot has to weigh the rewards of has intimate knowledge of the building's layout, but is removed the soft goals against the cost of achieving them); it also requires from the scene and can only interact with the robot replanning ability (in that the robot has to modify its via on-board wireless audio communication. The corridor in current plan based on new goals that are added). An additional which the robot is located has doors leading off from either (perhaps more severe) complication is that the planner side into rooms, a fact known to the robot. However, unknown needs to handle goals involving objects whose existence is to the robot (and the human team member) is the possibility not known in the initial state (e.g., the location of the humans that these rooms may contain injured humans (victims).

In this paper we apply a Monte-Carlo Tree Search implementation that is boosted with domain knowledge to the game of poker. More specifically, we integrate an opponent model in the Monte-Carlo Tree Search algorithm to produce a strong poker playing program. Opponent models allow the search algorithm to focus on relevant parts of the game-tree. We use an opponent modelling approach that starts from a (learned) prior, i.e., general expectations about opponent behavior, and then learns a relational regression tree-function that adapts these priors to specific opponents. Our modelling approach can generate detailed game features or relations on-the-fly. Additionally, using a prior we can already make reasonable predictions even when limited experience is available for a particular player. We show that Monte-Carlo Tree Search with integrated opponent models performs well against state-of-the-art poker programs.

In this paper we explore challenges related to the engineering of plan libraries for plan recognition. This is an often overlooked problem, yet essential in the design of any real world plan recognizers. We mainly discuss challenges related to the evaluation of equivalence between plan libraries. We explain why this is a potential source of ill-conceived plan libraries. We consider an existing well-established probabilistic plan recognizer as vehicle for our discussion, using the formalism of probabilistic hierarchical task networks to represent plans. We propose avenues for exploring solutions to those challenges within that framework.

Providing cognitive assistance in smart homes is a field of research that receives a lot of attention lately. In order to give adequate assistance at the opportune moment, we need to recognize the observed behavior when the patient carries out some activities in a smart home. To address this challenging issue, we present a formal activity recognition framework based on possibility theory. We present initial results from an implementation of this possibilistic recognition approach in a smart home laboratory.

In Real-Time Strategy (RTS) video games, players (controlled by humans or computers) build structures and recruit armies, fight for space and resources in order to control strategic points, destroy the opposing force and ultimately win the game. Players need to predict where and how the opponents will strike in order to best defend themselves. Conversely, assessing how the opponents will defend themselves is crucial to mounting a successful attack while exploiting the vulnerabilities in the opponent's defence strategy. In this context, to be truly adaptable, computer-controlled players need to recognize their opponents' behaviour, their goals, and their plans to achieve those goals. In this paper we analyze the algorithmic challenges behind behaviour recognition in RTS games and discuss a generic RTS behaviour recognition system that we are developing to address those challenges. The application domain is that of RTS games, but many of the key points we discuss also apply to other video game genres such as multiplayer first person shooter (FPS) games.

Humans somehow manage to choose quite intelligently planner should fill in to produce a concrete plan that accomplishes the 20 trillion primitive motor commands that constitute a the goal as quickly as possible. It has long been thought that hierarchical structure in Planning at multiple levels of abstraction has long been a behavior is essential in managing this complexity. For instance, Shakey the exists at many levels, ranging from small (hundred-step?) robot used STRIPS for high-level task planning, then called motor programs for typing characters and saying phonemes out to separate low-level planning/control algorithms to execute up to large (billion-step?) actions such as writing an ICAPS each of the planned actions (Fikes and Nilsson 1971). This hard separation of levels, where a high-level plan is We believe that leveraging hierarchical structure will be chosen before considering low-level details, greatly simplifies equally important in achieving robust, efficient robotic behaviors. However, the resulting plans While your household robot probably won't get may be inefficient or even infeasible due to missed lowerlevel tenure anytime soon, even simple domestic tasks still have synergies and conflicts.

In this paper we outline an approach to the integration of task planning and motion planning that has the following key properties: It is aggressively hierarchical. It makes choices and commits to them in a top-down fashion in an attempt to limit the length of plans that need to be constructed, and thereby exponentially decrease the amount of search required. Importantly, our approach also limits the need to project the effect of actions into the far future. It operates on detailed, continuous geometric representations and partial symbolic descriptions. It does not require a complete symbolic representation of the input geometry or of the geometric effect of the task-level operations.

The success of autonomous vehicles has made path planning in real, physically grounded environments an increasingly important problem. In environments where speed matters and vehicles must maneuver around obstructions, such as autonomous car navigation in hostile environments, the speed with which real vehicles can traverse a path is often dependent on the sharpness of the corners on the path as well as the length of path edges. We present an algorithm that incorporates the use of the turn angle through path nodes as a limiting factor for vehicle speed. Vehicle speed is then used in a time-weighting calculation for each edge. This allows the path planning algorithm to choose potentially longer paths, with less turns in order to minimize path traversal time. Results simulated in the Breve environment show that travel time can be reduced over the solution obtained using the Anytime D* Algorithm by approximately 10% for a vehicle that is speed limited based on turn rate.

Activity recognition plays an important role in many areas such as smart environments by offering unprecedented opportunities for assisted living, automation, security and energy efficiency. It’s also an essential component for planning and plan recognition in smart environments. One challenge of activity recognition is the need for collecting and annotating huge amounts of data for each new physical setting in order to be able to carry out the conventional activity discovery and recognition algorithms. This extensive initial phase of data collection and annotation results in a prolonged installation process and excessive time investment for each new space. In this paper we propose a new method of transferring learned knowledge of activities to a new physical space in order to leverage the learning process in the new environment. Our method called ”Home to Home Transfer Learning” (HHTL) is based on using a semi EM framework and modeling activities using structural, temporal and spatial features. This method allows us to avoid the tedious task of collecting and labeling huge amounts of data in the target space, and allows for a more accelerated and more scalable deployment cycle in the real world. It also allows us to exploit the insights learned in previous spaces. To validate our algorithms, we use the data collected in several smart apartments with different physical layouts.