The implementation of a novel, bio-inspired, robotic security system

The implementation of a robotic security solution generally requires one algorithm to route the robot around the environment and another algorithm to perform anomaly detection. Solutions to the routing problem require the robot to have a good estimate of its own pose. We present a novel security system that uses metrics generated by the localisation algorithm to perform adaptive anomaly detection. The localisation algorithm is a vision-based SLAM solution called RatSLAM, based on mechanisms within the hippocampus. The anomaly detection algorithm is based on the mechanisms used by the immune system to identify threats to the body. The system is explored using data gathered within an unmodified office environment. It is shown that the algorithm successfully reacts to the presence of people and objects in areas where they are not usually present and is tolerised against the presence of people in environments that are usually dynamic.

Mission path planning of aerial survey tasks using hybrid game evolutionary algorithm

The work presented in this report is aimed to implement a cost-effective offline mission path planner for aerial inspection tasks of large linear infrastructures. Like most real-world optimisation problems, mission path planning involves a number of objectives which ideally should be minimised simultaneously. Understandably, the objectives of a practical optimisation problem are conflicting each other and the minimisation of one of them necessarily implies the impossibility to minimise the other ones. This leads to the need to find a set of optimal solutions for the problem; once such a set of available options is produced, the mission planning problem is reduced to a decision making problem for the mission specialists, who will choose the solution which best fit the requirements of the mission. The goal of this work is then to develop a Multi-Objective optimisation tool able to provide the mission specialists a set of optimal solutions for the inspection task amongst which the final trajectory will be chosen, given the environment data, the mission requirements and the definition of the objectives to minimise. All the possible optimal solutions of a Multi-Objective optimisation problem are said to form the Pareto-optimal front of the problem. For any of the Pareto-optimal solutions, it is impossible to improve one objective without worsening at least another one. Amongst a set of Pareto-optimal solutions, no solution is absolutely better than another and the final choice must be a trade-off of the objectives of the problem. Multi-Objective Evolutionary Algorithms (MOEAs) are recognised to be a convenient method for exploring the Pareto-optimal front of Multi-Objective optimization problems. Their efficiency is due to their parallelism architecture which allows to find several optimal solutions at each time

Design of logical topologies for wavelength-routed optical networks

his paper studies the problem of designing a logical topology over a wavelength-routed all-optical network (AON) physical topology, The physical topology consists of the nodes and fiber links in the network, On an AON physical topology, we can set up lightpaths between pairs of nodes, where a lightpath represents a direct optical connection without any intermediate electronics, The set of lightpaths along with the nodes constitutes the logical topology, For a given network physical topology and traffic pattern (relative traffic distribution among the source-destination pairs), our objective is to design the logical topology and the routing algorithm on that topology so as to minimize the network congestion while constraining the average delay seen by a source-destination pair and the amount of processing required at the nodes (degree of the logical topology), We will see that ignoring the delay constraints can result in fairly convoluted logical topologies with very long delays, On the other hand, in all our examples, imposing it results in a minimal increase in congestion, While the number of wavelengths required to imbed the resulting logical topology on the physical all optical topology is also a constraint in general, we find that in many cases of interest this number can be quite small, We formulate the combined logical topology design and routing problem described above (ignoring the constraint on the number of available wavelengths) as a mixed integer linear programming problem which we then solve for a number of cases of a six-node network, Since this programming problem is computationally intractable for larger networks, we split it into two subproblems: logical topology design, which is computationally hard and will probably require heuristic algorithms, and routing, which can be solved by a linear program, We then compare the performance of several heuristic topology design algorithms (that do take wavelength assignment constraints into account) against that of randomly generated topologies, as well as lower bounds derived in the paper.

基于多传感器融合的组合导航方法研究

本文提出一种基于多传感器融合的组合导航方法,能够在小型旋翼无人机上实现低成本、高精度导航定位.该方法通过建立导航系统的机械编排模型,设计了一个17状态的扩展卡尔曼滤波器(EKF).对加速计的零偏和陀螺仪的漂移进行在线估计,实时的补偿传感器的测量误差.从而对旋翼无人机的速度、位置、角速度和姿态等参数进行精确的估计.通过对实际飞行数据仿真实验,并对比参考的导航系统,证明该方法在飞机的全包线飞行下均能够解算出可靠的导航信息。

Sectorization: measures and an electromagnetism based approach

Sectorization means dividing a set of basic units into sectors or parts, a procedure that occurs in several contexts, such as political, health and school districting, social networks and sales territory or airspace assignment, to achieve some goal or to facilitate an activity. This presentation will focus on three main issues: Measures, a new approach to sectorization problems and an application in waste collection. When designing or comparing sectors different characteristics are usually taken into account. Some are commonly used, and they are related to the concepts of contiguity, equilibrium and compactness. These fundamental characteristics will be addressed, by defining new generic measures and by proposing a new measure, desirability, connected with the idea of preference. A new approach to sectorization inspired in Coulomb’s Law, which establishes a relation of force between electrically charged points, will be proposed. A charged point represents a small region with specific characteristics/values creating relations of attraction/repulsion with the others (two by two), proportional to the charges and inversely proportional to their distance. Finally, a real case about sectorization and vehicle routing in solid waste collection will be mentioned.

Properties and Algorithms of the KCube Interconnection Networks

The KCube interconnection network was first introduced in 2010 in order to exploit the good characteristics of two well-known interconnection networks, the hypercube and the Kautz graph. KCube links up multiple processors in a communication network with high density for a fixed degree. Since the KCube network is newly proposed, much study is required to demonstrate its potential properties and algorithms that can be designed to solve parallel computation problems. In this thesis we introduce a new methodology to construct the KCube graph. Also, with regard to this new approach, we will prove its Hamiltonicity in the general KC(m; k). Moreover, we will find its connectivity followed by an optimal broadcasting scheme in which a source node containing a message is to communicate it with all other processors. In addition to KCube networks, we have studied a version of the routing problem in the traditional hypercube, investigating this problem: whether there exists a shortest path in a Qn between two nodes 0n and 1n, when the network is experiencing failed components. We first conditionally discuss this problem when there is a constraint on the number of faulty nodes, and subsequently introduce an algorithm to tackle the problem without restrictions on the number of nodes.

Étude d'un problème de tournées de véhicules sur les arcs avec contraintes de capacité et coûts de service dépendants du temps

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal

Optimal Path Searching through Specified Routes using different Algorithms

To connect different electrical, network and data devices with the minimum cost and shortest path, is a complex job. In huge buildings, where the devices are placed at different locations on different floors and only some specific routes are available to pass the cables and buses, the shortest path search becomes more complex. The aim of this thesis project is, to develop an application which indentifies the best path to connect all objects or devices by following the specific routes.To address the above issue we adopted three algorithms Greedy Algorithm, Simulated Annealing and Exhaustive search and analyzed their results. The given problem is similar to Travelling Salesman Problem. Exhaustive search is a best algorithm to solve this problem as it checks each and every possibility and give the accurate result but it is an impractical solution because of huge time consumption. If no. of objects increased from 12 it takes hours to search the shortest path. Simulated annealing is emerged with some promising results with lower time cost. As of probabilistic nature, Simulated annealing could be non optimal but it gives a near optimal solution in a reasonable duration. Greedy algorithm is not a good choice for this problem. So, simulated annealing is proved best algorithm for this problem. The project has been implemented in C-language which takes input and store output in an Excel Workbook

Production and Delivery (Optimization of production system and reliability)

This thesis is done to solve two issues for Sayid Paper Mill Ltd Pakistan. Section one deals with a practical problem arise in SPM that is cutting a given set of raw paper rolls of known length and width, and a set of product paper rolls of known length (equal to the length of raw paper rolls) and width, practical cutting constraints on a single cutting machine, according to demand orders for all customers. To solve this problem requires to determine an optimal cutting schedule to maximize the overall cutting process profitability while satisfying all demands and cutting constraints. The aim of this part of thesis is to develop a mathematical model which solves this problem.Second section deals with a problem of delivering final product from warehouse to different destinations by finding shortest paths. It is an operational routing problem to decide the daily routes for sending trucks to different destination to deliver their final product. This industrial problem is difficult and includes aspect such as delivery to a single destination and multiple destinations with limited resources. The aim of this part of thesis is to develop a process which helps finding shortest path.

Optimization of cable cycles : a trade-off between reliability and cost

This paper elaborates the routing of cable cycle through available routes in a building in order to link a set of devices, in a most reasonable way. Despite of the similarities to other NP-hard routing problems, the only goal is not only to minimize the cost (length of the cycle) but also to increase the reliability of the path (in case of a cable cut) which is assessed by a risk factor. Since there is often a trade-off between the risk and length factors, a criterion for ranking candidates and deciding the most reasonable solution is defined. A set of techniques is proposed to perform an efficient and exact search among candidates. A novel graph is introduced to reduce the search-space, and navigate the search toward feasible and desirable solutions. Moreover, admissible heuristic length estimation helps to early detection of partial cycles which lead to unreasonable solutions. The results show that the method provides solutions which are both technically and financially reasonable. Furthermore, it is proved that the proposed techniques are very efficient in reducing the computational time of the search to a reasonable amount.

Análise do uso de SIG no roteamento dos veículos de coleta de resíduos sólidos domiciliares

Relata-se neste trabalho, a análise do uso de um Sistema de Informação Geográfica - SIG como ferramenta para roteirização de veículos de coleta de resíduos sólidos domiciliares. O software utilizado foi o TransCAD, versão 3.2, que permite desenvolver rotas utilizando algoritmos que incluem o procedimento de roteirização em arco. O objetivo é minimizar a extensão total a ser percorrida pelos veículos coletores. O estudo de caso foi realizado na cidade de Ilha Solteira - SP. Os dados coletados e os resultados obtidos pelo TransCAD foram processados no software Microsoft Excel. Os resultados obtidos demonstraram reduções percentuais de até 41% na distância total percorrida e de 68% no tempo total de percurso em relação ao serviço atual.

Uma colônia de formigas para o caminho mais curto multiobjetivo

Multi-objective combinatorial optimization problems have peculiar characteristics that require optimization methods to adapt for this context. Since many of these problems are NP-Hard, the use of metaheuristics has grown over the last years. Particularly, many different approaches using Ant Colony Optimization (ACO) have been proposed. In this work, an ACO is proposed for the Multi-objective Shortest Path Problem, and is compared to two other optimizers found in the literature. A set of 18 instances from two distinct types of graphs are used, as well as a specific multiobjective performance assessment methodology. Initial experiments showed that the proposed algorithm is able to generate better approximation sets than the other optimizers for all instances. In the second part of this work, an experimental analysis is conducted, using several different multiobjective ACO proposals recently published and the same instances used in the first part. Results show each type of instance benefits a particular type of instance benefits a particular algorithmic approach. A new metaphor for the development of multiobjective ACOs is, then, proposed. Usually, ants share the same characteristics and only few works address multi-species approaches. This works proposes an approach where multi-species ants compete for food resources. Each specie has its own search strategy and different species do not access pheromone information of each other. As in nature, the successful ant populations are allowed to grow, whereas unsuccessful ones shrink. The approach introduced here shows to be able to inherit the behavior of strategies that are successful for different types of problems. Results of computational experiments are reported and show that the proposed approach is able to produce significantly better approximation sets than other methods

Optimal trajectory and solution of the inverse kinematics of a robotic manipulator by genetic algorithms

This paper presents the generation of optimal trajectories by genetic algorithms (GA) for a planar robotic manipulator. The implemented GA considers a multi-objective function that minimizes the end-effector positioning error together with the joints angular displacement and it solves the inverse kinematics problem for the trajectory. Computer simulations results are presented to illustrate this implementation and show the efficiency of the used methodology producing soft trajectories with low computing cost. © 2011 Springer-Verlag Berlin Heidelberg.

Otimização de cobertura, consumo de energia, roteamento e agregação de dados em rede de sensores sem fio utilizando algoritmos genéticos e lógica fuzzy

As Redes de Sensores Sem Fio possuem capacidades limitadas de processamento, armazenamento, comunicação (largura de banda) e fonte de energia, além de possuírem características e requisitos básicos de uma RSSF como: necessidade de se auto-organizar, comunicação com difusão de curto alcance e roteamento com múltiplos saltos. Neste trabalho é proposto uma ferramenta que otimize o posicionamento e os pacotes entregues através do uso de Algoritmo Genético (AG). Para solucionar o problema de roteamento que melhore o consumo de energia e maximize a agregação de dados é proposto a utilização de lógica fuzzy no protocolo de roteamento Ad hoc Ondemand Distance Vector (AODV). Esta customização é intitulada AODV – Fuzzy for Wireless Sensor Networks (AODV-FWSN). Os resultados mostram que a solução proposta é eficiente e consegue prolongar a vida útil da RSSF e melhorar a taxa de entrega de dados quando comparado com soluções similares.

A Study of Different Subsequence Elimination Strategies for the Soft Drink Production Planning

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)