Relevant Degree Programs
Ian M. Mitchell received a B.A.Sc. in Engineering Physics and an M.Sc. in Computer Science from the University of British Columbia, Canada in 1994 and 1997 respectively, and a Ph.D. in Scientific Computing and Computational Mathematics from Stanford University in 2002. After spending a year as a postdoctoral researcher in the Department of Electrical Engineering and Computer Science at the University of California, Berkeley and the Department of Computer Science at Stanford, Dr. Mitchell joined the faculty in the Department of Computer Science at the University of British Columbia where he is now a professor. He is the author of the Toolbox of Level Set Methods, the first publicly available high accuracy implementation of solvers for dynamic implicit surfaces and the time dependent Hamilton-Jacobi equation that works in arbitrary dimension. His research interests include development of algorithms and software for nonlinear differential equations, formal verification, control and planning in cyber-physical and robotic systems, assistive technology, and reproducible research.
Graduate Student Supervision
Doctoral Student Supervision (Jan 2008 - May 2019)
Reachability analysis and viability theory are key in providing guarantees of safety and proving the existence of safety-preserving controllers for constrained dynamical systems. The minimal reachable tube and (by duality) the viability kernel are the only constructs that can be used for this purpose. Unfortunately, current numerical schemes that compute these constructs suffer from a complexity that is exponential in the dimension of the state, rendering them impractical for systems of dimension greater than three or four.In this thesis we propose two separate approaches that improve the scalability of the computation of the minimal reachable tube and the viability kernel for high-dimensional systems. The first approach is based on structure decomposition and aims to facilitate the use of computationally intensive yet versatile and powerful tools for higher-dimensional linear time-invariant (LTI) systems. Within the structure decomposition framework we present two techniques – Schur-based and Riccati-based decompositions – that impose an appropriate structure on the system which is then exploited for the computation of our desired constructs in lower-dimensional subspaces.The second approach is based on set-theoretic methods and draws a new connection between the viability kernel and maximal reachable sets. Existing tools that compute the maximal reachable sets are efficient and scalable with polynomial complexity in time and space. As such, these scalable techniques can now be used to compute our desired constructs and therefore provide guarantees of safety for high-dimensional systems. Based on this new connection between the viability kernel and maximal reachable sets we propose a scalable algorithm using ellipsoidal techniques for reachability. We show that this algorithm can efficiently compute a conservative under-approximation of the viability kernel (or the discriminating kernel when uncertainties are present) for LTI systems. We then propose a permissive state-feedback control strategy that is capable of preserving safety despite bounded input authority and possibly unknown disturbances or model uncertainties for high-dimensional systems.We demonstrate the results of both of our approaches on a number of practical examples including a problem of safety in control of anesthesia and a problem of aerodynamic flight envelope protection.
The solution of a static Hamilton-Jacobi Partial Differential Equation (HJ PDE) can be used to determine the change of shape in a surface for etching/deposition/lithography applications, to provide the first-arrival time of a wavefront emanating from a source for seismic applications, or to compute the minimal-time trajectory of a robot trying to reach a goal. HJ PDEs are nonlinear so theory and methods for solving linear PDEs do not directly apply. An efficient way to approximate the solution is to emulate the causal property of this class of HJ PDE: the solution at a particularpoint only depends on values backwards along the characteristic that passes through that point and solution values always increase along characteristics. In our discretization of the HJ PDE we enforce an analogous causal property, that the solution value at a grid node may only depend on the values of nodes in its numerical stencil which are smaller. This causal property is related but not the same thing as an upwinding property of schemes for time dependent problems. The solution to such a discretized system of equations can be efficiently computed using a Dijkstra-like method in a single pass through the grid nodes in order of nondecreasing value. We develop two Dijkstra-like methods for solving two subclasses of static HJ PDEs. The first method is an extension of the Fast Marching Method for isotropic Eikonal equations and it can be used to solve a class of axis-aligned anisotropic HJ PDEs on an orthogonal grid. The second method solves general convex static HJ PDEs on simplicial grids by computing stencils for a causal discretization in an initial pass through the grid nodes, and then solving the discretization in a second Dijkstra-like pass through the nodes. This method is suitable for computing solutions on highly nonuniform grids, which may be useful for extending it to an error-control method based on adaptive grid refinement.
Master's Student Supervision (2010 - 2018)
Mobility is one of the most significant factors that determines older adults’ perceived level of health and well being. Cognitively impaired older adults are deprived of using powered wheelchairs because of the operational safety risks. These users can benefit from intelligent assistance during cognitively or visually challenging tasks such as back-in parking. An intelligent powered wheelchair that assists a cognitively impaired elderly user to perform a back-in parking task is proposed. A single subject participatory action design method is used with a cognitively impaired older adult to identify design guidelines for the proposed system. Based on analysis of transcripts from semi-structured interviews with the participant, a semi-autonomous back-in parking system is designed to drive the powered wheelchair into a pre-specified back-in parking space when the user commands it to. A prototype of a non-intrusive steering guidance feature for a joystick handle is also designed to render shear force in a way that can be associated with steering behavior of a car. The performance of the proposed system is evaluated in a pilot study. Experiments with the autonomous trigger and autonomous assisted modes are conducted during a back-in parking task with real-life obstacles such as tables and chairs in a long-term care facility. A single-subject research design is used to acquire and analyze quantitative data as a pilot study. Results demonstrate an increase in the user’s perception of ease of use, effectiveness and feeling of safety with the proposed system. While the user experienced at least one minor contact in 37.5% of the trials when driving unaided, the proposed system eliminated all minor contacts. No statistically significant difference in completion time and route length is observed with the proposed system. In the future, improved back-in parking systems can use this work as a benchmark for single subject participatory action design. Future iterations could also replicate the usability study on a larger population.