Skip to content. Skip to navigation
McGill Home SOCS Home
Personal tools
You are here: Home Announcements and Events Seminars Schedule

Seminar Home
Fall 2013 Schedule
Winter 2014 Schedule
Summer 2014 Schedule

SOCS Graduate Seminar Series Seminar Schedule

Date Category Seminar Info
2013/08/13 Graduate Seminar Series Place: MC103
Time: 12 - 12:30
Speaker: Jonathan Tremblay
Affiliation: McGill, SOCS
Area: Artificial Intelligence and Digital Games
Title: An Exploration Tool for Predicting Stealthy Behaviour

Stealthy movement is an important part of many games in the First Person Shooter (FPS) and Role Playing Games (RPG) genres. Structuring a game level to match stealth goals, however, is difficult, and can depend on subtle and fragile inter-actions between the game space, enemy motion, and other factors. In this talk we will apply a probabilistic path-finding approach to efficiently analyze a 2D space and find stealthy paths. This approach naturally accommodates variation in the level design, numbers and movements of enemies, fields of view, and player start and goal placement. Our design is integrated directly into the Unity 3D game development framework, allowing for interactive and highly dynamic exploration of how different virtual spaces and enemy configurations affect the potential for stealthly movement by players, or other NPCs.

2013/07/30 Graduate Seminar Series Place: MC103
Time: 12 - 12:30
Speaker: Nir Rikovitch
Affiliation: Master Student, Department of Mechanical Engineering, McGill
Title: Kinodynamic Non-Holonomic Motion Planning for UAVs: A Minimum Energy Approach

In recent years unmanned aerial vehicles (UAVs) have gained popularity for various applications, both civilian and military. As technology advanced, UAVs became cheaper, lighter and more readily available than their manned versions. Due to limited aircraft size and load carrying capabilities, battery capacity substantially reduces flight endurance. Therefore, generating flight paths for a UAV which take into account the dynamics of the vehicle, while at the same time minimizing the energy requirements is a worthwhile avenue to pursue. This seminar presents the minimum energy affine quadratic regulator (MEAQR) RRT* - an asymptotically optimal sampling-based motion planning algorithm for non-linear, non-holonomic, under-powered and under-actuated systems in a-priori known and static environments. The generated trajectory connects the initial and goal positions with a collision-free, dynamically feasible trajectory that adheres to the magnitude and bandwidth constraints of actuation, while minimizing energy consumption.

The algorithm is demonstrated on two example systems (1) a simple 2D pendulum with actuation constraints and (2) a quadrotor described by a 13-dimensional state-space model. In addition, an environment modeling procedure is designed, implemented and tested for a-priori map building required in order to test the algorithm on a real life environment.

2013/07/24 Graduate Seminar Series Place: MC103
Time: 12 - 12:30
Speaker: Bundit Laekhanukit
Affiliation: PhD student, SOCS
Area: theory
Title: Hardness of Approximation: Nearly Linear-Size PCP and The Limits of Time-Approximability Trade-off

The theory of NP-completeness is a fundamental theory in computer science, which separates problems into "easy" and "hard" problems. While many problems we encounter are "hard" (i.e., no polynomial-time algorithm exists unless P=NP), this does not rule out the possibility of getting an approximate solution. Unfortunately, even finding an approximate solution has its limit.

In this talk, we will discuss the limits of approximations of the maximum independent set problem (Independent Set) and the k-hypergraph pricing problem (Pricing). Under the assumption that SAT does not has a sub-exponential-time algorithm, we will show that no algorithm with a running time of 2^{n/r} could give an r-approximate solution for Independent Set; this is a tight hardness result. For the case of Pricing, we will show a sharp contrast in the approximability of the quasi-polynomial-time and polynomial-time algorithms.

2013/06/13 Graduate Seminar Series Place: MC103
Time: 1:30 - 2
Speaker: Martin Robillard
Affiliation: Associate Professor, SOCS, McGill
Title: Advice for new faculty members

2013/06/04 Graduate Seminar Series Place: MC103
Time: 12 - 12:30
Speaker: Giulia Alberini
Affiliation: PhD student, SOCS McGill
Area: Cryptography
Title: Verifiable Anonymous Polling

We introduce a new framework for polling responses from a large population of humans. Our framework allows to gather information without violating the responders' anonymity and at the same time enables public verification of the poll's result. In contrast to prior approaches to the problem, we do not require trusting the pollster for faithfully announcing the poll's results, nor do we rely on strong identity verification (a prerequisite for publicly verifiable voting systems).

We propose an "effort based" polling protocol whose results can be publicly verified by constructing a "responder certification graph" whose nodes are labeled by responders' replies to the poll, and whose edges cross-certify that adjacent nodes correspond to human votes. Cross-certification is achieved using a newly introduced (privately verifiable) proof of "human effort" (PHE). The proof relies on expansion properties of the certification graph. In effect, our protocol can be thought of as a method for converting certain types of private-coin protocols into a publicly-verifiable protocol.

Our results are applicable to a variety of settings in which crowd-sourced information gathering is required. This includes political polling, recommendation systems, viewer voting in TV shows and prediction markets.

2013/05/28 Graduate Seminar Series Place: MC103
Time: 12 - 12:30
Speaker: Jacob Beard
Affiliation: former MSc student at SOCS
Title: Developing Rich, Web-based User Interfaces with SCXML and SCION

User interfaces (UIs) comprise reactive systems whose behaviour often involves a complex notion of timing and state. Implementing this logic directly in a general-purpose programming language can be nontrivial, leading to applications that are slow to develop and error-prone. Previous work has demonstrated that Statecharts, a graphical language for modelling timed, reactive, stateful systems, can be used effectively to design, prototype, and synthesize complex user interfaces. This reduces the accidental complexity involved in user interface development, allowing developers to focus only on the remaining essential complexity, which ultimately leads to greater developer productivity, and faster, more robust UIs.

Web user interfaces are built on a standard suite of Open Web technologies, including HTML, CSS, and JavaScript, and in order to run Statecharts effectively on the Web, a Statecharts interpreter or compiler implemented in JavaScript is first needed. SCION is a liberally licensed open source project which provides an implementation of Statecharts in JavaScript. More specifically, SCION implements the SCXML draft specification, an emerging W3C standard which provides an XML syntax and semantics for Statecharts.

This talk will provide a practical examination of techniques to apply SCXML and SCION to real-world UI development today.

2013/05/21 Graduate Seminar Series Place: MC103
Time: 12 - 12:30
Speaker: Anqi Xu
Affiliation: PhD student, SOCS McGill
Area: Robotics
Title: Modeling and Making Use of Human->Robot Trust

We are interested in identifying computational models of “trust” in human-robot systems that are inferred from their interactions, and inspired by similar concepts relating to trust among humans. This computable quantity will allow a robot to estimate the extent to which its performance is consistent with a human’s expectations, with respect to task demands. We present an initial model of trust based on utility theory, and demonstrate how it can be coupled with an adaptive mechanism that dynamically adjusts the robot’s autonomous behaviors, in order to improve the efficiency of the collaborative team. This trust-driven methodology is instantiated using an interactive visual robot navigation system, and is evaluated through controlled user experiments as well as a field demonstration using an aerial robot.

2013/05/08 Graduate Seminar Series Place: MC103
Time: 12 - 12:30
Speaker: Bentley James Oakes
Affiliation: McGill SOCS
Area: Computer Game Design
Title: Evolving Strategies for a Turn-Based Game: Practical and Theoretical Issues

Video games often have challenging and exciting computer-controlled opponents to play against a human player. However, creating a artificial intelligence (AI) to operate these opponents requires significant development effort by both programmers and game designers. One solution is to use automated processes to evaluate and improve the strength of AIs, and adapt them to changing game maps or mechanics.

This seminar will present ongoing work into the application of genetic algorithms to the AI of Battle for Wesnoth, a popular turn-based strategy game. AI strategies are represented by a tree with action nodes, based on the behaviour tree formalism. These strategies were then evaluated in a Battle for Wesnoth game, in order to obtain a metric of their performance. The genetic algorithm then preferentially selected and combined strategies that performed well, allowing elements from strong strategies to transfer into other strategies. By iterating this process, this algorithm produced strategies that are stronger than the starting strategies.

An overview of genetic algorithms will be provided at the start of the seminar, followed by a short discussion on the difficulty of evaluating AI performance. Preliminary results from this work will then be presented, including the strength of automatically-generated strategies versus hand-built strategies.