| 1. |
- Anisi, David A., 1977-, et al.
(författare)
-
Algorithms for the connectivity constrained unmanned ground vehicle surveillance problem
- 2009
-
Ingår i: European Control Conference (ECC). - Budapest, Hungary : EUCA.
-
Konferensbidrag (refereegranskat)abstract
- The Connectivity Constrained UGV Surveillance Problem (CUSP) considered in this paper is the following. Given a set of surveillance UGVs and a user defined area to be covered, find waypoint-paths such that; 1) the area is completely surveyed, 2) the time for performing the search is minimized and 3) the induced information graph is kept recurrently connected. It has previously been shown that the CUSP is NP-hard. This paper presents four different heuristic algorithms for solving the CUSP, namely, the Token Station Algorithm, the Stacking Algorithm, the Visibility Graph Algorithm and the Connectivity Primitive Algorithm. These algorithms are then compared by means of Monte Carlo simulations. The conclusions drawn are that the Token Station Algorithm provides the most optimal solutions, the Stacking Algorithm has the lowest computational complexity, while the Connectivity Primitive Algorithm provides the best trade-off between optimality and computational complexity for larger problem instances.
|
|
| 2. |
- Anisi, David A., 1977-, et al.
(författare)
-
Communication constrained multi-UGV surveillance
- 2008
-
Ingår i: IFAC World Congress. - Seoul, Korea.
-
Konferensbidrag (refereegranskat)abstract
- This paper addresses the problem of connectivity constrained surveillance of a given polyhedral area with obstacles using a group of Unmanned Ground Vehicles (UGVs). The considered communication restrictions may involve both line-of-sight constraints and limited sensor range constraints. In this paper, the focus is on dynamic information graphs, G, which are required to be kept recurrently connected. The main motivation for introducing this weaker notion of connectivity is security and surveillance applications where the sentry vehicles may have to split temporary in order to complete the given mission efficiently but are required to establish contact recurrently in order to exchange information or to make sure that all units are intact and well-functioning. From a theoretical standpoint, recurrent connectivity is shown to be sufficient for exponential convergence of consensus filters for the collected sensor data.
|
|
| 3. |
- Anisi, David A., et al.
(författare)
-
Cooperative Surveillance Missions with Multiple Unmanned Ground Vehicles (UGVs)
- 2008
-
Ingår i: 47TH IEEE CONFERENCE ON DECISION AND CONTROL, 2008 (CDC 2008). - 9781424431243 ; , s. 2444-2449
-
Konferensbidrag (refereegranskat)abstract
- This paper proposes an optimization based approach to multi-UGV surveillance. In particular, we formulate both the minimum time- and connectivity constrained surveillance problems, show NP-hardness of them and propose decomposition techniques that allow us to solve them efficiently in an algorithmic manner. The minimum time formulation is the following. Given a set of surveillance UGVs and a polyhedral area, find waypoint-paths for all UGVs such that every point of the area is visible from a point on a path and such that the time for executing the search in parallel is minimized. Here, the sensor's field of view are assumed to be occluded by the obstacles and limited by a maximal sensor range. The connectivity constrained formulation extends the first by additionally requiring that the information graph induced by the sensors is connected at the time instants when the UGVs stop to perform the surveillance task. The second formulation is relevant to situation when mutual visibility is needed either to transmit the sensor data being gathered, or to protect the team from hostile persons trying to approach the stationary UGVs.
|
|
| 4. |
- Anisi, David A., 1977-, et al.
(författare)
-
Minimum time multi-UGV surveillance
- 2008
-
Ingår i: OPTIMIZATION AND COOPERATIVE CONTROL STRATEGIES. - Berlin : Springer Verlag. - 9783540880622 ; , s. 31-45
-
Konferensbidrag (refereegranskat)abstract
- This paper addresses the problem of concurrent task- and path planning for a number of surveillance Unmanned Ground Vehicles (UGVs) such that a user defined area of interest is covered by the UGVs' sensors in minimum time. We first formulate the problem, and show that it is in fact a generalization of the Multiple Traveling Salesmen Problem (MTSP), which is known to be NP-hard. We then propose a solution that decomposes the problem into three subproblems. The first is to find a maximal convex covering of the search area. Most results on static coverage use disjoint partitions of the search area, e.g. triangulation, to convert the continuous sensor positioning problem into a discrete one. However, by a simple example, we show that a highly overlapping set of maximal convex sets is better suited for minimum time coverage. The second subproblem is a combinatorial assignment and ordering of the sets in the cover. Since Tabu search algorithms are known to perform well on various routing problems, we use it as a part of our proposed solution. Finally, the third subproblem utilizes a particular shortest path sub-routine in order to find the vehicle paths, and calculate the overall objective function used in the Tabu search. The proposed algorithm is illustrated by a number of simulation examples.
|
|
| 5. |
- Anisi, David A., et al.
(författare)
-
Safe receding horizon control of an aerial vehicle
- 2006
-
Ingår i: PROCEEDINGS OF THE 45TH IEEE CONFERENCE ON DECISION AND CONTROL, VOLS 1-14. - : IEEE. - 9781424401703 ; , s. 57-62
-
Konferensbidrag (refereegranskat)abstract
- This paper addresses the problem of designing a real time high performance controller and trajectory generator for air vehicles. The control objective is to use information about terrain and enemy threats to fly low and avoid radar exposure on the way to a given target. The proposed algorithm builds on the well known approach of Receding Horizon Control (RHC) combined with a terminal cost, calculated from a graph representation of the environment. Using a novel safety maneuver, and under an assumption on the maximal terrain inclination, we are able to prove safety as well as task completion. The safety maneuver is incorporated in the short term optimization, which is performed using Nonlinear Programming (NLP). Some key characteristics of the trajectory planner are highlighted through simulations.
|
|
| 6. |
- Anisi, David, et al.
(författare)
-
On-line Trajectory planning for aerial vehicles : a safe approach with guaranteed task completion
- 2006
-
Ingår i: Collection of Technical Papers. - Reston, Virigina : American Institute of Aeronautics and Astronautics. - 9781563478192 - 1563478196 ; , s. 914-938
-
Konferensbidrag (refereegranskat)abstract
- On-line trajectory optimization in three dimensional space is the main topic of the paper at hand. The high-level framework augments on-line receding horizon control with an off-line computed terminal cost that captures the global characteristics of the environment, as well as any possible mission objectives. The first part of the paper is devoted to the single vehicle case while the second part considers the problem of simultaneous arrival of multiple aerial vehicles. The main contribution of the first part is two-fold. Firstly, by augmenting a so called safety maneuver at the end of the planned trajectory, this paper extends previous results by addressing provable safety properties in a 3 D setting. Secondly, assuming initial feasibility, the planning method presented is shown to have finite time task completion. Moreover, a quantitative comparison between the two competing objectives of optimality and computational tractability is made. Finally, some other key characteristics of the trajectory planner, such as ability to minimize threat exposure and robustness, are highlighted through simulations. As for the simultaneous arrival problem considered in the second part, by using a time-scale separation principle, we are able to adopt standard Laplacian control to a consensus problem which is neither unconstrained, nor first order.
|
|
| 7. |
- Gattami, Ather, et al.
(författare)
-
Stabilization of Vehicle Formations-A Case Study
- 2005
-
Ingår i: Book of Abstracts of Third Swedish Workshop on Autonomous Robotics. - 1650-1942.
-
Konferensbidrag (övrigt vetenskapligt/konstnärligt)abstract
- This work treats a specific multi-vehicle control case, namely six vehicles on the Multi-Vehicle Wireless Testbed (MTWT), wich is an arena at Caltech, California, built for doing experiments on small vehicles. A model is set up and a controller is found through simulations that stabilizes the system. Stability is proven through a Nyquist-like criterion.
|
|
| 8. |
- Lindhé, Magnus, et al.
(författare)
-
Flocking with obstacle avoidance : A new distributed coordination algorithm based on Voronoi partitions
- 2005
-
Ingår i: 2005 IEEE International Conference on Robotics and Automation (ICRA), Vols 1-4. - : IEEE. ; , s. 1785-1790
-
Konferensbidrag (refereegranskat)abstract
- A new distributed coordination algorithm for multi-vehicle systems is presented in this paper. The algorithm combines a particular choice of navigation function with Voronoi partitions. This results not only in obstacle avoidance and motion to the goal, but also in a desirable geographical distribution of the vehicles. Our algorithm is decentralized in that each vehicle needs only to know the position of neighboring vehicles, but no other inter-vehicle communication or centralized control are required. The algorithm gives a natural priority to safety, goal convergence, and formation keeping, in that (1) collision avoidance is guaranteed under all circumstances, (2) the vehicles will move toward the goal as long as a given optimization problem is feasible, and (3) if prior criteria admit, the vehicles tend to a desirable lattice formation. These theoretical properties are discussed in the paper and the performance of the algorithm is illustrated in simulations with realistic models of twenty all-terrain vehicles. Planned experimental evaluation using customized miniature cars is also briefly described.
|
|
| 9. |
- Nilsson, Ulrik, et al.
(författare)
-
Optimal positioning of surveillance UGVs
- 2008
-
Ingår i: 2008 IEEE/RSJ INTERNATIONAL CONFERENCE ON ROBOTS AND INTELLIGENT SYSTEMS, VOLS 1-3, CONFERENCE PROCEEDINGS. - New York : IEEE. - 9781424420575 ; , s. 2539-2544
-
Konferensbidrag (refereegranskat)abstract
- Unmanned ground vehicles (UGVs) equipped with surveillance cameras present a flexible complement to the numerous stationary sensors being used in security applications today. However, to take full advantage of the flexibility and speed offered by a group of UGV platforms, a fast way to compute desired camera locations that cover or surround a set of buildings e.g., in response to an alarm, is needed. In this paper we focus on two problems. The first is how to create a line-of-sight perimeter around a given set of buildings with a minimal number of UGVs. The second problem is how to find UGV positions such that a given set of walls are covered by the cameras while taking constraints in terms of zoom, range, resolution and field of view into account. For the first problem we propose a polynomial time algorithm and for the second problem we extend our previous work to include zoom cameras and furthermore provide a theoretical analysis of the approach itself. A number of examples are presented to illustrate the two algorithms.
|
|
| 10. |
- Nilsson, Ulrik, et al.
(författare)
-
Towards Optimal Positioning of Surveillance UGVs
- 2009
-
Konferensbidrag (refereegranskat)abstract
- Unmanned Ground Vehicles (UGVs) equipped with surveillance cameras present a flexible complement to the numerous stationary sensors being used in security applications today. However, to take full advantage of the flexibility and speed offered by a group of UGV platforms, a fast way to compute desired camera locations to cover ail area or a set of buildings, e.g., in response to ail alarm, is needed. Building upon earlier results in terrain guarding and sensor placement we propose a way to find candidate guard positions that; satisfy a large set. of view angle and range constraints simulataneously. Since the original problem is NP-complete, we do riot seek to find the true optimal set of guard positions. Instead, a near optimal subset of the candidate points is chosen using a scheme with a known approximation ratio of O(log(n)). A number of examples are presented to illustrate the approach.
|
|
| 11. |
- Thunberg, Johan, et al.
(författare)
-
A comparative study of task assignment and path planning methods for multi-UGV missions
- 2009
-
Ingår i: OPTIMIZATION AND COOPERATIVE CONTROL STRATEGIES. - Berlin, Heidelberg : Springer Berlin Heidelberg. - 9783540880622 ; , s. 167-180
-
Konferensbidrag (refereegranskat)abstract
- Many important problems involving a group of unmanned ground vehicles (UGVs) are closely related to the multi traviling salesman problem (m-TSP). This paper comprises a comparative study of a number of algorithms proposed in the litterature to solve m-TSPs occuring in robotics. The investigated algoritms include two mixed integer linear programming (MILP) formulations, a market based approach (MA), a Voronoi partition step (VP) combined with the local search used in MA, and a deterministic and a stocastic version of the granular tabu search (GTS). To evaluate the algoritms, an m-TSP is derived from a planar environment with polygonal obstacles and uniformly distributed targets and vehicle positions. The results of the comparison indicate that out of the decentralized approaches, the MA yield good solutions but requires long computation times, while VP is fast but not as good. The two MILP approaches suffer from long computation times, and poor results due to the decomposition of the assignment and path planning steps. Finally, the two GTS algorithms yield good results in short times with inputs from MA as well as the much faster VP. Thus the best performing centralized approach is the GTS in combination with the VP. Funded by the Swedish defence materiel administration (FMV) and the Swedish armed forces through the Technologies for Autonomous and Intelligent Systems (TAIS) project. 297316-LB704859
|
|
| 12. |
- Ögren, Petter, et al.
(författare)
-
A Convergent Dynamic Window Approach to Obstacle Avoidance
- 2005
-
Ingår i: IEEE Transactions on robotics. - 1552-3098 .- 1941-0468. ; 21:2, s. 188-195
-
Tidskriftsartikel (refereegranskat)abstract
- The dynamic window approach (DWA) is a well-known navigation scheme developed by Fox et al. and extended by Brock and Khatib. It is safe by construction, and has been shown to perform very efficiently in experimental setups. However, one can construct examples where the proposed scheme fails to attain the goal configuration. What has been lacking is a theoretical treatment of the algorithm's convergence properties. Here we present such a treatment by merging the ideas of the DWA with the convergent, but less performance-oriented, scheme suggested by Rimon and Koditschek. Viewing the DWA as a model predictive control (MPC) method and using the control Lyapunov function (CLF) framework of Rimon and Koditschek, we draw inspiration from an MPC/CLF framework put forth by Primbs to propose a version of the DWA that is tractable and convergent.
|
|
| 13. |
- Ögren, Petter, et al.
(författare)
-
A New Control Mode for Teleoperated Differential Drive UGVs
- 2007
-
Ingår i: PROCEEDINGS OF THE 46TH IEEE CONFERENCE ON DECISION AND CONTROL, VOLS 1-14. - 9781424414970 ; , s. 446-471
-
Konferensbidrag (refereegranskat)abstract
- This paper proposes a control mode that enables the users of teleoperated non-holonomic differential drive unmanned ground vehicles (UGVs) to interact with the unmanned vehicles in a new way. By introducing an intermediate control layer, a user interface that is very similar to so-called first person shooter (FPS) computer games, e.g. Doom and Half Life, can be created. The advantages of such interfaces is that they are intuitive, and that literally millions of potential future UGV-operators already have spent hundreds of hours training with them. The control mode gives the user direct control of the position and orientation of the on-board camera, while the actual orientation of the vehicle is abstracted away using feedback linearization. Thus, the idea is similar to using inverse kinematics to directly control the position and orientation of a robot arm gripper. The paper first describes the predominant direct vehicle control model, as well as the FPS interfaces. It is then shown how the proper choice of intermediate control layer can make the two equivalent
|
|
| 14. |
- Ögren, Petter, et al.
(författare)
-
Autonomous UCAV Strike Missions using Behavior Control Lyapunov Functions
- 2006
-
Konferensbidrag (refereegranskat)abstract
- An autonomous Unmanned Combat Aerial Vehicle (UCAV) carrying out a surveillance or strike mission must be able to handle situations where the different mission objectives are in conflict and a tradeoff must be made, e.g. when the time of arrival is in conflict with the prescribed safety distance to an enemy surface to air missile (SAM) site. This paper describes a framework called Behavior Control Lyapunov Functions (BCLF), to handle such tradeoffs. The framework combines the natural idea of different control behaviors for different mission objectives, suggested in the Behavior Based robotics approach, with the mathematical transparency of Control Lyapunov Functions (CLF) from control theory. First, each behavior is represented by a scalar function with certain CLF-like properties, describing to what extent that mission objective is satisfied. The operator then edits a priority table reflecting the order of importance between different objectives, as well as different levels of satisfaction. Based on the table and the current levels of satisfaction the algorithm decides which objectives should be focused on right now, and which should currently be ignored. Finally, the current high priority objectives are transformed into recommended subsets of the available control choices, and passed to the controller. The paper is concluded with simulation examples illustrating the approach.
|
|
| 15. |
|
|
| 16. |
- Ögren, Petter, et al.
(författare)
-
Formulation and Solution of the UAV Paparazzi Problem
- 2006
-
Konferensbidrag (refereegranskat)abstract
- Many UAV path planning problems dealing with multiple targets are formulated as instances of classical optimization problems such as the Traveling Salesperson Problem (TSP), Vehicle Routing Problem (VRP), and the Assignment Problem (AP). In their basic forms, all these problems minimize the length of the flight path to be flown by the UAVs. Even though this is often a reasonable choice, we argue that in instances when the targets are able to hide, or move, an objective function accounting for the target value, as well as the chance of actually finding the target is more natural. In some sense, the problem is similar to the one faced by a Paparazzi photographer, deciding where to go to get snapshots of non cooperative celebrities. Hence we formulate the so-called Paparazzi utility function, and show how it can be applied to UAV path planning problems similar to the TSP, VRP and AP
|
|
| 17. |
- Ögren, Petter
(författare)
-
Improved predictability of reactive robot control using Control Lyapunov Functions
- 2008
-
Ingår i: 2008 IEEE/RSJ INTERNATIONAL CONFERENCE ON ROBOTS AND INTELLIGENT SYSTEMS, VOLS 1-3, CONFERENCE PROCEEDINGS. - 9781424420575 ; , s. 1274-1279
-
Konferensbidrag (refereegranskat)abstract
- Model based robot control approaches are often designed to allow the verification of certain system properties such as safety or goal convergence. However, designing such controllers is often very time consuming, and most of the time it is not possible to add additional control objectives without jeopardizing the previously proved system properties.
|
|
| 18. |
|
|
