# Publications

I’m a Postdoctoral fellow in operational research and artificial
intelligence at the University of Toronto. My research interests include
combinatorial and multiobjective optimization, machine learning, data
science and big data analytics, and (meta)simulation for real-life
problems solving and uncertainty management.

I’ve been working on a variety of applications from robotic to
marketing all of which involved managing the problem’s
complexity to obtain practical solutions in a reasonable time-frame.
I’m interested in Markov chains and stochastic processes which I
applied to search and rescue and detection search problems jointly with
combinatorial and multiobjective optimization techniques.
I’m also interested in machine learning which enable us, for
instance, to foresee the production resulting from the transformation of
the raw matter at a given plant (e.g., from logs to lumbers).

This page contains selected publications and given talks as well as related projects.
Here is the list of all my publications in BibTeX format
[→ BibTeX]

On this page:

[Refereed publications]

[Other]
**M. Morin**, I. Abi-Zeid, C.G. Quimper, O. Nilo,
“Decision Support for Search and Rescue Response Planning,” in
*Proceedings of the 14th International Conference on Information
Systems for Crisis Response and Management*,
2017.

**Abstract.**
*
Planning, controlling and coordinating search and rescue operations is
complex and time is crucial for survivors who must be found quickly. The
search planning phase is especially important when the location of the
incident is unknown. We propose, implement, solve, and evaluate
mathematical models for the multiple rectangular search area problem. The
objective is to define optimal or near-optimal feasible search areas for
the available search and rescue units that maximize the probability of
success. We compare our new model to an existing model on problem instances
of realistic size. Our results show that we are able to generate, in a
reasonable time, near optimal operationally feasible plans for searches
conducted in vast open spaces. In an operational context, this research can
increase the chances of finding survivors. Ultimately, as our models get
implemented in the Canadian Coast Guard search planning tool, this can
translate into more lives being saved.
*

[+ abstract]

Paper:
[→ IscramLive]
[→ PDF]

**M. Morin**, R. Thomopoulos, I. Abi-Zeid, M. Léger,
F. Grondin, M. Pleau
“Explaining the Results of an Optimization-Based Decision Support
System - A Machine Learning Approach,” in
*Proceedings of the 2016 conference on Applied Mathematical Programming
and Modelling*,
2016.

**Abstract.**
*
In this paper, we present work conducted in order to explain the results of
a commercial software used for real-time decision support for the flow
management of a combined wastewater network. This tool is deployed in many
major cities and is used on a daily basis. We apply decision trees to build
rules for classifying and interpreting the solutions of the optimization
model. Our main goal is to build a classifier that would help a user
understand why a proposed solution is good and why other solutions are
worse. We demonstrate the feasibility of the approach to our industrial
application by generating a large dataset of feasible solutions and
classifying them as satisfactory or unsatisfactory based on whether the
objective function is a certain percentage higher than the optimal
(minimum) objective. We evaluate the performance of the learned classifier
on unseen examples. Our results show that our approach is very promising
according to reactions from analysts and potential users.
*

[+ abstract]

Paper:
[→ PDF]

**M. Morin**, F. Paradis, A. Rolland, J.
Wery, J. Gaudreault, F. Laviolette
“Machine Learning-Based Metamodels for Sawing Simulation,” in
*Proceedings of the 2015 Winter Simulation Conference*,
2015.

**Abstract.**
*
We use machine learning to generate metamodels for sawing simulation.
Simulation is widely used in the wood industry for decision making.
These simulators are particular since their response for a given input is
a structured object, i.e., a basket of lumbers. We demonstrate how we
use simple machine learning algorithms (e.g., a tree) to obtain a good
approximation of the simulator's response. The generated metamodels are
guaranteed to output physically realistic baskets (i.e., there exists at
least one log that can produce the basket). We also propose to use
kernel ridge regression. While having the power to exploit the structure
of a basket, it can predict previously unseen baskets. We finally
evaluate the impact of possibly predicting unrealistic baskets using
ridge regression jointly with a nearest neighbor approach in the output
space. All metamodels are evaluated using standard machine learning
metrics and novel metrics especially designed for the problem.
*

[+ abstract]

Paper:
[→ Informs-Sim]
[→ PDF]

F. Simard, **M. Morin**, C.G. Quimper, F. Laviolette, and J.
Desharnais, “Bounding an Optimal Search Path with a Game of Cop and
Robber on Graphs,” in
*Principles and Practice of Constraint Programming*,
2015.

**Abstract.**
*
In search theory, the goal of the Optimal Search Path (OSP) problem is to
find a finite length path maximizing the probability that a searcher
detects a lost wanderer on a graph. We propose to bound the probability
of finding the wanderer in the remaining search time by relaxing the
problem into a stochastic game of cop and robber from graph theory. We
discuss the validity of this bound and demonstrate its effectiveness on a
constraint programming model of the problem. Experimental results show
how our novel bound compares favorably to the DMEAN bound from the
literature, a state-of-the-art bound based on a relaxation of the OSP
into a longest path problem.
*

[+ abstract]

Paper:
[→ SpringerLink]
[→ PDF]

F. Simard, **M. Morin**, C.G. Quimper, F. Laviolette, and J.
Desharnais, “Relaxation of the Optimal Search Path Problem with the Cop
and Robber Game,” in
*Doctoral Program CP 2014*,
2014.

**Abstract.**
*
In the Optimal Search Path problem from search theory, the
objective is to and a finite length searcher's path that maximizes the
probability of detecting a lost wanderer on a graph. We introduce a
novel bound on the probability of finding the wanderer in the remaining
search time and discuss how this bound is derived from a relaxation
of the problem into a game of cop and robber from graph theory. We
demonstrate the efficiency of this bound on a constraint programming
model of the problem.
*

[+ abstract]

Paper:
[→ Graal]
[→ PDF]

Addendum:
[→ Graal]
[→ PDF]

**M. Morin**, and C.G. Quimper,
“The Markov Transition Constraint,” in
*Integration of AI and OR Techniques in Constraint Programming for
Combinatorial Optimization Problems*, 2014.

**Abstract.**
*
We introduce a novel global Markov transition constraint (MTC) to model
finite state homogeneous Markov chains. We present two algorithms to
filter the variable domains representing the imprecise probability
distributions over the state space of the chain. The first filtering
algorithm is based on the fractional knapsack problem and the second
filtering algorithm is based on linear programming. Both of our filtering
algorithms compare favorably to the filtering performed by solvers when
decomposing an MTC into arithmetic constraints. Cases where the
fractional knapsack decomposition enforces bounds consistency are
discussed whereas the linear programming filtering always perform bounds
consistency. We use the MTC constraint to model and solve a problem of
path planning under uncertainty.
*

[+ abstract]

Paper:
[→ PDF]

Slides:
[→ PDF]

**M. Morin**, I. Abi-Zeid, Y.R. Petillot, and C.G. Quimper,
“A Hybrid Algorithm for Coverage Path Planning with Imperfect
Sensors,” in
*Proceedings of the IEEE/RSJ International Conference on Intelligent
Robots and Systems (IROS 2013)*, 2013.

**Abstract.**
*
We are interested in the coverage path planning problem with
imperfect sensors, within the context of robotics for mine
countermeasures. In the studied problem, an autonomous underwater
vehicle (AUV) equipped with sonar surveys the bottom of the ocean
searching for mines. We use a cellular decomposition to represent the
ocean floor by a grid of uniform square cells. The robot scans a
fixed number of cells sideways with a varying probability of
detection as a function of distance and of seabed type. The goal is
to plan a path that achieves the minimal required coverage in each
cell while minimizing the total traveled distance and the total
number of turns. We propose an off-line hybrid algorithm based on
dynamic programming and on a traveling salesman problem reduction. We
present experimental results and show that our algorithm’s
performance is superior to published results in terms of path quality
and computational time, which makes it possible to implement the
algorithm in an AUV.
*

[+ abstract]

Paper:
[→ IEEE XPlore]
[→ PDF]

Slides:
[→ PDF]

Digest:
[→ PDF]

**M. Morin**, I. Abi-Zeid, T. T. Nguyen, L. Lamontagne and
P. Maupin, “Search and Surveillance in Emergency situations –
A GIS based approach to construct optimal visibility graphs,”
in *Proceedings of the 10th International Conference on Information
Systems for Crisis Response and Management*,,
2013.

**Abstract.**
*
We present a methodology to construct near-optimal visibility graphs from
vector and raster terrain data based on the integration of Geographic
Information Systems, computational geometry, and integer linear
programming. In an emergency situation, the ability to observe an
environment, completely or partially, is crucial when searching an area
for survivors, missing persons, intruders or anomalies. We first analyze
inter-visibility using computational geometry and GIS functions. Then,
we optimize the visibility graphs by choosing vertices in a way to either
maximize coverage with a given number of watchers or to minimize the
number of watchers needed for full coverage.
*

[+ abstract]

Paper:
[→ IscramLive]
[→ PDF]

Slides:
[→ PDF]
presented by Irène Abi-Zeid

**M. Morin**, A.P. Papillon, F. Laviolette, I. Abi-Zeid, and
C.G. Quimper, “Constraint Programming for Path Planning
with Uncertainty: Solving the Optimal Search Path problem,” in
*Principles and Practice of Constraint Programming*,
2012, pp. 988-1003.

**Abstract.**
*
The optimal search path (OSP) problem is a single-sided detection search
problem where the location and the detectability of a moving object are
uncertain. A solution to this NP-hard problem is a path on a graph that
maximizes the probability of finding an object that moves according to a
known motion model. We developed constraint programming models to solve
this probabilistic path planning problem for a single indivisible
searcher. These models include a simple but powerful branching heuristic
as well as strong filtering constraints. We present our experimentation
and compare our results with existing results in the literature. The OSP
problem is particularly interesting in that it generalizes to various
probabilistic search problems such as intruder detection, malicious code
identification, search and rescue, and surveillance.
*

[+ abstract]

Paper:
[→ SpringerLink]
[→ PDF]

Poster:
[→ PDF]

Slides:
[→ PDF]

Source code:
[→ source]

I. Abi-Zeid, O. Nilo, S. Schvartz, and **M. Morin**,
“Towards a Knowledge-Based System
Prototype for Aeronautical Search and Rescue Operations,” in
*Proceedings of the 13th International Conference on
Information Fusion*, 2010
(**invited paper**).

**Abstract.**
*
The long-term objective of our project is to develop a knowledge-based
tool for Search and Rescue (SAR) operations to support a Canadian search
mission coordinator in determining the likely location of a missing
aircraft overland. In order to attain this objective, we used a
knowledge engineering approach to acquire, structure and model SAR
experts’ knowledge. This knowledge was modeled and implemented in a
knowledge-based system prototype. The input to the interactive prototype
consists of the known information regarding a given SAR case. Its main
output is a set of scenarios describing the various hypotheses on what
might have happened to the missing aircraft, why and where, the plausible
routes followed, as well as the possibility area, defined as the region
most likely to contain the missing aircraft. In this paper, we introduce
the knowledge model, present an application example and briefly describe
the prototype.
*

[+ abstract]

Paper:
[→ IEEE XPlore]
[→ PDF]

**M. Morin**, L. Lamontagne, I. Abi-Zeid, and P. Maupin,
“The Ant Search Algorithm: An Ant Colony Optimization Algorithm
for the Optimal Searcher Path Problem with Visibility,” in
*Advances in Artificial Intelligence: 23rd Canadian Conference on
Artificial Intelligence*, 2010, pp. 196-207.

**Abstract.**
*
In the first part of this paper, we present the Optimal Searcher Path
problem with Visibility, a novel path planning approach that models
inter-region visibility and that uses concepts from search theory to
model uncertainty on the goal’s (i.e., the search object)
detectability and location. In the second part, we introduce the Ant
Search algorithm, a solving technique based on ant colony optimization.
Our results, when compared with a general mixed-integer programming model
and solver, show that Ant Search is a promising technique for handling
this particular complex problem.
*

[+ abstract]

Paper:
[→ SpringerLink]
[→ PDF]

**M. Morin**, L. Lamontagne, I. Abi-Zeid, P. Lang, and P.
Maupin, “The Optimal Searcher Path Problem with a Visibility
Criterion in Discrete Time and Space,” in
*Proceedings of the 12th International Conference on
Information Fusion*, 2009, pp. 2217-2224.

**Abstract.**
*
In this paper, the problem of path planning for a ground search unit
looking for an object of unknown location is considered. As in the
classical optimal searcher path problem, the probability of finding the
search object is the main criterion of optimality and the search unit is
constrained by the environment topology that influences its choices for a
navigable path as well as its detection capabilities. This paper proposes
an extension to the classical optimal searcher path problem in discrete
time and space by integrating inter-region visibility as an additional
criterion. This new formulation allows a refinement in the discretization
of the space in which a ground search unit evolves. A general
mixed-integer programming model is proposed, and experimental results
with a moving object in grid environments are discussed.
*

[+ abstract]

Paper:
[→ IEEE XPlore]
[→ ISIF]
[→ PDF]

[Top]

**M. Morin**, “Anticipating Lumber Production for a Better Wood Allocation,”
Info-Forac. , 2017
(**extended abstract**).

Paper: [→ ULaval.Forac]

**M. Morin**, “Foreseeing the Products of Sawmilling,”
Info-Forac. , 2016
(**extended abstract**).

Paper: [→ ULaval.Forac]

**M. Morin**, “Search and Coverage Path Planning,”
Université Laval, Québec, QC, Canada,
Ph.D. thesis, 2015.

**Abstract.**
*
We tackle two different and complementary problems: the Coverage Path Planning (CPP) and the
Optimal Search Path (OSP).
The CPP is a main challenge in mobile robotics.
The OSP is a classic from search theory.
We first present a review of both problems that highlights their differences
and their similarities from the point of view of search (coverage) operations.
Both problems are positioned on the continuum of the a priori knowledge
on the whereabouts of a search object.
We then formalize an extension of the CPP we call the CPP with
imperfect extended detections (CPPIED).
We present a novel and powerful heuristic algorithm that uses dynamic
programming and a traveling salesman (TSP) reduction.
We apply the method to underwater minesweeping operations on maps with more
than 21 thousand cells.
We then study a novel Constraint Programming (CP) model to solve
the OSP.
We first improve on using the classical objective function found in the
OSP definition.
Our novel objective function, involving a single modification of the operators
used to compute the probability of success of a search plan, leads to a stronger
filtering of the probability variables of the model.
Then, we propose a novel heuristic for the OSP:
the Total Detection (TD) heuristic.
Experiments show that our model, along with the proposed heuristic, is
competitive with problem-specific Branch and Bounds supporting the claim
that CP is a good technique to solve search theory problems.
We finally propose the Markov Transition Constraint (MTC) as a novel
modeling tool in CP to simplify the implementation of models based on
Markov chains.
We prove, both empirically and theoretically, that interval arithmetic is
insufficient to filter the probability variables of a single MTC,
i.e., to enforce bounds consistency on these variables.
Interval arithmetic is the only available tool to filter an
MTC when it is decomposed into individual arithmetic constraints.
We thus propose an algorithm based on linear programming which is proved to
enforce bounds consistency.
Since linear programming is computationally expensive to use at each node of the
search tree of a CP solver, we propose an
in-between solution based on a fractional knapsack filtering.
The MTC global constraint usage is illustrated on a CP model of
the OSP.
*

[+ abstract]

Thesis:
[→ PDF, recto-verso]

Supervisor: Claude-Guy Quimper
[→
homepage]

Cosupervisor: Irène Abi-Zeid
[→
homepage]

I. Abi-Zeid,
**M. Morin**, and T.T. Nguyen, “Vers une
planification multicritère dans le cadre de missions de
recherche et sauvetage terrestres,” presented at the
*73rd Meeting of the European Working Group MCDA*, 2011.

**Abstract.**
*
Search and Rescue operations involve the efficient allocation of
available resources in order to locate a lost search object caught in a
critical situation (e.g., the survivors of an aeronautical incident). In
this paper, we describe our work in progress for developing a
multi-criteria inland search operations planning method. The method uses
geographic information system tools, visibility and accessibility graphs
discretization, metaheuristics and search theory.
*

**Résumé.**
*
Les opérations de recherche et sauvetage nécessitent
l’allocation efficace des ressources disponibles dans le but de
retrouver un objet de recherche en situation critique (e.g., les survivants
d’un incident aéronautique). L’état
d’avancement des travaux sur une méthode de planification
multicritère des opérations de recherches en milieu terrestre
utilisant des outils de système d’informations
géographiques, des méthodes de discrétisations par
graphes de visibilité et d’accessibilité, des
métaheuristiques ainsi que la théorie de la recherche est
présentée.
*

[+ abstract]

Paper:
[→ PDF]

**M. Morin**, “Introducing Multi-Criteria Path
Planning with Terrain Visibility Constraints: The Optimal Searcher Path
Problem with Visibility,” in
*Proceedings of the XV ELAVIO*, 2010
(**extended abstract**).

Paper:
[→ PDF]

Slides:
[→ PDF]

**M. Morin**, “Multi-Criteria Path Planning with
Terrain Visibility Constraints: The Optimal Searcher Path Problem with
Visibility,” Université Laval, Québec, QC, Canada,
Master's thesis, 2010.

**Abstract.**
*
How can search theory and path planning concepts be used to formulate and
to solve detection search problems in the context of a ground SAR
operation while taking into account practical aspects such as terrain
visibility constraints? As an answer to this research question, we have
formulated a novel detection search problem to include the
searcher’s visibility constraints (the Optimal Searcher Path
problem with Visibility) and we developed solving techniques for the
single criterion and for the multi-criteria cases. In the single
criterion case, the search plan’s efficiency corresponds to the
probability of finding the search object (i.e., the goal); a mixed
integer linear program is presented and compared to our novel Ant Colony
Optimization adaptation called Ant Search. The multi-criteria case
introduces the searcher’s security and the plan’s complexity
as supplementary efficiency criteria; the initial Ant Search algorithm is
extended to Pareto Ant Search and to Lexicographic Ant Search.
*

[+ abstract]

Thesis:
[→ PDF, recto-verso]
[→ bibl.ULaval]

Supervisor: Luc Lamontagne
[→ homepage]

Cosupervisor: Irène Abi-Zeid
[→ homepage]

**M. Morin**, I. Abi-Zeid, and L. Lamontagne, “An
algorithm for the optimal search path with visibility problem,”
prepared for Defence R&D Canada - Valcartier, by MITACS, Contract
number W7701-08-1871, 2010, 20 p.

[Top]

* Last update: May 23, 2017 *

© Michael Morin, 2017