List of projects I have done in McGill University
Information Gathering and Reward Exploitation of Subgoals for POMDPs
Abstract
Planning in large partially observable Markov decision processes (POMDPs) is challenging especially when a long planning horizon is required. A few recent algorithms successfully tackle this case but at the expense of weaker information gathering capacity. In this paper, we propose Information Gathering and Reward Exploitation of Subgoals (IGRES), a randomized POMDP planning algorithm that leverages information in the state space to automatically generate “macroactions” that can tackle tasks with long planning horizons, while locally exploring the belief space to allow effective information gathering. Experimental results show that IGRES is an effective multipurpose POMDP solver, providing stateoftheart performance for both long horizon planning tasks and information gathering tasks.
Paper (author version) is here.
Multiple Kernel Learning
Project
report and presentation are available: [report]
[slides].
Multiple kernel learning (MKL) aims at simultaneously learning a kernel and the associated predictor in supervised learning settings. SMOlike algorithm can be used to obtain the optimal combination of kernels. In this project, we demonstrate MKL algorithms by comparing its performance with other algorithms on various data sets. We also learn behaviours of MKL with various values of parameters and combinations of kernels.
The basic idea is to jointly learn kernel and SVM parameters from training data {(x_{i},y_{i})}. Given n m × m kernel matrices, K_{1},…K_{n}, we consider their linear combination:

(1) 
We are to learn the optimal weights β ∈ ℝ^{n}. This corresponds to learning a standard SVM in the feature space formed by concatenating the vectors ϕ_{k}. The primal can be formulated as:

(2) 


Figure 1:
Comparison
on 7 UCI Data Sets by Accuracy (%)








Australian 
Breast 
Diabetes 
German 
Heart 
Ionosphere 
Liver 

# Instances 
690 
683 
768 
1000 
270 
351 
270 
# Features 
14 
10 
8 
24 
13 
34 
13 








Linear SVM 
85.0725 
96.3397 
76.0417 
77.3 
84.0741 
85.755 
65.7971 








Polynomial Kernel 
85.0725 
97.0717 
77.0833 
74.6 
84.4444 
88.8889 
67.5362 








RBF Kernel 
85.5072 
96.1933 
75.7813 
75.6 
76.6667 
94.0171 
69.2754 








MKL 
85.3623 
97.0717 
76.9531 
76.4 
86.1111 
94.8718 
69.2754 








Figure 2:
Behaviours
in terms of Accuracy (%) on Sonar Data Set








# Kernels 
… 
6 
7 
8 
9 
10 
… 








Accuracy(%) 
… 
88.9423 
90.8654 
91.3462 
88.9423 
89.4231 
… 








Figure 3:
Behaviours
in terms of Accuracy (%) According to p and
Number of Kernels














1.1 
1.33 
1.67 
2 
2.33 
2.67 
3 
4 
5 
6 
10 














1 
75.9615 
75.9615 
75.9615 
75.9615 
75.9615 
75.9615 
75.9615 
75.9615 
75.9615 
75.9615 
75.9615 

2 
79.8077 
79.8077 
79.8077 
79.8077 
79.8077 
79.8077 
79.8077 
79.8077 
79.8077 
79.8077 
79.8077 

3 
81.25 
80.2885 
81.25 
80.7692 
80.7692 
80.7692 
80.2885 
80.2885 
80.2885 
79.8077 
79.8077 

4 
87.0192 
86.5385 
86.5385 
86.0577 
86.0577 
86.0577 
86.0577 
86.0577 
85.0962 
85.0962 
85.0962 

5 
88.9423 
88.4615 
88.9423 
88.9423 
89.4231 
88.9423 
88.9423 
89.4231 
88.9423 
88.9423 
88.4615 

6 
88.9423 
89.9038 
88.9423 
88.9423 
88.4615 
88.4615 
87.9808 
88.9423 
88.9423 
88.9423 
89.9038 

7 
89.4231 
88.9423 
90.8654 
90.8654 
90.8654 
90.8654 
90.3846 
90.3846 
90.3846 
89.9038 
89.9038 

8 
88.9423 
89.4231 
89.9038 
91.3462 
91.3462 
91.8269 
91.8269 
91.3462 
91.3462 
91.3462 
91.3462 

9 
87.9808 
88.4615 
88.9423 
88.9423 
90.3846 
90.8654 
90.8654 
90.8654 
91.3462 
91.3462 
91.3462 

10 
87.5 
87.9808 
88.9423 
89.4231 
90.3846 
90.3846 
90.3846 
90.3846 
90.3846 
90.3846 
90.8654 

15 
87.0192 
87.5 
87.9808 
87.9808 
87.9808 
87.9808 
88.4615 
88.4615 
88.4615 
88.4615 
88.4615 

40 
87.0192 
86.5385 
86.5385 
86.0577 
85.5769 
85.5769 
86.0577 
85.5769 
85.5769 
85.5769 
85.5769 














Monte Carlo Localization for ROS (Robot Operating System)
Code is available: [code] [help].
In this project, we implement a particle filter for localisation (Monte Carlo localisation), which functions similarly as the existing AMCL package.
A Motion Planner in Polygonal Environment
Virtual machine file (.vdi) with implementation is available here (1.6G).
In this project, we plan for navigation of a robot in a polygonal world by carrying out heuristic search in the adjacency graph for quadtree representation of the configuration space. With the help of CGAL (Computational Geometry Algorithms Library), we could easily calculate the Minkowski Sum of polygons.