Optimization
Home Schedule Projects Evaluation and Policy Resources Announcements
Projects

Team-based projects are integrated as an essential part of the course. These projects help students to get hands-on experience in applying different metaheuristic technqiues studied in this course in solving combinatroial problems. Students select one of the problems listed below for which they will undertake an independent investigation and apply the studied algorithms in the course to solve it. Course instructor and TAs will provide support to help the students with searching and using the literature, analyzing the challenging aspects of the problem and writing the final report of the project. The programming parts of the project must be implemented in Matlab/Octave.

The following is the definite list of projects. Registration is on a first come, first served basis. To register, please fill in the registration form before Friday May 23, 2014 and submit it to your course instructor's eamil address. Please check below the registration status before selecting the project.

List of available projects:
ID Project title and description Assignement
1
Railway Scheduling Problem: A feasible train timetable should specify for each train the departure and arrival times to each dependency of the network in such a way that the line capacity and other operational constraints are taken into account. Optimizing train timetables on a single line track is known to be NP-hard with respect to the number of conflicts in the schedule. Ref. [Dario Pacciarelli and Marco Pranzo, "A Tabu Search Algortihm for the Railway Scheduling Problem, MIC’2001 - 4th Metaheuristics International Conference.]

Assigned to:

  1. Trevor Jones
  2. Nick O'Hara
  3. Michal Dedys
  4. William Lindsay
  5. ---
2
Flight Scheduling Problem: Given demand and revenues for every origin-destination pair over time-of-the-day and day-of-the-week, route information distances, times, operating restrictions, aircraft characteristics and operating costs and operational and managerial constraints. Find a set of flights with departure and arrival times and aircraft assignment which maximize profits. Ref. [Ghizlane Bencheikh, Jaouad Boukachour and Ahmed EL Hilali Alaoui, "Improved Ant Colony Algorithm to Solve the Aircraft Landing Problem," International Journal of Computer Theory and Engineering, Vol. 3, No. 2, April 2011 ISSN: 1793-8201] and [F. Mokhatab Rafiei, S.M. Manzari, M. Khashei, "Scheduling Flight Perturbations with Ant Colony Optimization Approach," International Journal of Computer Science and Artificial Intelligence ].

Assigned to:

  1. Piyush Gadigone
  2. Yash Malik
  3. Satyam Gupta
  4. Khushi Sohi
  5. Sugandha Sharma
3
Crew Scheduling: is the process of assigning crews to operate transportation systems, such as rail lines or aircraft. In this problem, within a set of constraints and rules, move a set roster of people with certain qualifications, from place to place with the least amount of personnel and aircraft or vehicles in the least amount of time. Ref. [A. Azadeha, M. Hosseinabadi Farahania, H. Eivazyb, S. Nazari-Shirkouhia, G. Asadipoura, "A hybrid meta-heuristic algorithm for optimization of crew scheduling Applied Soft Computing, Volume 13, Issue 1, January 2013, Pages 158–164.], [Panta Lucica, Dusan Teodorovica, "Simulated annealing for the multi-objective aircrew rostering problem," Transportation Research Part A 33 (1999) 19-45] and [MING-SHEN JIAN, and TA-YUAN CHOU, "Multiobjective Genetic Algorithm to Solve the Train Crew Scheduling Problem," NEW ASPECTS of SYSTEMS THEORY and SCIENTIFIC COMPUTATION.].

Assigned to:

  1. Divij Rajkumar
  2. Warren Smith
  3. Steven Vincent
  4. Masroor Hasan
  5. Joe Manduca
4
Timetabling Problem (TTP): The course timetabling problem involves resource allocation constraints; under limited resources the conditions with regard to teachers, courses, students, and teaching facilities have to be met. In this problem, it is given a list of m teachers, a list of p classes involved a list of n weekly teaching hours for each class the curriculum of each class, that is the list of the frequencies of the teachers working in the class and a set of hard and/or soft contratints. Ref. [Ruey-Maw Chen and Hsiao-Fang Shih, "Solving University Course Timetabling Problems Using Constriction Particle Swarm Optimization with Local Search," Algorithms 2013, 6, 227-244; doi:10.3390/a6020227.]

Assigned to:

  1. Elisa Lou
  2. Aaron Pang
  3. Maxim Rabiciuc
  4. Ajay Sreenivasan
  5. Eric Tam
5
Drilling of Printed Circuit Boards: To connect a conductor on one layer with a conductor on another layer, or to position the pins of integrated circuits, holes have to be drilled through the board. The holes may be of different sizes. To drill two holes of different diameters consecutively, the head of the machine has to move to a tool box and change the drilling equipment. This is quite time consuming. Thus it is clear that one has to choose some diameter, drill all holes of the same diameter, change the drill, drill the holes of the next diameter, etc. The aim is to minimize the travel time for the machine head. For more info: [Grötschel, M.; M. Jünger & G. Reinelt (1991). Optimal Control of Plotting and Drilling Machines: A Case Study. Mathematical Methods of Operations Research, Vol. 35, No. 1, (January, 1991), pp.61-84.]  

Assigned to:

  1. Robert Dandy
  2. Steven Meyer
  3. Jacob Simon
  4. ---
  5. ---
6
Order-picking Problem in Warehouses: This problem is associated with material handling in a warehouse. Assume that at a warehouse an order arrives for a certain subset of the items stored in the warehouse. Some vehicle has to collect all items of this order to ship them to the customer. The relation to the TSP is immediately seen. The storage locations of the items correspond to the nodes of the graph. The distance between two nodes is given by the time needed to move the vehicle from one location to the other. The problem of finding a shortest route for the vehicle with minimum pickup time can now be solved as a TSP. See [van Dal, R. (1992). Special Cases of the Traveling Salesman Problem, Wolters-Noordhoff, Groningen.], [Matic Horvat. An Approach to Order Picking Optimization in Warehouses. DIPLOMA THESIS, University of Ljubljana, 2012] and [Yuanbin Hou1, Long Li1, Lei Wang, "Picking Routes Optimization of Automated Warehouse Based on Parthenon Genetic Ant Colony Algorithm," 2012 International Conference on Convergence Information Technology Lecture Notes in Information Technology, Vol.19, 2012.]

Assigned to:

  1. Justin Cheung
  2. Stephen Chou
  3. Pulkit Kakkar
  4. Evgeny Nam
  5. Yen-Cheng (Tony) Wu
7
Printing Press Scheduling Problem: in this problem there exist five pairs of cylinders between which the paper rolls and both sides of a page are printed simultaneously. There exist three kind of forms, namely 4-, 6- and 8-page forms, which are used to print the editions. The scheduling problem consists of deciding which form will be on which run and the length of each run. In the mTSP vocabulary, the plate change costs are the inter-city costs. For more details [Gorenstein, S. (1970). Printing press scheduling for multi-edition periodicals. Management Science, Vol. 16, No. 6, pp.B373–83 and Carter, A.E. & Ragsdale, C.T. (2002). Scheduling pre-printed newspaper advertising inserts using genetic algorithms. Omega, Vol. 30, pp. 415–21].  
8
Credit Card Scoring: is a way of separating specific subgroups in a population of objects (such as applications for credit), which have significantly different credit risk characteristics. It is a classification problem that can be defined by a classification function assigning each object some categorical value called the class number. A utility function is used for separating objects belonging to different sets. Values of utility functions for objects from one class should be in the same range. “The best” utility function in some class is found by minimizing the error of misclassification. Ref. [Vladimir Bugera, Hiroshi Konno and Stanislav Uryasev, "Credit cards scoring with quadratic utility functions", Journal of Multi-Criteria Decision Analysis, Special Issue: MCDA Methodologies in Finance Volume 11, Issue 4-5, pages 197–211, July - October 2002], [Ekrem Duman, Ilker Elikucuk, "Solving Credit Card Fraud Detection Problem by the New Metaheuristics Migrating Birds Optimization," Lecture Notes in Computer Science Volume 7903, 2013, pp 62-71] and [ZVI DREZNER, GEORGE A. MARCOULIDES and MARK HOVEN STOHS, "Financial Applications of a Tabu Search Variable Selection Model", JOURNAL OF APPLIED MATHEMATICS AND DECISION SCIENCES, 5(4), 215–234, 2001.]

Assigned to:

  1. Christopher Chong
  2. Jeremy Simpson
  3. Yi Hao Dong
  4. Christopher Fayoux
  5. Junwin Li
9
Elevator Dispatching Problem: Elevator dispatching is a good example of a stochastic optimal control problem of economic importance that is too large to solve by classical techniques such as dynamic programming. The objective of elevator dispatching is to provide passengers with the shortest waiting times and the shortest time to destination. Ref.: [Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. The MIT Press] and [Berna Bolata, Pablo Cortés, “Genetic and tabu search approaches for optimizing the hall call—Car allocation problem in elevator group systems,” Applied Soft Computing 11 (2011) 1792–1800.]

Assigned to:

  1. Douglas Lee
  2. Andrew Hassan
  3. Garrett Everding
  4. Samuel Cheung
  5. Ke Jian
10
Job Shop Scheduling Problem: Job shop scheduling is an optimization problem in which n jobs J1, J2, ..., Jn of varying sizes are given. These jobs need to be scheduled on m identical machines, while trying to minimize the makespan. The makespan is the total length of the schedule (that is, when all the jobs have finished processing). Ref. [Amin Jamili & Mohammad Ali Shafia & Reza Tavakkoli-Moghaddam, "A hybrid algorithm based on particle swarm optimization
and simulated annealing for a periodic job shop scheduling problem", Int J Adv Manuf Technol], [A. Garrido, M. A. Salido, F. Barber and M. A. López, "Heuristic Methods for Solving Job-Shop Scheduling Problems", ] and [Milos Seda, "Mathematical Models of Flow Shop and Job Shop Scheduling Problems," World Academy of Science, Engineering and Technology 31 2007].

Assigned to:

  1. Rui Zhao
  2. Libin Bai
  3. Yuanqi Li
  4. Debin Li
  5. Bolun Yao
11
Assembly Line Balancing Problem (ALBP): An assembly line is a sequence of workstations connected together by a material handling system. It is used to assemble components into a final product. Balancing assembly lines is a difficult combinatorial optimization problem arising frequently in manufacturing. The Assembly Line Balancing Problem (ALBP) addresses assigning tasks (work elements) to workstations that minimize the amount of the idle time of the line, while satisfying specific constraints. Ref. [Qi Lv, "Simple Assembly Line Balancing Using Particle Swarm Optimization Algorithm," International Journal of Digital Content Technology and its Applications. Volume 5, Number 6, June 2011] and [Uğur ÖZCAN, Hakan ÇERÇĐOĞLU, Hadi GÖKÇEN, Bilal TOKLU, "A Tabu Search Algorithm for the Parallel Assembly Line Balancing Problem," G.U. Journal of Science, 22(4): 313-323, 2009].  

Assigned to:

  1. Kefan Xie
  2. Rey David Wu
  3. Varun Dave
  4. James Li
  5. ---
12
Quadratic Assignment Problem (QAP): Given a number of n activities assigned to n locations. A distance is specified among each pair of locations, and weight or flow is specified among pairs of activities (representing transfer of data, material, etc.) The problem is to assign all activities to different locations (permutation) with the goal of minimising the sum of the distances multiplied by the corresponding flows. Quadratic: cost function depends on multiplication of distances by flows. Ref. [Samuel Gabrielsson. A Parallel Tabu Search Alglorithm for the Quadratic Assignment Problem. September 2007], [Gerald Paul, "Comparative performance of tabu search and simulated annealing heuristics for the quadratic assignment problem," Operations Research Letters 38 (2010) 577–581] and [Zvi Drezner , "Tabu Search and Hybrid Genetic Algorithms for Quadratic Assignment Problems," : Local Search Techniques: Focus on Tabu Search, Book edited by: Wassim Jaziri, ISBN 978-3-902613-34-9, pp. 278].

Assigned to:

  1. Aran Savundararasa
  2. Patrick Wojcik
  3. Sivaskanthan Jegatheswaran
  4. Amy Chang
  5. Hongzhe Yang 
13
School Bus Routing Problem: The objective of the scheduling is to obtain a bus loading pattern such that the number of routes is minimized, the total distance travelled by all buses is kept at minimum, no bus is overloaded and the time required to traverse any route does not exceed a maximum allowed policy. For problem modeling, see [Angel, R.D.; Caudle, W.L.; Noonan, R. & Whinston, A. (1972). Computer assisted school bus scheduling. Management Science, Vol. 18, pp.279–88.], [Michela Spada, Michel Bierlaire, Thomas Liebling, "Decision-aid Methodology for the School BusRouting and Scheduling Problem," STRC 3rd Swiss Transport Research Conference Monte Verita / Ascona, March 19-21, 2003] and Yindong Shen . Tabu Search for Bus and Train Driver Scheduling. PhD Thesis, The University of Leeds, 2001.

Assigned to:

  1. Shival Maharaj
  2. Akif Hossain
  3. Nicholas Kim
  4. James Kim
  5. Abdulmajeed Al-Dhalaan
14
Auto-tuning of a PID (Proportional-Integral-Derivative) Controller: PID controller is a generic control loop feedback mechanism (controller) widely used in industrial control systems. It is the most commonly used feedback controller. By tuning the three parameters in the PID controller algorithm, the controller can provide control action designed for specific process requirements. The response of the controller can be described in terms of the responsiveness of the controller to an error, the degree to which the controller overshoots the setpoint and the degree of system oscillation. Alaa Khamis, Adavanced Mechatronics Systems, Germanu University in Cairo, Lecture L7-Dynamic Compensation-II, Fall 2013.

Assigned to:

  1. Nikolai Semenenko
  2. Didier Smith
  3. Josip Vulic
  4. Glenn Christian Sumido
  5. Shale Craig
15
Voice Activity Detector (VAD): a.k.a speech activity detection or speech detection is the problem of determining the presence of speech periods in a given audio signal. Several VAD techniques with different levels of recall and precision have been proposed. There is a number of evaluations metrics that can be used to quantitatively evaluate the efficiency of the VAD such as FEC, MSC, OVER and NDS. FEC (Front end clipping) is the clipping due to speech being misclassified as non-speech in the onset regions. MSC (Mid speech clipping) is the clipping due to speech being misclassified as non-speech in the speech regions. OVER (Carry over) is Non-speech interpreted as speech in the offset regions. NDS (Noise detected as speech) is Non-speech interpreted as speech in the non-speech regions. FEC and MSC are performance indicators similar to recall, while OVER and NDS are the break-down of precision [Pham Chau Khoa. Noise Robust Voice Activity Detection. Master's thesis, Nanyang Technological University, 2012]. Recall is more important than precision and it's related to the false alarms. Labelling speech as non-speech is more risky than labelling non-speech as speech. The VAD error rate (VER) and the false trigger rate (FTR) can be defined as follows: VER=FEC+MSC and FTR=OVER+NDS. It is always recommendable to optimally tune the parameter of the VAD in such a way that minimizes the sum of VAD error rate and false trigger rate. Ref.[Pham Chau Khoa. Noise Robust Voice Activity Detection. Master's thesis, Nanyang Technological University, 2012.]

Assigned to:

  1. Michael Thiessen
  2. Roxanne Guo
  3. Fang Wang
  4. Kyle Olive
  5. Sean Aubin

16

Combinatorial Optimization in VLSI Design: chip is composed of basic elements, called cells, circuits, boxes, or modules. They usually have a rectangular shape, contain several transistors and internal connections, and have at least two pins (in addition to power supply). The pins have to be connected to certain pins of other cells by wires according to the netlist. A net is simply a set of pins that have to be connected, and the netlist is the set of all nets. The basic placement task is to place the cells legally "without overlaps" in the chip area. A feasible placement determines an instance of the routing problem, which consists of implementing all nets by wires. The quality of a placement depends on the quality of a wiring that can be achieved for this instance. For several reasons it is usually good if the wire length (the total length of the wires connecting the pins of a net) is as short as possible. [Ref.: Stephan Held, Bernhard Korte, Dieter Rautenbach, and Jens Vygen, "Combinatorial Optimization in VLSI Design"]  

17

Hot Rolling Scheduling Problem: In the iron and steel industry, orders are scheduled on the hot rolling mill in such a way that the total set-up cost during the production can be minimized. The solution of the model will yield a complete schedule for the hot strip rolling mill. The details of a recent application of modeling such problem can be read from [Tang, L.; Liu, J.; Rong, A. & Yang, Z. (2000).A multiple traveling salesman problem model for hot rolling scheduling in Shangai Baoshan Iron & Steel Complex. European Journal of Operational Research, Vol. 124, pp. 267–82.], [L. Nolle, D. A. Armstrong, A. A. Hopgood and J. A. Ware, "SIMULATED ANNEALING AND GENETIC ALGORITHMS APPLIED TO FINISHING MILL OPTIMISATION FOR HOT ROLLING OF WIDE STEEL STRIP,"International Journal of Knowledge-Based Intelligent Engineering Systems, Vol. 6, No. 2, April 2002] and [Leo Lopez, Michael W. Carter, Michel Gendreau, "The hot strip mill production scheduling problem: A tabu search approach," European Journal of Operational Research 106 ( 1998) 3 17-335].  

Assigned to:

  1. Austin Lee
  2. Tian Yu Zhang
  3. Collins Chung
  4. David Wang
  5. ---
18
Overhauling Gas Turbine Engines: To guarantee a uniform gas flow through the turbines there are nozzle-guide vane assemblies located at each turbine stage. Such an assembly basically consists of a number of nozzle guide vanes affixed about its circumference. All these vanes have individual characteristics and the correct placement of the vanes can result in substantial benefits (reducing vibration, increasing uniformity of flow, reducing fuel consumption). The problem of placing the vanes in the best possible way can be modeled as a TSP with a special objective function. Ref. [Plante, R.D.; T.J. Lowe & R. Chandrasekaran (1987). The Product Matrix Traveling Salesman Problem: An Application and Solution Heuristics. Operations Research, Vol. 35, pp.772-783.].  
19
Computer Wiring: Modules are located on a computer board and a given subset of pins has to be connected. In contrast to the usual case where a Steiner tree connection is desired, here the requirement is that no more than two wires are attached to each pin. Hence we have the problem of finding a shortest Hamiltonian path with unspecified starting and terminating points. A similar situation occurs for the so-called testbus wiring. To test the manufactured board one has to realize a connection which enters the board at some specified point, runs through all the modules, and terminates at some specified point. For each module we also have a specified entering and leaving point for this test wiring. This problem also amounts to solving a Hamiltonian path problem with the difference that the distances are not symmetric and that starting and terminating point are specified. Ref. [Lenstra, J.K. & A.H.G. Rinnooy Kan (1974). Some Simple Applications of the Travelling Salesman Problem. BW 38/74, Stichting Mathematisch Centrum, Amsterdam.].

Assigned to:

  1. Keefer Davies
  2. Andrew Dawidek
  3. Pardeep Singh
  4. Brian Chow
  5. ---

20

Wind Park Design Problem: This project addresses the problem associated with the optimal wind park design. A combinatorial optimization model for wind turbines type and number choice and placement considering the given wind conditions and wind park area will be developed. Ref.: [Ivan Mustakerov and Daniela Borissova, "Wind turbines type and number choice using combinatorial optimization", Renewable Energy 35 (2010) 1887–1894 and [Andrew Kusiak, Zhe Song, "Design of wind farm layout for maximum wind energy capture," Renewable Energy 35 (2010) 685–694].

Assigned to:

  1. Mai Wang
  2. Chao Gao
  3. Yi Kun Song
  4. Hong Wen Zhu
  5. Qi Feng Liu
21
Vehicle Suspension Design: The primary function of a suspension system of a vehicle is to isolate the road excitations experienced by the tires from being transmitted to the passengers. This design problem can be seen as an optimization problem with two objectives: minimizing the maximum bouncing acceleration of the sprung mass and minimizing average suspension displacement subject to a number of constraints. The constraints arise from the practical kinetic and comfortability considerations, such as limits of the maximum vertical acceleration of the sprung mass and the suspension working space. For more details [A.E. Baumal, J.J. McPhee, P.H. Calamai, “Application of genetic algorithms to the design optimization of an active vehicle suspension system ,” Computer Methods in Applied Mechanics and Engineering, Volume 163, Issues 1–4, 21 September 1998, Pages 87–94.]  
22
Robot Path Planning Problem: This problem is an interesting problem that has been studied extensively over the last two decades. This problem addresses how to find a collision-free path for a mobile robot from a start position to a given goal position, amidst a collection of obstacles. Path planning can be seen as an optimization problem which aims at improving some system objectives with several constraints. System objectives may be the travelling distance, travelling time, and consuming energy. However, the travelling distance is the most common objective. Beside this, the necessity of considering collisions avoidance and path smoothness makes the problem becoming more challenging. Ref. [Yun-Qian Miao Miao, Alaa Khamis, Mohamed Kamel, Fakhri Karray, “A Novel Approach to Path Planning for Autonomous Mobile Robots”, Journal of Control and Intelligent Systems, 2011.], [Yun-Qian Miao, Alaa Khamis, Mohamed Kamel, Fakhri Karray, "Global Optimal Path Planning for Mobile Robots based on Hybrid Approach with High Diversity and Memorization," International Conference on Autonomous and Intelligent Systems (AIS 2011), June 22-24, 2011, Burnaby, BC, Canada] and [H. Mostafa, A. Hussein, M. Badrel-din, O. Sultan and A. Khamis, “Metaheuristic Optimization Approach to Mobile Robot Path Planning”, International Conference on Engineering and Technology (ICET2012), New Cairo, 2012].

Assigned to:

  1. Nicolas Arciniega
  2. Nicholas Champion
  3. David Garcia
  4. Tawhid Mumtaz-Shah
  5. Gregory McGuire
23
Mission Planning Problem: The mission planning problem consists of determining an optimal path for each army men (or planner) to accomplish the goals of the mission in the minimum possible time. In this problme, there are n planners, m goals which must be visited by some planners, and a base city to which all planners must eventually return. Simila routing problems arearising in the planning of unmanned aerial vehicle applications. See [Yu, Z.; Jinhai, L.; Guochang, G.; Rubo, Z. & Haiyan, Y. (2002). An implementation of evolutionary computation for path planning of cooperative mobile robots.Proceedings of the fourth world congress on intelligent control and automation, Vol. 3, pp. 1798–802.], [Brummit, B. & Stentz, A. (1998). GRAMMPS: a generalized mission planner for multiple mobile robots. Proceedings of the IEEE international conference on robotics and automation, May 1998.], [Ryan, J.L.; Bailey, T.G.; Moore, J.T & Carlton, W.B. (1998). Reactive Tabu search in unmanned aerial reconnaissance simulations. Proceedings of the 1998 winter simulation conference, Vol. 1, pp . 873–9.] and [Brummit, B. & Stentz, A. (1996). Dynamic mission planning for multiple mobile robots. Proceedings of the IEEE international conference on robotics and automation, April 1996.].

Assigned to:

  1. Alex Laviolette
  2. Shi Shi
  3. Kyle Bennet
  4. Adam Watson
  5. Joe Price
24
Multirobot Control: Unintelligent carts are commonly found in large airports. Travelers pick up carts at designated points and leave them in arbitrary places. It is a considerable task to re-collect them. It is, therefore, desirable that intelligent carts (intelligent robots) draw themselves together automatically. Using mobile software agents to locate robots scattered in a field, e.g. an airport, and make them autonomously. The objective is to determine the moving behaviors of smart carts by using an metaheuristic optimization-based clustering algorithm. Resources must be used efficiently to maximize the benefit of utilizing a multirobot team. For example, in search and rescue time is of the utmost importance, while for planetary exploration fuel efficiency may be a primary concern. Ref. [Yasushi Kambayashi, Yasuhiro Tsujimura, Hidemi Yamachi, Munehiro Takimoto and Hisashi Yamamoto, “Design of a Multi-Robot System Using Mobile Agents with Ant Colony Clustering”, Proceedings of the 42nd Hawaii International Conference on System Sciences – 2009][Alaa Khamis, Cooperative Multirobot Systems, Plenary Talk at IAC2014]

Assigned to:

  1. Mohammed Sadat Islam
  2. Matthew Richard Longo
  3. Naveen Narayanan
  4. Johnny Wang
  5. Gordon Zhou
25
Collective Robotic Search (CRS): A group of unmanned mobile robots are searching for a specified target in a high risk environment. Assumptions: A number of robots/particles are randomly dropped into a specified area and flown through the search space with one new position calculated for each particle per iteration; The coordinates of the target are known and the robots use a fitness function, in this case the Euclidean distance of the individual robots relative to the target, to analyze the status of their current position; Obstacle's boundary coordinates are known. Ref. [Smith, L., Venayagamoorthy, G. K. and Holloway, P. (2006): Obstacle Avoidance in Collective Robotic Search Using Particle Swarm Optimization. IEEE Swarm Intelligence Symposium, Indianapolis, Indiana, USA, May 2006.], [Alaa Khamis, Cooperative Multirobot Systems, Plenary Talk at IAC2014] and [Qing-Hao Meng, Wei-Xing Yang, Yang Wang, Ming Zeng, " Multi-robot odor-plume tracing in indoor natural airflow environments using an improved ACO algorithm 2010 IEEE International Conference on Robotics and Biomimetics (ROBIO), 2010.]

Assigned to:

  1. Manodasan Wignarajah
  2. Mohammad Khan
  3. Arvin Aminpour
  4. Alireza Pourhaj
  5. Ragulan Ravinthiran
26
Multiple Targets Clustering Problem: Clustering in a d-dimensional Euclidean space is the process of partitioning a given set of n points into a number, say k, of groups (or clusters) based on some similarity metric between objects. Suppose that it is required to track n targets using k mobile trackers. If the number of available trackers is less than the number of targets to be tracked, the targets can be grouped into a number of clusters equal to the number of trackers. Then the tracker can track the centroid of the cluster instead of the target itself. This clustering process is based on the positions of targets. Ref. [Ujjwal Maulik, Sanghamitra Bandyopadhyay, "Genetic algorithm-based clustering technique", Pattern Recognition 33 (2000)1455-1465.].

Assigned to:

  1. Zhechen Du
  2. Lingyuan Li
  3. Zhengfang Duanmu
  4. Yijie Liang
  5. Tao Shen
27
Complex Task Allocation Problem: In mobile surveillance systems, complex task allocation addresses how to optimally assign a set of surveillance tasks to a set of mobile sensing agents to maximize overall expected performance, taking into account the priorities of the tasks and the skill ratings of the mobile sensors. Ref. Alaa Khamis, Ahmed Elmogy and Fakhreddine Karray, "Complex Task Allocation in Mobile Surveillance Systems," Journal of Intelligent and Robotic Systems, Springer], [Mohamed Badreldin, Ahmed Hussein and Alaa Khamis, "A Comparative Study between Optimization and Market-based Approaches to Multi-robot Task Allocation," Advances in Artificial Intelligence Journal, 2013.] and [Alaa Khamis, Cooperative Multirobot Systems, Plenary Talk at IAC2014].

Assigned to:

  1. Alexander Maguire
  2. Dane Carr
  3. Austin Dobrik
  4. Lucas Wojciechowski
  5. Ariel Weingarten
28
Camera Placement for Airport Surveillance: Multi-sensor surveillance systems are used to monitor or observe the behaviour of persons, processes, places, objects, etc. to determine whether they are functioning normally or if there is any deviation from their standard behaviour. These systems include a vast array of static and mobile sensors. Static sensors include, but not limited to, light sensors, temperature sensors, perimeter intrusion detector, sound sensors, fire detectors and cameras. Static sensor placement has an enormous impact on the performance of the surveillance system. Static sensor placement problem can be seen as a combinatorial problem that involves the placement of a set of N sensors with different fields of view in a set of M areas of interest. Suggested reading [Mohammad Reza Shams Amiri. Automated Camera Placement using Hybrid Particle Swarm Optimization. European Master in Computer Science, Blekinge Institute of Technology, 2014] and [N. Conci and L. Lizzi, |CAMERA PLACEMENT USING PARTICLE SWARM OPTIMIZATION IN VISUAL SURVEILLANCE APPLICATIONS", ICIP 2009].

Assigned to:

  1. Nicholas Lun
  2. Johnny Li
  3. Wilson Tran
  4. Freeman Kam
  5. Kent Ma
29
Political Districting Problem: is defined as aggregating n sub-regions of a territory into m electoral districts subject to the following constraints: 1. The districts should have near-equal voting population, 2. The socio-economic homogeneity inside each district as well as the integrity of different communities should be maximized, 3. The districts have to be compact and the sub-regions of each district have to be contiguous and 4. Sub-regions should be considered as indivisible political units and their boundaries should be respected. Ref. [Burcin Bozkaya, Erhan Erkut, Gilbert Laporte, "A tabu search heuristic and adaptive memory procedure for political districting European Journal of Operational Research 144 (2003) 12-26] and [Sean L. Forman and Yading Yue, "Congressional Districting Using a TSP-Based Genetic Algorithm"].

Assigned to:

  1. Raymond DiCecco
  2. Joel Phillip
  3. Theo Gugoiu
  4. Jacob Baechler
  5. Saba Z. Saba
30
Communication Relay for Unmanned Aerial Vehicles in Autonomous Search and Rescue Mission: The objective of this project is to simulate search and rescue scenarios where autonomous unmanned aerial vehicles are deployed to locate multiple rescue targets. When a target is found, the swarm of micro-aerial vehicles (MAVs) self-organizes to utilize their range-limited communication capabilities for setting up a communication relay network between the target and the base. This solution is appropriate for real-world situations where rescue targets are trapped on intraversable terrain with a limited radius of communication. Ref. [Sabine Hauert, Laurent Winkler, Jean-Christophe Zufferey and Dario Floreano, "Ant-based swarming with positionless micro air vehicles for communication relay," Swarm Intell (2008) 2: 167–188], [Wave Relay MANET Communication System Connects Swarming Unmanned Aerial Vehicles Persistent Systems, LLC, 2007] and [Alaa Khamis, Cooperative Multirobot Systems, Plenary Talk at IAC2014].

Assigned to:

  1. Robert Tran
  2. Anthony Ng
  3. Aaron Chung
  4. Asif Arman
  5. Avishesh Shah
31
Design of Global Navigation Satellite System Surveying (GNSS) Networks: A GNSS is a space-based satellite system which provides coverage for all locations worldwide and is quite crucial in real-life applications such as early warning and management for disasters, environment and agriculture monitoring, etc. The goal of surveying is to determine the geographical positions of unknown points on and above the earth using satellite equipment. These points, on which receivers are placed, are co-ordinated by a series of observation sessions. When there are multiple receivers or multiple working periods, the problem of finding the best order of sessions for the receivers can be formulated as an mTSP. For technical details refer [Saleh, H.A. & Chelouah, R. (2004). The design of the global navigation satellite system surveying networks using genetic algorithms. Engineering Applications of Artificial Intelligence, Vol. 17, pp. 111–22.].  Assigned to:
  1. Pranjal Singh
  2. Sola Ogunsakin
  3. Raul Jonathan Acevedo
  4. Ryan Zhang
  5. Greg O'Grady
32
Crowd Behavior During Emergency Evacuations: In case of mass emergencies and disasters, it has been observed that most victims were injured or killed by the misbehaviors of the crowd, rather than the actual cause (such as fire or explosion) of the disaster. Planning an evacuation strategy from public areas (such as buildings, shopping centers, stadiums, subways, train stations, airports, etc.) is a formidable problem due to the non-adaptive behaviors of the crowds and the unpredictable dynamics of the environment. Non-adaptive crowd behaviors refer to the destructive actions that a crowd may experience in emergency situations, such as stampede, pushing, knocking, and trampling on others, etc. These actions are responsible for a large number of injuries and deaths in man-made and natural disasters. Simulating human behaviors during emergency situations can help in predicting occupants’ distribution and planning an effective evacuation strategy. Understanding this behavior can also help in designing building’s emergency exits, fire protection design and in emergency preparation.

Assigned to:

  1. Anushervon Saidmuradov
  2. Aayushi Kaushik
  3. Desiyee Collier
  4. Sarah Chan
  5. Nigel Chan
33
A Bio-Inspired Coordination Mechanism for a Swarm of Miniature Robots:Coordination addresses the interdependency management among the cooperative or competitive entities of the system in order to achieve their goals. The objective of this project is to design a bio-inspired coordination algorithm that can be used to manage a group of tiny robots in a search and rescue mission. The algorithm will be based on understanding the crowd dynamics during emergency evacuation. Simulating this behavior can be useful in predicting occupants' distribution and the whole evacuation process. This simulation model can be applied in fire protection design, emergency preparation and planning an evacuation strategy from public areas (such as buildings, stadiums, subways, train stations, shopping malls, airports, etc.).

Assigned to:

  1. Shawn Tariq
  2. Adnan Alam
  3. Pranav chadha
  4. Michael Orschel
  5. Stephen Louli
34
Trajectory Planning and Assignment in Multirobot Systems: This problem addresses tasking large numbers of homogenous robots to move to a set of specified goal locations, addressing both the assignment and trajectory planning subproblems concurrently. This is related to the standard linear Euclidean assignment problem except that the solution to the trajectory generation subproblem must result in time-parameterized trajectories and guarantee collision avoidance.. Ref. [Matthew Turpin, Nathan Michael, and Vijay Kumar, "Trajectory Planning and Assignment in Multirobot Systems,"Algorithmic Foundations of Robotics X, Springer Tracts in Advanced Robotics Volume 86, 2013, pp 175-190].), and [Alaa Khamis, Cooperative Multirobot Systems, Plenary Talk at IAC2014].

Assigned to:

  1. Jonathan Wei
  2. Alex Klen
  3. Jacob Abrahams
  4. Sanjay Menakuru
  5. Gurjant Kalsi
35
Design/Research Problem: Identify a combinatorial design/research problem in a pertinent area of academic, industrial or commercial importance for which there is no available solution with reasonable capabilities. Try to solve this problem using one of metaheuristic techniques studied in this course. Students can also select a problem related to their Engineering Design Project course where the studied metaheuristic techniques can be applied.  
 

Projects must be done in group of 5 students. Teamwork helps to achieve more than what could ever be achieved on your own, improve problem solving, foster creativity and innovation and improve decision making. Teams of students must conceive, design and develop the project. Different issues should be considered to form a collaborative team such as responsibility for assignment, team composition (hard and soft skills, previous academic performance, etc.) and the schedule of the team members (how easy to establish regular face-to-face meetings). Once team is formed, students should be willing to subordinate their personal preferences to the decisions of the team, and be willing to compromise in order to achieve a group consensus. As team work should have team rewards, team members will receive a common grade. However a free-riding team member will be penalized if a common and repetitive negative feedback (peer evaluations) received from the other team members. This feedback will be investigated before deciding the penalty. "Coming together is a beginning, keeping together is progress and working together is success", Henry Ford (1863-1947), founder of the Ford Motor Company and father of modern assembly lines.


Project Work Plan: a suggested work plan for the project can be downloaded here ECE457A-Project.pdf.


Project Report: 

The objective of the final project is to provide a comparative study between different meta-heuristic optimization techniques to solve the selected problem. The project report must contain the following sections: 

Summary: The Summary should be a brief version of the full report. It should give the reader an accurate overview. Be brief, but be specific. 

1. Introduction: summarize the importance of the problem you are trying to solve and the reason that motivated you to select this project. Explain what was the problem or challenge that you were given? state the purpose of the project and how did you solve it? Enumerate the objectives of the project and describe in brief the structure of the report. 

2. Literature Review: Conduct a critical survey on similar solutions and explain how your solution extends or differs from these solutions. 

3. Problem Formulation and Modeling: Include the problem statement and describe its model.

4. Proposed Solution:

  • Generate an initial solution.
  • Suggest a cost function (objective function) suitable for this problem.
  • Define a suitable neighborhood operator.
  • Define a suitable solving strategy for this problem.
  • Select your own values for the parameter and explain the basis for your selection.
  • Describe how each algorithm (TS, SA, GA, PSO and ACO) will proceed to solve this problem by performing at least two hand iterations on a reduced version of the problem.
  • Implement the proposed solution using Matlab/Octave.
5. Performance Evaluation: Establish a set of evaluation metrics and run some experiments with different values of algorithm parameters to quantitatively and qualitatively assess the performance of the developed solution using different meta-heuristic optimization techniques. Students must identify the pros and cons of each technique and assess the quality of work as well as its fit with project objectives.

6. Conclusions & Recommendations: summarize the conclusion and future improvement. Explain how did you solve the problem, what problems were met? what did the results show? And how to refine the proposed solution?You may organize ideas using lists or numbered points, if appropriate, but avoid making your report into a check-list or a series of encrypted notes 

References: Every report needs references; in fact, your failure to consult references for guidance may be considered negligence. On the other hand, when you include sentences, photos, drawings or figures from other sources in your report, the complete reference must be cited. Failure to do so is plagiarism, an academic infraction with serious consequences.


Project Delivery: 

In order to complete evaluating the project, each team has to prepare a CD/Memory Stick for the supervisor containing all materials related to the project (complete documentation report according to the course policy mentioned above + a well documented Matlab/Octave code and executable code with UserGuide that shows how to install and use the developed software).