Back to Main

 

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 “macro-actions” 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 multi-purpose POMDP solver, providing state-of-the-art 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. SMO-like 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 {(xi,yi)}. Given n m × m kernel matrices, K1,…Kn, we consider their linear combination:

     ∑n
K  =    βkKk,βk ≥ 0
     k=1

(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-ϕk. The primal can be formulated as:

         1 ∑n  T       ∑m     λ-∑n  p 2
w,b,mξ≥i0n,β≥02    wkwk + C    ξi + 2(  βk)p
           k=1n        i=1      k=1
             ∑  ∘ --- T
       s.t. yi(    βkw kϕk(xi) +b) ≥ 1- ξi
             k=1

(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









 

uci

 

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









 

2

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

 














PICT

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














3

 

 

 

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.

 

localization1

localization2

 

 

 

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.

 

planner