Metaheuristic Optimization and their Applications in Robotics and Automation

The course grade will be calculated as follows:

Evaluation Method			Weight
Attendance			40%
In-class Participation			30%
Project			30%
Total			100%

The following is the definite list of projects. Registration is on a first come, first served basis. Please send me your choice before Monday Feb. 6, 2012.

List of Case Studies:
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 samrt carts by using an ACO-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	Cell Assignment in PCS Networks (CA) Problem: The cell assignment problem is a challenging problem in PCS (Personal Communication Services) networks. In PCS networks, each cell has an antenna that is used to communicate with subscribers over some pre-assigned radio frequencies. Groups of cells are connected to a switch, through which the cells are then routed to the satellite networks.
13	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.
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.
15	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.
16	Research Problem: Identify a problem related to your current research 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 optimization techniques studied in this course.

Project Report:

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 propsoed 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. Students must 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).

Porject Presentations:

The project team presents the developed project on Friday February 10, 2011 in 10 minutes plus 5 minutes for a question period. The classmates view the presentation, review the presented material, and ask questions. Marks are assigned solely by the course instructors based on the presentation. 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.