MCTR1005: Optimization Techniques in Mechatronic Systems

Mini-Project	Description	Due Date
1	Tabu Search (TS) Project	March 14
2	Simulated Annealing (SA) Project	April 4
3	Genetic Algorithm (GA) Project	April 21
4	Ant Colony Optimization (ACO) Project	May 13

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 Thursday February 21 and submit it to MCTR1005@gmail.com. To check the registration status, click here.

List of available projects:
1	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.
2	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.
3	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.
4	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.
5	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.
6	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.
7	The 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.
8	The Vehicle Routing Problem (VRP): The VRP consists of determining the routes to be taken by a set of m vehicles satisfying the following conditions: starting and ending at the depot, having minimum travel cost and each customer is visited exactly once by exactly one vehicle.
9	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).
10	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.
11	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.
12	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.
13	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.
14	Travelling Salesman Problem (TSP): Given n cities, a travelling salesman must visit the n cities and return home, making a loop (roundtrip). He would like to travel in the most efficient way (cheapest way or shortest distance or some other criterion). Search space is BIG. For example, for 21 cities there are 21! =51090942171709440000 possible tours. This is NP-Hard problem. TSP is used as a platform for the study of general methods that can be applied to a wide range of discrete optimization problems such as Microchips manufacturing, Assignment of routes for planes of a specified fleet, Permutation flow shop scheduling problem (PFSP), Transportation and Logistics, Overhauling of gas turbine engines and others.
15	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.
16	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.).
17	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"]
18	Wind turbines optimization: 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].
19	Design optimization of Reverse osmosis (RO) desalination systems: RO is a membrane-technology filtration method that removes many types of large molecules and ions from solutions by applying pressure to the solution when it is on one side of a selective membrane. The purpose of this project is to select the optimal RO pressure pump power in kW for maximizing RO productivity subject to a number of constraints.
20	Design Problem: Identify any design problem in mechatronic systems for which there is no available solution with reasonable capabilities. Try to solve this problem using one of metaheuristic optimization techniques studied in this course. Design problems may include, but are not limited to, optimal design of linkages, cams, gears, machine tools, and other mechanical components, packaging design, desalination unit design, solar panels design, design of aircraft and aerospace structures for minimum weight, finding the optimal trajectories of space vehicles, design of pumps, turbines, and heat transfer equipment for maximum efficiency, design of optimum pipeline networks, selection of machining conditions in metal-cutting processes for minimum production cost, controlling the waiting times and queueing in production lines to reduce the costs, etc.
21	Research Problem: Identify a problem related to your current research in a pertinent area of academic, industrial or commercial importance related to robotics and automation for which there is no available solution with reasonable capabilities. Try to solve this problem using one of metaheuristic optimization techniques studied in this course.

Projects must be done in group of minimum 2 and maximum 4 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, the optimal team size (from 2 to 4 students), team composition (hard and soft skills, previous academic performance, gender, ethnicity, 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 Report [Not required for Mini-projects]:

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

1. 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.

2. 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.

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

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 chosen optimization algorithm will proceed to solve this problem by performing two hand iterations on a reduced version of the problem.
Implement the proposed solution using MATLAB.

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

7. 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 CD:

Before the presentation and in order to complete evaluating the project, each team has to prepare a CD for the supervisor containing all materials related to the project (complete documentation report according to the course policy mentioned above + a well documented source code and executable code with UserGuide that shows how to install and use the developed software + all the software packages used during the project development if any).

Project Presentations:

The project team presents the developed project in 10 minutes plus 5 minutes for a question period. The classmates view the presentation, review the presented material, and ask questions. Each presentation is attended by the course instructor as chair, course TA, critiquers (classmates), and the project team. All project proposals must be submitted to the course instructor before the proposal presentation. The teams do not need to submit their presentation material for marking. However, students are encouraged to submit their electronic presentation materials for archival. During the presentation, one or two members can do all of the speaking, or three or four members can share the speaking equally. All team members must be on the stage. Absent members need to provide documentation excusing their participation, e.g., a doctor's note. The course instructors will provide the critiquers with hardcopies of the evaluation sheet. The critiquers mark these sheets up and hand the completed sheets to the presenting team at the end of the presentation. The critiquers should provide clear, relevant and professional comments. The critquers comments do not need to agree with the instructors' comments, but must be well justified. Marks are assigned solely by the course instructors based on the presentation. The instructors use the same evaluation sheet as the other reviewers. The classmates' critique questions and results do not affect the presentation marks directly, but may help the instructors to clarify their own rationale, especially in evaluating the team's responses to questions.