text:
Conference Paper

# Multiple UAV coalition formation

Authors:
To read the full-text of this research, you can request a copy directly from the authors.

## Abstract

Unmanned aerial vehicles (UAVs) have the potential to carry munitions in support of battlefield operations, however they have limited sensor range and can carry only small quantities of resources. Often, to fully prosecute a target, a variety of assets may be required, and it may be necessary to deliver these assets simultaneously. Therefore, a team of UAVs that satisfies the target resource requirement needs to be assigned to a single target, and this team is called a coalition. Other desired requirements for the coalition are (i) minimize the target prosecution delay and (ii) minimize the size of the coalition. In this paper, we propose a two-stage optimal coalition formation algorithm that assigns appropriate numbers of UAVs satisfying the desired requirements. We developed a Dubins curves based simultaneous strike scheme. Simulation results are presented to show that the two-stage coalition formation algorithm has low computational overhead and can be applied in real-time.

## No full-text available

... One aspect of the task allocation problem is what is known as the coalition formation problem: How do we form teams of agents, with each team assigned to a particular task, in order to best complete the set of tasks at hand? While the coalition formation problem in multi-agent systems has received much atten- tion [4,12,14,16], only a small fraction of that work has focused on multi-robot domains [2,5,15,17,20]. The multi-agent algorithms and techniques are not directly transferable to multi-robot domains, as multi-robot domains present challenges and constraints not encountered with software agents [19]. ...
... Abdallah and Lesser [1] demonstrate that the multi-dimensional knapsack problem is reducible to the coalition formation problem. While significant research exists for multi-agent coalition formation [4,12,14,16], only a small fraction of research has focused on multi-robot domains [2,5,15,17,20]. Vig and Adams [19,20] demonstrate some of the differences between general multi-agent and multirobot domains and highlight the fact that the general multi-agent algorithms and techniques are not directly transferable to multi-robot domains, as multi-robot domains present challenges and constraints not encountered with software agents. Vig and Adams [20] introduce the service oriented model employed in this paper and present a market based approach, RACHNA that attempts to address some of the issues with coalition formation in multi-robot domains. ...
Article
This paper focuses on coalition formation for task allocation in both multi-agent and multi-robot domains. Two different problem formalizations are considered, one for multi-agent domains where agent resources are transferable and one for multi-robot domains. We demonstrate complexity theoretic differences between both models and show that, under both, the coalition formation problem, with m tasks, is NP-hard to both solve exactly and to approximate within a factor of $${O(m^{1-\epsilon})}$$ for all $${\epsilon > 0}$$. Two natural restrictions of the coalition formation problem are considered. In the first situation agents are drawn from a set of j types. Agents of each type are indistinguishable from one another. For this situation a dynamic programming based approach is presented, which, for fixed j finds the optimal coalition structure in polynomial time and is applicable in both multi-agent and multi-robot domains. We then consider situations where coalitions are restricted to k or fewer agents. We present two different algorithms. Each guarantees the generated solution to be within a constant factor, for fixed k, of the optimal in terms of utility. Our algorithms complement Shehory and Kraus’ algorithm (Artif Intell 101(1–2):165–200, 1998), which provides guarantee’s on solution cost, as ours provides guarantees on utility. Our algorithm for general multi-agent domains is a modification of and has the same running time as Shehory and Kraus’ algorithm, while our approach for multi-robot domains runs in time $${O(n^{\frac{3}{2}}m)}$$, much faster than Vig and Adams (J Intell Robot Syst 50(1):85–118, 2007) modifications to Shehory and Kraus’ algorithm for multi-robot domains, which ran in time O(n k m), for n agents and m tasks.
... In this section, an algorithm for MPC formation flight of two quadrotor is presented. Formation Control has been addressed in [11][12][13][14][15][16][17][18][19][20]. However, in the near future it will be possible to develop control techniques using formation control not only for UAVs but also for UGVs. ...
Article
Full-text available
Unmanned Aerial Vehicles (UAVs) are gaining increasing interest thanks to their flexibility and versatility. However, these systems are very complex and a good simulation platform is needed. In this paper, a new Framework for simulation and fast prototyping of UAV control laws is presented. The Framework exploits the high realism of the simulations carried out in a three-dimensional virtual environment with the easiness of use of development systems such as Matlab® for fast prototyping of control systems. Then a novel method that exploits the benefits of Model Predictive Control (MPC) for cooperative scenarios is introduced. The obtained results show good performances of MPC in solving the formation problem of unmanned aerial vehicles; finding an optimal solution and taking into account different constraints. The developed framework allows also to easily change from simulated agent to real one.
... Experimental demonstrations of the distributed auction-based approach for the box pushing problem [18,44], cooperative load transportation [27], and disaster management [24] were respectively presented. The coalition formation for the simultaneous attack problem was treated using a centralized [42] and distributed scheme [25,41]. The centralized scheme solved the combinatorial optimization problem for the coalition formation using the particle swarm optimization (PSO) technique, and the distributed scheme utilized an auction and an integer programming. ...
Article
Full-text available
New market-based decentralized algorithms are proposed for the task assignment of multiple unmanned aerial vehicles in dynamic environments with a limited communication range. In particular, a cooperative timing mission that cannot be performed by a single vehicle is considered. The baseline algorithms for a connected network are extended to deal with time-varying network topology including isolated subnetworks due to a limited communication range. The mathematical convergence and scalability analyses show that the proposed algorithms have a polynomial time complexity, and numerical simulation results support the scalability of the proposed algorithm in terms of the runtime and communication burden. The performance of the proposed algorithms is demonstrated via Monte Carlo simulations for the scenario of the suppression of enemy air defenses.
... The goal of flock formation, which is directly related to the research area of coalition formation [38][39][40][41], is to form groups of heterogeneous entities with shared or individual goals. Several studies on coalition formation have considered mobile entities, such as UAVs, vehicles, and/or mobile robots [42][43][44][45]. Most of the studies on coalition formation focus on task sharing and resource allocation challenges in the coalition. ...
Article
Full-text available
In recent years, unmanned aerial vehicles (UAVs) have been used in a wide range of domains. As the number of UAV flights increases, central flight areas may become overcrowded. This may cause delays in UAV traffic or gridlock on UAV routes. To address this challenge, we propose a flocking protocol that enables individual UAVs to optimize their flight preferences, while receiving the benefits of traveling in a group. Flocking can reduce overcrowding , and as a result, UAVs will be able to travel on less congested routes and have fewer encounters with other UAVs, thus reducing flight time and conserving energy. The protocol allows each UAV to create a flock or join an existing flock for all or part of its journey. We perform a simulation of UAV flights in an urban area and compare the average flight time of the UAVs based on various flight situations (e.g., different routes and participation in groups of UAVs). The simulation results demonstrate that the use of the flocking protocol significantly reduced the average flight time, and the flight saving rate increased with an increase in the UAV mean number. A similar effect is also observed in situations where each UAV and flock formed a dynamic A* based path in advance to avoid collisions.
... In another attempt, the Fast Marching Square (FM2) algorithm [14]- [17] has been verified for obtaining excellent results on mobile vehicles, but kinematic constraints have not been considered to validate the feasibility of the trajectories. The Dubins path was introduced as a suitable method to solve this problem in 2D [18], [19] and 3D [20] environments. However, the resulting paths are not optimized. ...
Preprint
Full-text available
This paper presents a novel and feasible path planning technique for a group of unmanned aerial vehicles (UAVs) conducting surface inspection of infrastructure. The ultimate goal is to minimise the travel distance of UAVs while simultaneously avoid obstacles, and maintain altitude constraints as well as the shape of the UAV formation. A multiple-objective optimisation algorithm, called the Angle-encoded Particle Swarm Optimization (theta-PSO) algorithm, is proposed to accelerate the swarm convergence with angular velocity and position being used for the location of particles. The whole formation is modelled as a virtual rigid body and controlled to maintain a desired geometric shape among the paths created while the centroid of the group follows a pre-determined trajectory. Based on the testbed of 3DR Solo drones equipped with a proprietary Mission Planner, and the Internet-of-Things (IoT) for multi-directional transmission and reception of data between the UAVs, extensive experiments have been conducted for triangular formation maintenance along a monorail bridge. The results obtained confirm the feasibility and effectiveness of the proposed approach.
... In another attempt, the Fast Marching Square (FM2) algorithm [14]- [17] has been verified for obtaining excellent results on mobile vehicles, but kinematic constraints have not been considered to validate the feasibility of the trajectories. The Dubins path was introduced as a suitable method to solve this problem in 2D [18], [19] and 3D [20] environments. However, the resulting paths are not optimized. ...
Conference Paper
Full-text available
This paper presents a novel and feasible path planning technique for a group of unmanned aerial vehicles (UAVs) conducting surface inspection of infrastructure. The ultimate goal is to minimise the travel distance of UAVs while simultaneously avoid obstacles, and maintain altitude constraints as well as the shape of the UAV formation. A multiple-objective optimisation algorithm, called the Angle-encoded Particle Swarm Optimization (θ-PSO) algorithm, is proposed to accelerate the swarm convergence with angular velocity and position being used for the location of particles. The whole formation is modelled as a virtual rigid body and controlled to maintain a desired geometric shape among the paths created while the centroid of the group follows a predetermined trajectory. Based on the testbed of 3DR Solo drones equipped with a proprietary Mission Planner, and the Internet-of-Things (IoT) for multi-directional transmission and reception of data between the UAVs, extensive experiments have been conducted for triangular formation maintenance along a monorail bridge. The results obtained confirm the feasibility and effectiveness of the proposed approach.
... There are also some scholars who study the agent team formation problem in various application fields, such as RoboCup [33], rescue problem in fire field [27,34], unmanned aerial vehicles coalition formation strategies [35], agent team formation in social networks [36][37][38], business projects [39], engineering projects [40], and design problem [41]. In each specific field, there are some particular goal and constraints needing to be considered. ...
Article
Full-text available
With the development of aerospace science and technology, Earth Observation Satellite cluster which consists of heterogeneous satellites with many kinds of payloads appears gradually. Compared with the traditional satellite systems, satellite cluster has some particular characteristics, such as large-scale, heterogeneous satellite platforms, various payloads, and the capacity of performing all the observation tasks. How to select a subset from satellite cluster to perform all observation tasks effectively with low cost is a new challenge arousing in the field of aerospace resource scheduling. This is the agent team formation problem for observation task-oriented satellite cluster. A mathematical scheduling model is built. Three novel algorithms, i.e., complete search algorithm, heuristic search algorithm, and swarm intelligence optimization algorithm, are proposed to solve the problem in different scales. Finally, some experiments are conducted to validate the effectiveness and practicability of our algorithms.
... Once the coalition is determined using any of the strategies, the CL sends accept and reject decisions with ETAT at the target to the accepted PCM. The accept members assume the role of coalition members and have to prosecute the target simultaneously (which is one of the mission requirements) [7]. ...
Article
Full-text available
A team of networked UAVs are deployed in an unknown re-gion to search and destroy targets. To successfully destroy a target, a coalition of UAVs with sufficient cumulative re-sources needs to be assigned. Forming coalitions under net-works with dynamic topology is difficult and the type of coalition formation strategy adopted affects the mission per-formance. In this paper, we determine a mechanism to form coalitions in dynamically changing networks and investigate different coalition formation strategies.
... In this section, an algorithm for MPC formation flight of two quadrotor is presented. Formation Control has been addressed in [57], [58], [59], [60], [61], [62], [63], [64], [65], [66] . However, in the near future it will be possible to develop control techniques using formation control not only for UAVs but also for UGVs. ...
Thesis
Full-text available
... The approaches based on the minimization of a cost function can take into account different and conflicting constraints [6,7] that range from the fuel consumption minimization to the information availability about the displacement (in terms of positions) of other vehicles joining to the fleet. ...
Conference Paper
Full-text available
Today Unmanned Aerial Vehicles (UAVs) and in particular quad-rotors represent novel platforms to accomplish a wide set of missions as surveillance, Search & Rescue, inspection, pho-togrammetry. The main limitation of these vehicles is represented by the restricted operating area. The area is mainly limited by power supplies (batteries or fuel). A strategy to overcame this limitation is to increase the number of vehicles forming a coalition. The main benefit of coalition formation are the extended mission range and the capability to increase the sensorial set. Each vehicles is a part of a dynamic network that must be properly coordinated in order to optimize all the available resources. In this paper a new framework for simulation of unmanned vehicles in cooperative scenarios is first presented. The framework is based on the interaction of a physics-engine, which simulates the dynamics of vehicles and their interaction with world increasing the realism of simulation, and a simulation environment where the high-level strategy is designed/developed. A Model Predictive Control (MPC) is then introduced to solve the problem of leader-follower applied to quad-rotors. Using the developed framework and the MPC technique is possible to easily instantiate the coalition minimizing also a cost function. The obtained results from the control strategy point of view show that positioning error at steady state is equal to zero. The MPC allows also the modelling of different conflicting constraints as the control actions, positioning error, and fuel/energy consumption.
... Heimfarth et al. [7] have dealt with UAVs for Wireless Sensor Networks (WSNs) that are vulnerable to failures that may lead to the disconnection of parts of the network, creating partitions in the network, isolating the sensor nodes. This problem compromises the final results achieved by the WSN operation, as those isolated nodes are not able to deliver their messages to the sink nodes [8] . A way to overcome such problem is to provide an alternative connection to support the connectivity via other types of nodes that repair the connectivity among the sensor nodes. ...
Article
Full-text available
The major issue in airborne accidents is the retrieval of black box. An Unmanned Arial Vehicle (UAV) can be set inside the flight. The control of ejection is given to the pilot in the cockpit (manually). Flying Adhoc Network (FANET) is formed between the black box and the UAV. At the time of uncertain events like high jacking, engine failure etc., the pilot may trigger the UAV from its rear wing. The UAV should track the flight black box beacon signal, the UAV sends it to the Base Station (BS) via satellite. The upcoming idea is to setup UAV at the rear end of the aircraft (model airbus).The UAV is configured to send the response to the uncertain circumstances like highjack.
Conference Paper
Unmanned aerial vehicles (UAVs) have the capability of executing various missions. However, the capability of single UAV is limited. It may require multiple UAVs to form coalition and prosecute tasks cooperatively. So, multiple UAVs task assignment faces the problems of: (a) satisfy the heterogeneous resource requirement and (b) satisfy the task prosecution for real-time requirement. In this paper, a PSO based algorithm DCAA is proposed for UAVs task assignment. UAVs search for targets and try to form coalition when they find targets. Once formed, the coalition members will adjust their paths to prosecute the target simultaneously to induce maximum damage. The simulation results show that using the proposed algorithm, UAVs can complete mission in short time. And the mission completion percentage keeps at a high level. The proposed algorithm is suitable for real-time application.
Article
As one of the important components of computational flight mechanics and control, numerical algorithms of trajectory optimization for flight vehicles are currently studied by many researchers in aerospace engineering to completely solve these difficult problems, but few papers on the survey of this research field have been published recently. Based on the investigation of more than one hundred literatures, considering the application perspectives of computational flight mechanics and recent developments of trajectory optimization, the numerical algorithms of trajectory optimizations for aerospace vehicles are summarized and systematically analyzed. This paper summarized the basic principle, characteristics and application for all kinds of current trajectory optimization algorithms; and introduced some new methods and theories appearing in recent years. Finally, collaborative trajectory optimization for many flight vehicles, and hypersonic vehicle trajectory optimization were mainly reviewed in this paper. In the conclusion of this paper, the future research properties are presented regarding to numerical algorithms of trajectory optimization and control for flight vehicles as follows: collaboration and antagonization for many flight vehicles and multiple targets, global, real-time online, high accuracy of 7-D trajectory, considering all kinds of unknown random disturbances in trajectory optimization, and so on.
Article
New levels of challenge are required for real-time strategy games because of their limited learning curve. Usually this learning curve has an upper bound after which a player is able to win the most of the matches against the built-in artificial intelligence. In this research a method based on swarm intelligence is proposed to control a military swarm in the Star craft environment in order to achieve a better performance against the built-in artificial intelligence of the game. This method provides a way to form the units in such a way that they reach a suitable position to attack an enemy group conformed by elements of the same type. The results obtained in the experiments prove that is possible to implement this method and achieve a better performance than the greedy algorithm of the built-in AI. Finally, since the method is based in nature it is scalable, decentralized and robust as shown in the results.
Article
Ad-hoc aerial sensor networks leveraging MUAVs (Micro Unmanned Aerial Vehicles) are ideally suited to cost-efficiently explore unknown or hostile environments for example in case of incidents producing harmful gases or radiation. In this manuscript we present results on the investigations of communication-aware steering algorithms for cooperative MUAV swarms. The mission objective is to achieve a maximum spatial exploration efficiency with the simultaneous ability to self-optimize the communication links by exploiting controlled mobility. While our previous work has mainly considered the performance of the Air-to-Air mesh network, in this paper we focus on the Air-to-Ground-link connectivity control. To achieve appropriate communication links to a central sensor data sink even while exploring larger search areas, an agent-based role management strategy is used to provide suitable multi-hop connectivity. The novel algorithms are investigated for static as well as dynamically changing environments. Key results include a detailed realistic aerial channel characterization and network dimensioning analysis considering numbers of MUAVs and density of ground stations vs. exploration speed and sensor data latency.
Article
In this article, the cooperative fault accommodation in formation flight of unmanned vehicles is investigated through a hierarchical framework. Three levels are envisaged, namely a low-level fault recovery (LLFR), a formation-level fault recovery (FLFR) and a high-level (HL). In the LLFR module, a recovery controller is designed by using an estimate of the actuator fault. A performance monitoring module is introduced at the HL hierarchy to identify a partially low-level (LL) recovered vehicle due to inaccuracy in the fault estimate which results in violating the error specification of the formation mission. The HL supervisor then activates the FLFR module to compensate for the performance degradations of the partially LL recovered vehicle at the expense of the other healthy vehicles. Both centralised and decentralised control approaches are developed for our proposed cooperative fault recovery technique. A robust H ∞ controller is designed in which the parameters of the controller are adjusted to accommodate for the partially LL-recovered vehicle by enforcing that the other healthy vehicles allocate more control effort to compensate for the performance degradations of the faulty vehicle. Numerical simulations for a formation flight of five satellites are provided in the deep space, which do indeed confirm the validity and effectiveness of our proposed analytical work.
Conference Paper
Full-text available
Unmanned Aerial Vehicles (UAVs) and in par- ticular quad-rotors are gaining an increasing interest owing to their flexibility and versatility. Today the challenge is to integrate these versatile platforms in a wide fleet in order to perform cooperative tasks as surveillance, search & rescue, inspection. The coalition formation problem is a pre-condition for cooperative missions. This problem can be solved with different methodologies from biologically-inspired algorithms to parasocial consensus sampling ones. In this paper a new framework for simulation of unmanned vehicles in cooperative scenarios is first presented. Then a novel method that exploits the benefits of Model Predictive Control (MPC) for a coalition formation problem (leader-follower) is introduced. The obtained results evidence the good performance of MPC to solve the problem of coalition formation for unmanned aerial vehicles finding the optimal solution taking into account different kind of constraints. The developed framework allows also to easily change from simulated agent to real one.
Conference Paper
A team of unmanned aerial vehicles (UAVs) with limited communication ranges and limited resources are deployed in a region to search and destroy stationary and moving targets. When a UAV detects a target, depending on the target resource requirement, it is tasked to form a coalition over the dynamic network formed by the UAVs. In this paper, we develop a mechanism to find potential coalition members over the network using principles from internet protocol and introduce an algorithm using Particle Swarm Optimization to generate a coalition that destroys the target is minimum time. Monte-Carlo simulations are carried out to study how coalition are formed and the effects of coalition process delays.
Conference Paper
In a search and prosecute mission, multiple heterogeneous unmanned aerial vehicles UAVs that carry different resources need to perform the classify, prosecute and battle damage assessment (BDA) tasks on targets sequentially. Depending on the target resource requirement, it may be necessary to deploy a coalition of UAVs to perform the action. In this paper, we propose coalition formation algorithms that have low computational overhead to determine coalitions for the prosecute and the BDA tasks. We also develop a simultaneous strike mechanism based on Dubins curves for the UAVs to prosecute the target simultaneously. Monte-Carlo simulation results are presented to show how the algorithms work and the effect of increasing the number of BDA tasks on the mission performance.
Article
Unmanned aerial vehicles (UAVs) have the potential to carry resources in support of search and prosecute operations. Often to completely prosecute a target, UAVs may have to simultaneously attack the target with various resources with different capacities. However, the UAVs are capable of carrying only limited resources in small quantities, hence, a group of UAVs (coalition) needs to be assigned that satisfies the target resource requirement. The assigned coalition must be such that it minimizes the target prosecution delay and the size of the coalition. The problem of forming coalitions is computationally intensive due to the combinatorial nature of the problem, but for real-time applications computationally cheap solutions are required. In this paper, we propose decentralized sub-optimal (polynomial time) and decentralized optimal coalition formation algorithms that generate coalitions for a single target with low computational complexity. We compare the performance of the proposed algorithms to that of a global optimal solution for which we need to solve a centralized combinatorial optimization problem. This problem is computationally intensive because the solution has to (a) provide a coalition for each target, (b) design a sequence in which targets need to be prosecuted, and (c) take into account reduction of UAV resources with usage. To solve this problem we use the Particle Swarm Optimization (PSO) technique. Through simulations, we study the performance of the proposed algorithms in terms of mission performance, complexity of the algorithms and the time taken to form the coalition. The simulation results show that the solution provided by the proposed algorithms is close to the global optimal solution and requires far less computational resources.
Article
Multiple UAVs are deployed to carry out a search and destroy mission in a bounded region. The UAVs have limited sensor range and can carry limited resources which reduce with use. The UAVs perform a search task to detect targets. When a target is detected which requires different type and quantities of resources to completely destroy, then a team of UAVs called as a coalition is formed to attack the target. The coalition members have to modify their route to attack the target, in the process, the search task is affected, as search and destroy tasks are coupled. The performance of the mission is a function of the search and the task allocation strategies. Therefore, for a given task allocation strategy, we need to devise search strategies that are efficient. In this paper, we propose three different search strategies namely; random search strategy, lanes based search strategy and grid based search strategy and analyze their performance through Monte-Carlo simulations. The results show that the grid based search strategy performs the best but with high information overhead.
Conference Paper
Novel systems allocating teams of humans and unmanned heterogeneous vehicles are necessary for future applications. An intelligent framework is presented that reasons over a library of coalition formation algorithms to select the most appropriate algorithm(s) to apply to complex missions. The framework is based on decision networks to handle uncertainties in dynamic environments. A group of features is used to identify the most suitable algorithm(s). The proposed framework uses principal component analysis to extract the most significant features that are crucial for making decisions. A technique based on link analysis calculates the utility values for each feature-value pair and algorithm in the library. Experimental results demonstrate that the presented framework accurately chooses the most appropriate coalition formation algorithm(s) based on multiple specified mission criteria and requirements.
Article
Purpose The purpose of this paper is to generate optimised trajectories for an unmanned aerial vehicle (UAV) during a forest fire detection mission. It is assumed that the UAV flies 3D curvature-constrained Dubins manoeuvres and has a limited amount of battery energy that prevents it from covering the entire search area in a single trip. Design/methodology/approach In this paper, the search area is discretised into a grid of multiple targets, and each target assigned with a score that is proportional to the time elapsed since the last UAV visit. This problem, known as Dubins Airplane Orienteering Problem, consists of finding the number and order of targets to visit and the UAV heading at each target that maximises the total trip score without exceeding the UAV battery energy. The solution is found using the Randomised Variable Neighbourhood Search metaheuristic. All target scores are updated after each trajectory generation according to the elapsed time since the last UAV visit. Findings The proposed approach produced feasible results when generating optimised trajectories for a fire detection mission context where energy battery constraints are important. Practical implications The authors carry out the planning of UAV missions with limited amounts of onboard energy such as a real fire detection mission using a single electric propulsion and fixed-wing UAV. Originality/value This paper introduces an energy-based approach to the Dubins Airplane Orienteering Problem, which takes into account the UAV performance and energy budget when generating optimised trajectories.
Conference Paper
Micro-UAVs (Unmanned Aerial Vehicles) attract much interest in a wide range of commercial applications. Due to small size, very limited power and susceptibility to wind their design poses difficult problems in control and motion planning. FPGA technology allows integration of high speed control circuits with efficient hardware implementations of complex algorithms on the same reconfigurable hardware chip. This is a very attractive option for implementation of a micro-UAV computing platform. This paper presents development of control platform for micro-UAVs focusing on integration of lower level control with online motion planning in wind. Some aspects of tight integration of on-board optical sensors with the aircraft control system are also discussed.
Article
This paper addresses a task allocation problem for a team of UAVs that cooperatively performs a search and attack mission in an unknown region. The UAVs are heterogeneous carrying different types and amounts of munition resources, and limited in communications and sensing capabilities. The environment is highly uncertain and dynamic where no prior information is available and dynamic events such as UAV failures unpredictably occur. The objective of the mission is to maximize total reward obtained by destroying targets within a given mission horizon. A group of UAVs may need to be formed to attack a target because individual UAVs may not have sufficient resources for the execution of attack tasks. Instantaneous task allocation approaches that seek for optimal solution for current tasks cannot effectively account for the unpredictability of future tasks in the uncertain dynamic environment. In this paper, we propose a distributed task allocation scheme based on resource welfare of which concept is adopted from economics. The approach we present enables the UAV team to effectively utilize resources by balancing resource depletions and consequently be capable of smoothly responding to dynamic events by retaining more UAVs available. Simulation experiments were conducted in various conditions to evaluate the performance of the proposed approach in comparison with the instantaneous task allocation method. The results show that our approach improves the performance by up to 29.3 % with respect to the instantaneous task allocation method.
Article
In this paper, we address a task allocation problem for a robot team that performs a search and attack mission. The robots are limited in sensing and communication capabilities, and carry different types of resources that are used to attack a target. The environment is uncertain and dynamic where no prior information about targets is given and dynamic events unpredictably happen. The goal of robot team is to collect total utilities as much as possible by destroying targets in a mission horizon. To solve the problem, we propose a distributed task allocation framework incorporated with effective resource management based on resource welfare. The framework we propose enables the robot team to retain more robots available by balancing resources among robots, and respond smoothly to dynamic events, which results in system performance improvement.
Article
Small unmanned aerial vehicles called micro-UAVs are excellent examples of cyber-physical systems which interact with complex and dynamic environments. The success of this technology depends on smart avionics systems compensating for the physical limitations of small airframes, which have very limited on-board power. This paper presents development of micro-UAV for surveillance of open-cut mining sites that represent significant challenges due to difficult terrain and changing wind conditions. The real time aircraft control is integrated with motion planning based on Rapid-exploring Random Tree (RRT) methods which allow efficient handling of the wind factor. The main computational difficulty with RRT in real time motion planning is overcome by employing reduced forward model (RFM) of the aircraft. We also outline some strategies on integrating motion planning, control, and payload processors in reconfigurable hardware to optimise performance and power consumption. The micro-UAV development process is incremental and in large part based on simulations with hardware in the loop but gathering data from experimental flights is essential for accurate reduced forward models. We developed the avionics and experimental vehicle and used it in surveillance missions over mining sites to validate our approach.
Chapter
The chapter addresses two problems that typically arise during the creation of decision support systems that include humans in the information processing workflow, namely, resource management and complexity of decision support in dynamic environments, where it is impossible (or impractical) to implement all possible information processing workflows that can be useful for a decision-maker. The chapter proposes the concept of human-computer cloud, providing typical cloud features (elasticity, on demand resource provisioning) to the applications that require human input (so-called human-based applications) and, on top of resource management functionality, a facility for building information processing workflows for ad hoc tasks in an automated way. The chapter discusses main concepts lying behind the proposed cloud environment, as well as its architecture and some implementation details. It is also shown how the proposed human-computer cloud environment solves information and decision support demands in the dynamic and actively developing area of e-tourism.
Article
To solve the coordination of rendezvous and collision avoidance of multiple air vehicles, a novel cooperative trajectory planning method based on sparse A* algorithm in 3D environment is proposed. This method introduces a new planning frame, which takes the coordination problem into account before and during the trajectory searching process. During the searching process, the method gives considerations to both the original constrains of every trajectory and the collision check between multiple trajectories. Meanwhile, the method could do a heuristic search with some cost factors such as the uncoordinated value and etc. This cooperative planning method can process various constrains effectively and simplify the heuristic factor to get a good performance.
Article
This paper describes a model reduction strategy for obtaining a computationally efficient prediction of a fixed-wing UAV performing waypoint navigation under steady wind conditions. The strategy relies on the off-line generation of time parametrized trajectory libraries for a set of flight conditions and reduced order basis functions functions for determining intermediate locations. It is assumed that the UAV has independent bounded control over the airspeed and altitude, and consider a 2D slice of the operating environment. We found that the reduced-order model finds intermediate positions within 10% and at speeds of 10× faster than clock-time (even in wind conditions in excess of 50% of the UAV's forward airspeed) when compared against simulation results using a medium-fidelity flight dynamics model. The potential of this strategy for online planning operations is highlighted.
Conference Paper
Multi robot systems are of increased demand in industrial environments for easier task execution in short durations. The challenge in deploying a multi robot system for task execution lies in coordinating the robots to perform a task collaboratively within the stipulated time. This paper deals with the following challenge in the multi robot system, first is the search for the most optimal solution for coalition formation, which acquires ample information about the task and the robot agent used, followed by allocating tasks to the robots in the coalition which is commonly referred to as Multi-Robot Task Allocation (MRTA) problem. The optimal solution for robot coalition lies in determining the best number of robots required to complete the task within the deadline that is achieved using dynamic ANT coalition technique which works online. The novelty of the proposed methodology lies in using the most effective local search process of the memetic algorithm rather than using the whole of the memetic algorithm which includes the global search and local search process.
Conference Paper
In cooperative missions, if an individual UAV does not have sufficient resources to neutralize a target then a coalition of UAVs may needs to be formed that fulfills the target resource requirement. This paper proposes an algorithm for the decentralized coalition formation of multiple heterogeneous UAVs that cooperatively perform a search and attack task to neutralize the static ground targets. The main objective of the proposed algorithm is to determine the smallest coalition that would successfully destroy the target in minimum time. First, the responding UAVs are sorted in the ascending order of their resource difference based cost, and then the eligible sets of UAVs with required total resources that can fulfill the target resource criteria are determined. Second, from the eligible sets of UAVs, the algorithm determines the set with minimum time to neutralize the target based on the time of arrival of UAVs on target. Simulation tests to study the performance of proposed approach are carried out and the results are compared with one of the reference sub optimal decentralized coalition formation approach. The results clearly depict that the proposed approach is more effective and gives near optimal solution for the decentralized coalition formation.
Article
Drones are critical to military collaborative engagement, surveillance, and monitoring of areas of interest. They also play an increasingly influential role in commercial applications. We describe a new innovative method for collisionless, survivable, and persistent flying of given $k$ drones over $2n$ waypoints that results in dispersed coverage of a given area of interest, where $n$ > $k \geq 3$ and $k$ divides $n$ . Our method is fundamentally different than any known to date since it does not need sensors to avoid collisions between drones. In addition, the flight of drones doesn’t have to be coordinated.
Article
Full-text available
In this paper, based on task sequence and time constraint in the SEAD mission of multi-UAV, a heterogeneous multi-UAV cooperative task assignment mathematical model is established. We put forward a hybrid algorithm GSA-GA(gravity search algorithm-genetic algorithm) to resolve cooperative task assignment. The algorithm combines gravity search algorithm and genetic algorithm, improves the coding and decoding methods in updating the position. The simulation result shows that the GSA-GA has rapid convergence rate in solving the cooperative task assignment compared with the classic DPSO algorithm, and has the better resolution. © 2018, Editorial Board of Journal of Northwestern Polytechnical University. All right reserved.
Chapter
The chapter addresses two problems that typically arise during the creation of decision support systems that include humans in the information processing workflow, namely, resource management and complexity of decision support in dynamic environments, where it is impossible (or impractical) to implement all possible information processing workflows that can be useful for a decision-maker. The chapter proposes the concept of human-computer cloud, providing typical cloud features (elasticity, on demand resource provisioning) to the applications that require human input (so-called human-based applications) and, on top of resource management functionality, a facility for building information processing workflows for ad hoc tasks in an automated way. The chapter discusses main concepts lying behind the proposed cloud environment, as well as its architecture and some implementation details. It is also shown how the proposed human-computer cloud environment solves information and decision support demands in the dynamic and actively developing area of e-tourism.
Chapter
The paper describes conceptual and technological principles of the human-computer cloud, that allows to deploy and run human-based applications. It also presents two ways to build decision support services on top of the proposed cloud environment for problems where workflows are not (or cannot be) defined in advance. The first extension is represented by a decision support service leveraging task ontology to build the missing workflow, the second utilizes the idea of human-machine collective intelligence environment, where the workflow is defined in the process of a (sometimes, guided) collaboration of the participants.
Article
Coalition structure is an efficient networking architecture for task implementation in unmanned aerial vehicle (UAV) networks. However, both the formation of coalition and the spectrum resource for intra-coalition communication affect the reconnaissance performance. In this paper, we investigate a cooperative reconnaissance and spectrum access (CRSA) scheme for task-driven heterogeneous coalition-based UAV networks by jointly optimizing task layer and resource layer. Specifically, coalition formation game (CFG) is formulated to jointly optimize task selection and bandwidth allocation. In addition to the traditional Pareto order and selfish order, coalition expected altruistic order maximizing coalitions’ utility is proposed. The CFG under the proposed order is proved to be an exact potential game (EPG). Then the existence of stable coalition partition is guaranteed with the help of Nash equilibrium (NE). We propose a joint bandwidth allocation and coalition formation (JBACF) algorithm to achieve stable coalition partition wherein an efficient gradient projection (GP) based method is applied to solve bandwidth allocation. The effectiveness of the proposed scheme and algorithms are demonstrated through in-depth numerical simulations. The results show that our proposed CRSA scheme is superior to non-joint optimization scheme. Also, the proposed order is superior to traditional Pareto order and selfish order.
Article
Novel systems allocating coalitions of humans and unmanned heterogeneous vehicles will act as force multipliers for future real-world missions. Conventional coalition formation architectures seek to compute efficient robot coalitions by leveraging either a single greedy, approximation, or market-based algorithm, which renders such architectures inapplicable to a variety of real-world mission scenarios. A novel, intelligent multi-criteria decision making framework is presented that reasons over a library of coalition formation algorithms for selecting the most appropriate subset of algorithm(s) to apply to a wide spectrum of complex missions. The framework is based on influence diagrams in order to handle uncertainties in dynamic real-world environments. An existing taxonomy comprised of multiple mission and domain dependent features is leveraged to classify the coalition formation algorithms. Dimensionality reduction is achieved via principal component analysis, which extracts the most significant taxonomy features crucial for decision making. A link analysis technique provides the mission specific utility values of each feature-value pair and algorithm in the library. Experimental results demonstrate that the presented framework accurately selects the most appropriate subset of coalition formation algorithm(s) based on multiple mission criteria, when applied to a number of simulated real-world mission scenarios.
Article
Full-text available
The optimal timing of air-to-ground tasks is undertaken. Specifically, a scenario where multiple air vehicles are required to prosecute geographically dispersed targets is considered. The vehicles must perform multiple tasks on each target. The targets must be found, classified, attacked, and verified as destroyed. The optimal performance of these tasks requires cooperation amongst the vehicles such that critical timing constraints are satisfied. In this paper, an optimal task assignment and timing algorithm is developed, using a mixed integer linear program, or MILP, formulation. MILP can be used to assign all tasks to the vehicles in an optimal manner, including variable arrival times, for groups of air vehicles with coupled tasks involving timing and task order constraints. When the air vehicles have sufficient endurance, the existence of a solution is guaranteed.
Article
Full-text available
This paper investigates the problem of decentralized task assignment for a fleet of cooperative UAVs. It extends the analysis of a previously proposed algorithm to consider the performance with different communication network topologies. The results show that the second communication step introduced during the planning phase of the new algorithm is crucial for sparse networks because the convergence rate of the information consensus algorithms can be quite slow. Further analysis shows that the selection of the candidate plans communicated during this plan-ning phase has a significant impact on the performance of the overall algorithm. A comparison of the performance and computation of four selection approaches clearly shows the importance of correctly accounting for the potential actions of the other UAVs, even though that tends to be more computationally expensive. A modification of the original candidate plan selection algorithm is also presented, which further improves the overall performance by increasing the robustness to inconsistencies in the information across the team.
Conference Paper
Full-text available
A multiple UAV search and attack mission in a battlefield involves allocating UAVs to different target tasks efficiently. This task allocation becomes difficult when there is no communication among the UAVs and the UAVs sensors have limited range to detect the targets and neighbouring UAVs, and assess target status. In this paper, we propose a team theoretic approach to efficiently allocate UAVs to the targets with the constraint that UAVs do not communicate among themselves and have limited sensor range. We study the performance of team theoretic approach for task allocation on a battle field scenario. The performance obtained through team theory is compared with two other methods, namely, limited sensor range but with communication among all the UAVs, and greedy strategy with limited sensor range and no communication. It is found that the team theoretic strategy performs the best even though it assumes limited sensor range and no communication.
Book
Full-text available
Not Available
Article
Full-text available
This paper presents a reasoning system that enables a group of heterogeneous robots to form coalitions to accomplish a multirobot task using tightly coupled sensor sharing. Our approach, which we call ASyMTRe, maps environmental sensors and perceptual and motor control schemas to the required flow of information through the multirobot system, automatically reconfiguring the connections of schemas within and across robots to synthesize valid and efficient multirobot behaviors for accomplishing a multirobot task. We present the centralized anytime ASyMTRe configuration algorithm, proving that the algorithm is correct, and formally addressing issues of completeness and optimality. We then present a distributed version of ASyMTRe, called ASyMTRe-D, which uses communication to enable distributed coalition formation. We validate the centralized approach by applying the ASyMTRe methodology to two application scenarios: multirobot transportation and multirobot box pushing. We then validate the ASyMTRe-D implementation in the multirobot transportation task, illustrating its fault-tolerance capabilities. The advantages of this new approach are that it: 1) enables robots to synthesize new task solutions using fundamentally different combinations of sensors and effectors for different coalition compositions and 2) provides a general mechanism for sharing sensory information across networked robots
Article
Full-text available
Coalition formation is a key topic in multiagent systems. One would prefer a coalition structure that maximizes the sum of the values of the coalitions, but often the number of coalition structures is too large to allow exhaustive search for the optimal one. But then, can the coalition structure found via a partial search be guaranteed to be within a bound from optimum? We show that none of the previous coalition structure generation algorithms can establish any bound because they search fewer nodes than a threshold that we show necessary for establishing a bound. We present an algorithm that establishes a tight bound within this minimal amount of search, and show that any other algorithm would have to search strictly more. The fraction of nodes needed to be searched approaches zero as the number of agents grows. If additional time remains, our anytime algorithm searches further, and establishes a progressively lower tight bound. Surprisingly, just searching one more node drops the bound in half. As desired, our algorithm lowers the bound rapidly early on, and exhibits diminishing returns to computation. It also drastically outperforms its obvious contenders. Finally, we show how to distribute the desired search across self-interested manipulative agents.
Article
Despite more than a decade of experimental work in multi-robot systems, important theoretical aspects of multi-robot coordination mechanisms have, to date, been largely untreated. To address this issue, we focus on the problem of multi-robot task allocation (MRTA). Most work on MRTA has been ad hoc and empirical, with many coordination architectures having been proposed and val- idated in a proof-of-concept fashion, but infrequently an- alyzed. With the goal of bringing objective grounding to this important area of research, we present a formal study of MRTA problems. A domain-independent taxon- omy of MRTA problems is given, and it is shown how many such problems can be viewed as instances of other, well-studied, optimization problems. We demonstrate how relevant theory from operations research and combinato- rial optimization can be used for analysis and greater un- derstanding of existing approaches to task allocation, and show how the same theory can be used in the synthesis of new approaches.
Chapter
Numerous coalition formation algorithms exist in the Distributed Artificial Intelligence literature. Algorithms exist that form agent coalitions in both super additive and non-super additive environments. The employed techniques vary from negotiation-based protocols in Multi-Agent System (MAS) environments to those based on computation in Distributed Problem Solving (DPS) environments. Coalition formation behaviors have also been discussed in the game theory literature. Despite the plethora of multi-agent coalition formation literature, to the best of our knowledge none of these algorithms have been demonstrated with an actual multiple-robot system. There exists a discrepancy between the multiagent algorithms and their applicability to the multiple-robot domain. This work aims to correct that discrepancy by unearthing issues that arise while attempting to tailor these algorithms to the multiple-robot domain. A well-known multipleagent coalition formation algorithm has been studied in order to identify the necessary modifications to facilitate its application to the multiple-robot domain.
Conference Paper
The problem of assigning multiple agents to time-dependent cooperative tasks is addressed using a mixed-integer linear program. A time-dependent cooperative task is a task requiring multiple agents to perform separate sub tasks simultaneously or within some predetermined margin where agent availability to perform a subtask is limited to specific intervals in time. By separating the underlying calculation of agent availability and cost from the mechanism of assignment, a method to solve complex cooperative assignment problems can be formulated. A cooperative UAV target tracking/target prosecution scenario is presented to illustrate the assignment method.
Article


text:
Account
It's free!

Register

Share

Books Shortlist

Solution - The differential equation of y=c/x+c^2 is - General and Particular Solutions of a Differential Equation

ConceptGeneral and Particular Solutions of a Differential Equation

Question

The differential equation of y=c/x+c2 is :

(a)x^4(dy/dx)^2-xdy/dx=y

(b)(d^2y)/dx^2+xdy/dx+y=0

(c)x^3(dy/dx)^2+xdy/dx=y

(d)(d^2y)/dx^2+dy/dx-y=0

Solution

(a)

y=c/x+c^2..........(i)

Differentiating w.r.t.x,

dy/dx=c/x^2...........(ii)

(dy/dx)^2=(-c/x^2)^2

(dy/dx)^2=c^2/x^4

x^4(dy/dx)^2=c^2

x^4(dy/dx)^2=y-c/x ["From " (i)]

x^4(dy/dx)^2=y+xdy/dx

x^4(dy/dx)^2-xdy/dx=y

Is there an error in this question or solution?

APPEARS IN

2014-2015 (March)
Question 4.1.3 | 2 marks
Solution for question: The differential equation of y=c/x+c^2 is concept: General and Particular Solutions of a Differential Equation. For the courses HSC Arts, HSC Science (Computer Science), HSC Science (Electronics), HSC Science (General)
S

format: plain


text:
# Thoughts on Kickstarter project, USB Based Variable Power Supply For Small Projects

I am new to electronics and am still just learning. I saw this project on Kickstarter for a small USB based DC power supply and was wondering what some of the more experienced people thought of it.

I am considering buying two for experimentation/hacking at home. Is this a good idea or should I be considering an alternative product?

Link to the Kickstarter project: http://www.kickstarter.com/projects/210251816/usb-based-variable-power-supply-for-small-projects-0. UPDATE: It is closed and didn't meet funding but was relaunced here http://www.kickstarter.com/projects/210251816/usb-variable-power-supply-for-small-projects-relau.

-
Was just reading another question and it said shopping advice was off-topic here. Sorry about that, please feel free to close if this is indeed not a good question to have asked. – spoon16 Jun 9 '12 at 21:46
The "500A" in the project/part number stands for 500 amps, right? – Nick T Jun 9 '12 at 23:57
@NickT, no it is 500 mA. USB 2.0 is limited to 500 mA. – Brian Carlton Jul 5 '12 at 18:04
@BrianCarlton, ever the stooge to my comedy. – Nick T Jul 5 '12 at 19:08

The voltage regulator is a linear regulator with a pot for adjusting the Vout. Any halfway competent hobbyist could hack something together in 30 minutes. 10 minutes for someone that is experienced. They would also likely use a better heat-sink to the max power is higher. And using some leftover wall-warts from "the box of orphaned wall-warts" makes this super cheap. If you hacked something together using spare parts lying around then you might spend US$5 and it would work just as good. The 7-segment display is a waste. It is useful, sure, but there is so much more that could have been achieved with that micro-controller. Here's how I would have designed that device to be much more useful: Use a micro-controller with an actual USB interface. Using a small app on the PC you could control the output voltage and monitor the output voltage and output current. It could implement some sort of programmable overvoltage/current protection as well. Controlling multiple vout's with sequencing or other simple "waveform generation" could be very useful. The power supply itself would be a switching regulator based on a SEPIC topology. This way the output could be either a higher or lower voltage than the input. The output voltage/current is controlled from the micro-controller. It is actually fairly easy to control the output voltage. Output current is a little more difficult, but not impossible. If a low-noise output is required then I would follow the SEPIC regulator with a programmable LDO regulator. Again, the output voltage would be controlled by the micro-controller. Usually the LCD output would be about 0.5v lower than the output of the SEPIC. In this way efficiency is still mostly high, but the output noise would be very low. Then I would design a similar device, but instead of a programmable supply it would be a programmable load. USB controlled. - This product uses a MP1410 2A buck regulator. However, it has a maximum duty cycle of 90%. Instead of SEPIC, I would use a buck regulator IC which can go up to 100% duty cycle. That helps the output go to the point that is almost equal to the input. They are demanding$14K! I am shocked how they could have pledged over $6K! – abdullah kahraman Jun 10 '12 at 8:01 @abdullahkahraman It looks like the picture on the kickstarter page is an old version since it is obviously using a linear reg and not a switcher. Also the text describes an MP1401, while the schematics have the mp1410 that you mention. I still don't understand why you would use a simple buck regulator instead of a sepic, since the sepic would give a larger Vout range than the sepic. – David Kessner Jun 10 '12 at 14:53 Make an edit to improve the original post @DavidKessner and then ask the OP if it fits their needs afterwards, I dont want to close a post with 2 nice answers. – Kortuk Jun 10 '12 at 15:07 I don't think they even have thought on the topology. Probably this design is for hobbyist use for microcontrollers, LCDs, LEDs etc. So, one will use mostly 1.8 to 5.5V. However, if, say, 9V is needed, it probably will be for motor driving and such. Well, 250mA may be enough for lots of hobbyist motors such as small DC motors and servos. Now, a SEPIC sounds very logical. – abdullah kahraman Jun 10 '12 at 17:48 Sir, I'd like to buy your product. – Joel B Jul 5 '12 at 18:22 This is a bad and dangerous design. Without USB negotiation you can only draw 100mA from Vbus. 500mA is only allowed after the device asks the host if its OK. This design has no USB end point at all and no current limiting (except the regs internal limiter) so it breaks specifications if it tries to draw > 100mA whenever it wants. It also doesn't have detection for USB Charging Ports so it can draw full power whenever it wants from VBus rather than when it is safe to do so. Additionally there is no inrush current limiter but a pretty substantial input capacitance. Again the host better have ample protection. In general this is a pretty dangerous device to use unless your really sure your host port has good solid current limiting. I wouldn't plug this into an USB port I cared about continuing to work afterwards. - A good power supply will have its outputs isolated from mains ground. This power supply does not, as far as I can tell. A good power supply will go to +5V, because that was once the most commonly-used supply for digital circuits and is still popular. This supply does not. A good power supply will have an adjustable current limit, for powering things like LEDs, and for safely powering up new circuits for the first time. This circuit does not have an adjustable current limit. Also,$14000 for this design? Any competent hobbyist could do better than this.
I am guessing that they could have designed an isolated power USB power supply with real USB communication using $14K! Hobbyist market is really big.. – abdullah kahraman Jun 10 '12 at 8:03 I agree the design sucks but presumably the$14k isn't for the design but to do a largish production run to keep costs low, $14k sounds about right for a 1000 unit run of these with cases/knobs/etc. – Mark Jun 10 '12 at 20:08 But this is the kind of thing that is easily bootstrapped. There's no need for$14k to make a thousand mediocre power supplies. Hand-assemble fifty and see how that goes. – markrages Jun 10 '12 at 22:29


text:
# Rational points and finite étale covers

This question is broadly about non-trivial examples where a map $f:Y\to X$ of smooth projective $k$-varieties ($k$ not algebraically closed) is such that existence of $k$-points (or in fact $k'$-points for $k'/k$ a finite extension) on $X$ ensures their existence on $Y$. For example, if $f$ is a birational $k$-map, the Lang-Nishimura Theorem guarantees an element of $Y(k)$ if $X(k)$ is not empty.

An interesting example is the case of $f:Y\to X$ being a finite étale cover. In general it will not be the case that a point in $X(k)$ lifts to one in $Y(k)$ (for example elliptic curves and an element in the Tate-Shafarevich group). Are there however examples or conditions that guarantee this happens?

We say that a variety $X/k$ is potentially dense if $X(k')$ is dense in $\bar{X}$ for some finite extension $k'/k$. Campana's classification program conjectures that $X$ is potentially dense if and only $X$ is special (i.e. has trivial core), so in this case, since it seems that a finite étale cover remains special if the base is special, we'd have that the arithmetic of special varieties is preserved under étale covers. But does potential density pull back under finite étale covers?

Related bibliography and any comments on the aforementioned or related topics mentioned are welcome!

Not a full answer but a collection of comments (Edit: Should be a full answer now, see edit at bottom):

Potential density does pull back under etale covers of projective varieties over number fields. The pull-backs of points of $X(K)$ are defined over $L$, with $L/K$ finite, by the Chevalley-Weil theorem.

If $X$ is a Fano variety (i.e. the negative of the canonical class is ample) then Colliot-Thelene conjectured that the Brauer-Manin obstruction is the only obstruction to the Hasse principle. If $f:Y \to X$ be an etale cover with $X$ Fano, then $Y$ is also Fano ($K_Y = f^*(K_X)$). So you might be able to get something that way by assuming this conjecture.

On the opposite end, if $X$ is general type, then so will be $Y$ and the Lang conjecture predicts that $X,Y$ will have few rational points and you probably can find some twist of $Y$ (if the cover is Galois) with no points.

In the intermediate case, your elliptic curve example generalizes to abelian varieties.

Edit: If the cover is etale and Galois then there should be a twist with no points, regardless of the geometry. Chevalley-Weil implies that the set of twists with points is finite, whereas the set of all twists is infinite. E.g. in the case of elliptic curves, never mind the Tate-Shafarevich group, choose an element of the Weil-Chatelet group with no local points.

• Is it not the case that every fano variety is simply connected so any étale cover is trivial? – Daniel Loughran Feb 2 '11 at 22:41
• @Daniel. You might be right, I don't know. – Felipe Voloch Feb 3 '11 at 0:06
• I was not aware of the Chevalley-Weil theorem, thank you! Though Fano varieties are rationally connected and so are simply connected, making étale covers uninteresting. As Campana's work suggests (as does your comment about Lang's conjecture) one would indeed expect interesting examples to lie in "middle" Kodaira dimensions. – Frank Feb 3 '11 at 0:06
• As a reference for the simple connectedness of rationally connected varieties, it goes back to Campana and probably Kollar-Miyaoka-Mori. It's proven for example in Debarre's book 'Higher dimensional algebraic geometry'. – Frank Feb 3 '11 at 0:09

For finite étale morphisms I found the following result in a survey article of Graber, Harris, Mazur and Starr:

Call a flat morphism $\pi:X\to B$ of schemes over a number field $F$ with $B$ smooth and irreducible arithmetically surjective if for every finite degree extension $L/F$, the induced mapping of rational points $X(L)\to B(L)$ is surjective.

$\textbf{Proposition:}$ Let $B$ be an integral, integrally closed scheme over a number field $F$. A finite flat morphism $\pi:X\to B$ defined over $F$ is arithmetically surjective if and only if it admits a section over $F$.


text:
# 3.2 Vector addition and subtraction: graphical methods  (Page 2/15)

 Page 2 / 15

Step 1. Draw an arrow to represent the first vector (9 blocks to the east) using a ruler and protractor .

Step 2. Now draw an arrow to represent the second vector (5 blocks to the north). Place the tail of the second vector at the head of the first vector .

Step 3. If there are more than two vectors, continue this process for each vector to be added. Note that in our example, we have only two vectors, so we have finished placing arrows tip to tail .

Step 4. Draw an arrow from the tail of the first vector to the head of the last vector . This is the resultant    , or the sum, of the other vectors.

Step 5. To get the magnitude of the resultant, measure its length with a ruler. (Note that in most calculations, we will use the Pythagorean theorem to determine this length.)

Step 6. To get the direction of the resultant, measure the angle it makes with the reference frame using a protractor. (Note that in most calculations, we will use trigonometric relationships to determine this angle.)

The graphical addition of vectors is limited in accuracy only by the precision with which the drawings can be made and the precision of the measuring tools. It is valid for any number of vectors.

## Adding vectors graphically using the head-to-tail method: a woman takes a walk

Use the graphical technique for adding vectors to find the total displacement of a person who walks the following three paths (displacements) on a flat field. First, she walks 25.0 m in a direction $\text{49.0º}$ north of east. Then, she walks 23.0 m heading $\text{15.0º}$ north of east. Finally, she turns and walks 32.0 m in a direction 68.0° south of east.

Strategy

Represent each displacement vector graphically with an arrow, labeling the first $\text{A}$ , the second $\text{B}$ , and the third $\text{C}$ , making the lengths proportional to the distance and the directions as specified relative to an east-west line. The head-to-tail method outlined above will give a way to determine the magnitude and direction of the resultant displacement, denoted $\mathbf{\text{R}}$ .

Solution

(1) Draw the three displacement vectors.

(2) Place the vectors head to tail retaining both their initial magnitude and direction.

(3) Draw the resultant vector, $\text{R}$ .

(4) Use a ruler to measure the magnitude of $\mathbf{\text{R}}$ , and a protractor to measure the direction of $\text{R}$ . While the direction of the vector can be specified in many ways, the easiest way is to measure the angle between the vector and the nearest horizontal or vertical axis. Since the resultant vector is south of the eastward pointing axis, we flip the protractor upside down and measure the angle between the eastward axis and the vector.

In this case, the total displacement $\mathbf{\text{R}}$ is seen to have a magnitude of 50.0 m and to lie in a direction $7.0º$ south of east. By using its magnitude and direction, this vector can be expressed as $R=\text{50.0 m}$ and $\theta =7\text{.}\text{0º}$ south of east.

Discussion

The head-to-tail graphical method of vector addition works for any number of vectors. It is also important to note that the resultant is independent of the order in which the vectors are added. Therefore, we could add the vectors in any order as illustrated in [link] and we will still get the same solution.

the range of objects and phenomena studied in physics is
what is Linear motion
straight line motion is called linear motion
then what
Amera
linear motion is a motion in a line, be it in a straight line or in a non straight line. It is the rate of change of distance.
Saeedul
Hi
aliyu
Richard
Linear motion is a one-dimensional motion along a straight line, and can therefore be described mathematically using only one spatial dimension
Jason
what is the formula to calculate wavelength of the incident light
if a spring is is stiffness of 950nm-1 what work will be done in extending the spring by 60mmp
State the forms of energy
machanical
Ridwan
Word : Mechanical wave Definition : The waves, which need a material medium for their propagation, e.g., Sound waves. \n\nOther Definition: The waves, which need a material medium for their propagation, are called mechanical waves. Mechanical waves are also called elastic waves. Sound waves, water waves are examples of mechanical waves.t Definition: wave consisting of periodic motion of matter; e.g. sound wave or water wave as opposed to electromagnetic wave.h
correct
Akinpelu
what is mechanical wave
a wave which require material medium for its propagation
syed
The S.I unit for power is what?
watt
Okoli
Am I correct
Okoli
it can be in kilowatt, megawatt and so
Femi
yes
Femi
correct
Jaheim
kW
Akinpelu
OK that's right
Samuel
SI.unit of power is.watt=j/c.but kw.and Mw are bigger.umots
syed
What is physics
study of matter and its nature
Akinpelu
The word physics comes from a Greek word Physicos which means Nature.The Knowledge of Nature. It is branch of science which deals with the matter and energy and interaction between them.
Uniform
why in circular motion, a tangential acceleration can change the magnitude of the velocity but not its direction
reasonable
Femi
because it is balanced by the inward acceleration otherwise known as centripetal acceleration
MUSTAPHA
What is a wave
Tramsmission of energy through a media
Mateo
is the disturbance that carry materials as propagation from one medium to another
Akinpelu
mistakes thanks
Akinpelu
find the triple product of (A*B).C given that A =i + 4j, B=2i - 3j and C = i + k
Difference between north seeking pole and south seeking pole
if the earth Suddenly contract s then
please formula for density is what
Akinpelu
mass/volume
Jaja
what is motion
In physics, motion is the change in position of an object with respect to its surroundings in a given interval of time. Motion is mathematically described in terms of displacement, distance, velocity, acceleration, time, and speed. ... Momentum is a quantity which is used for measuring the motion of
Karthi


text:
# Bayesian Estimation of Correlation - Now Robust!

So in the last post I showed how to run the Bayesian counterpart of Pearson’s correlation test by estimating the parameters of a bivariate normal distribution. A problem with assuming normality is that the normal distribution isn’t robust against outliers. Let’s see what happens if we take the data from the last post with the finishing times and weights of the runners in the men’s 100 m semi-finals in the 2013 World Championships in Athletics and introduce an outlier. This is how the original data looks:

What if Usain Bolt had eaten mutant cheese burgers both gaining in weight and ability to run faster?

# More Bayesian Football Models

I recently had a lot of fun coding up a Bayesian Poisson model of football scores in the Spanish la Liga. I describe the model, implemented using R and JAGS, in these posts: part 1, part 2, part 3. Turns out that Gianluca Baio and Marta Blangiardo already developed a similar Bayesian model with some extra bells and whistles. For example, they modeled both the defense skill and and offense skill of each team while I used an overreaching skill for each team. They have a paper on their model, which I really enjoyed reading, which can be found here. The model is further discussed on Gianluca Baio’s blog (as I found out after reading about Baio’s blog on statblogs.com). Interesting stuff!

# The Bayesian Counterpart of Pearson’s Correlation Test

Except for maybe the t test, a contender for the title “most used and abused statistical test” is Pearson’s correlation test. Whenever someone wants to check if two variables relate somehow it is a safe bet (at least in psychology) that the first thing to be tested is the strength of a Pearson’s correlation. Only if that doesn’t work a more sophisticated analysis is attempted (“That p-value is still to big, maybe a mixed models logistic regression will make it smaller…”). One reason for this is that the Pearson’s correlation test is conceptually quite simple and have assumption that makes it applicable in many situations (but it is definitely also used in many situations where underlying assumption are violated).

Since I’ve converted to “Bayesianism” I’ve been trying to figure out what Bayesian analyses correspond to the classical analyses. For t tests, chi-square tests and Anovas I’ve found Bayesian versions that, at least conceptually, are testing the same thing. Here are links to Bayesian versions of the t test, a chi-square test and an Anova, if you’re interested. But for some reason I’ve never encountered a discussion of what a Pearson’s correlation test would correspond to in a Bayesian context. Maybe this is because regression modeling often can fill the same roll as correlation testing (quantifying relations between continuous variables) or perhaps I’ve been looking in the wrong places.

The aim of this post is to explain how one can run the Bayesian counterpart of Pearson’s correlation test using R and JAGS. The model that a classical Pearson’s correlation test assumes is that the data follows a bivariate normal distribution. That is, if we have a list $x$ of pairs of data points $[[x_{1,1},x_{1,2}],[x_{2,1},x_{2,2}],[x_{3,1},x_{3,2}],...]$ then the $x_{i,1} \text{s}$ and the $x_{i,2} \text{s}$ are each assumed to be normally distributed with a possible linear dependency between them. This dependency is quantified by the correlation parameter $\rho$ which is what we want to estimate in a correlation analysis. A good visualization of a bivariate normal distribution with $\rho = 0.3$ can be found on the the wikipedia page on the multivariate normal distribution :

# Modeling Match Results in La Liga Using a Hierarchical Bayesian Poisson Model: Part three.

In part one and part two of Modeling Match Results in La Liga Using a Hierarchical Bayesian Poisson Model I developed a model for the number of goals in football matches from five seasons of La Liga, the premier Spanish football league. I’m now reasonably happy with the model and want to use it to rank the teams in La Liga and to predict the outcome of future matches!

## Ranking the Teams of La Liga

We’ll start by ranking the teams of La Liga using the estimated skill parameters from the 2012/2013 season. The values of the skill parameters are difficult to interpret as they are relative to the skill of the team that had its skill parameter “anchored” at zero. To put them on a more interpretable scale I’ll first zero center the skill parameters by subtracting the mean skill of all teams, I then add the home baseline and exponentiate the resulting values. These rescaled skill parameters are now on the scale of expected number of goals when playing home team. Below is a caterpillar plot of the median of the rescaled skill parameters together with the 68 % and 95 % credible intervals. The plot is ordered according to the median skill and thus also gives the ranking of the teams.

Two teams are clearly ahead of the rest, FC Barcelona and Real Madrid CF. Let’s look at the credible difference between the two teams.

# CogSci 2013 in Berlin was Hot!

One month ago I went to UseR 2013 in Albacete, Spain wich was a great conference featuring 33° C and many interesting presentations. Surpisingly CogSci 2013 in Berlin, which I attended this week, was even warmer, outside it is currenly 36° C! There were also many interesting presentations at CogSci 2013 with some of the highlights being:

• The symposia on Music Cognition inlcuding a talk by Edward Large on how to model pitch and harmony perception using dynamical systems.
• A tutorial on Dynamic Field Theory by John Spencer, Gregor Schoener, and Yulia Sandamirskaya. They are working on an introductory book on Dynamic Field Theory which I’m very much looking forward to.
• Two presentations on how to approximate Bayesian computation using artificial neural networks and sparse distributed memory.
• Philip Pärnamets presented fascinating evidence for that what we look at influences decisions in moral desicion tasks and that by manipulating what participants are looking at it is possible to manipulate their moral decisions.

A very diverse list of highlights but that’s cognitive science… I also present a poster (+ conference article) together with Erik Lagerstedt and Peter Gärdenfors on an oscillator model of categorical rhythm perception that we’ve developed. Here’s the abstract:

Categorical perception is a well studied phenomenon in, for example, colour perception, phonetics and music. In this article we implement a dynamical systems model of categorical rhythm perception based on the resonance theory of rhythm perception developed by Large (2010). This model is used to simulate the categorical choices of participants in two experiments of Desain and Honing (2003). The model is able to accurately replicate the experimental data. Our results support that resonance theory is a viable model of rhythm perception and they show that by viewing rhythm perception as a dynamical system it is possible to model properties of categorical perception.

Here’s a link to the full conference article and here is the reference to the article:

Bååth, R., Lagerstedt, E. and Gärdenfors, P. (2013) An Oscillator Model of Categorical Rhythm Perception. In Knauff, M., Pauen, M., Sebanz, N., and Wachsmuth, I. (Eds.) Proceedings of the 35th Annual Conference of the Cognitive Science Society (1803-1808). Austin, TX: Cognitive Science Society.

# Modeling Match Results in La Liga Using a Hierarchical Bayesian Poisson Model: Part two.

In the last blog post I showed my initial attempt at modeling football results in La Liga using a Bayesian Poission model, but there was one glaring problem with the model; it did not consider the advantage of being the home team. In this post I will show how to fix this! I will also show a way to deal with the fact that the dataset covers many La Liga seasons and that teams might differ in skill between seasons.

## Modeling Match Results: Iteration 2

The only change to the model needed to account for the home advantage is to split the baseline into two components, a home baseline and an away baseline. The following JAGS model implements this change by splitting baseline into home_baseline and away_baseline.

Another cup of coffee while we run the MCMC simulation…

# Modeling Match Results in La Liga Using a Hierarchical Bayesian Poisson Model: Part one.

Update: This series of posts are now also available as a technical report:
Bååth, R. (2015), Modeling Match Results in Soccer using a Hierarchical Bayesian Poisson Model. LUCS Minor, 18. (ISSN 1104-1609) (pdf)

This is a slightly modified version of my submission to the UseR 2013 Data Analysis Contest which I had the fortune of winning :) The purpose of the contest was to do something interesting with a dataset consisting of the match results from the last five seasons of La Liga, the premium Spanish football (aka soccer) league. In total there were 1900 rows in the dataset each with information regarding which was the home and away team, what these teams scored and what season it was. I decided to develop a Bayesian model of the distribution of the end scores. Here we go…

Ok, first I should come clean and admit that I know nothing about football. Sure, I’ve watched Sweden loose to Germany in the World Cup a couple of times, but that’s it. Never the less, here I will show an attempt to to model the goal outcomes in the La Liga data set provided as part of the UseR 2013 data analysis contest. My goal is not only to model the outcomes of matches in the data set but also to be able to (a) calculate the odds for possible goal outcomes of future matches and (b) to produce a credible ranking of the teams. The model I will be developing is a Bayesian hierarchical model where the goal outcomes will be assumed to be distributed according to a Poisson distribution. I will focus more on showing all the cool things you can easily calculate in R when you have a fully specified Bayesian Model and focus less on model comparison and trying to find the model with highest predictive accuracy (even though I believe my model is pretty good). I really would like to see somebody try to do a similar analysis in SPSS (which most people uses in my field, psychology). It would be a pain!

This post assumes some familiarity with Bayesian modeling and Markov chain Monte Carlo. If you’re not into Bayesian statistics you’re missing out on something really great and a good way to get started is by reading the excellent Doing Bayesian Data Analysis by John Kruschke. The tools I will be using is R (of course) with the model implemented in JAGS called from R using the rjags package. For plotting the result of the MCMC samples generated by JAGS I’ll use the coda package, the mcmcplots package, and the plotPost function courtesy of John Kruschke. For data manipulation I used the plyr and stringr packages and for general plotting I used ggplot2. This report was written in Rstudio using knitr and xtable.

I start by loading libraries, reading in the data and preprocessing it for JAGS. The last 50 matches have unknown outcomes and I create a new data frame d holding only matches with known outcomes. I will come back to the unknown outcomes later when it is time to use my model for prediction.

# useR 2013 was a blast!

I had a great time at useR 2013 in Albacete, Spain. The food was great, the people were fun and the weather was hot. A pleasant surprise was that I won the useR data analysis contest with my submission “Modeling Match Results in La Liga Using a Hierarchical Bayesian Poisson Model.” It was a fun exercise modeling football scores and I might write a post about it later, for now you can download my original submission here if you’re interested.

I also got great feedback on my talk “The State of Naming Conventions in R”. The message I was trying to get across was basically:

• Naming conventions are important.
• You’re not totally off if you use lowerCamelCase for function names.
• You’re totally off if you use UpperCamelCase for function names.

The talk was based on a short article I got into the RJournal and here are the slides:

Some more awesomeness from UseR 2013:

• Rcpp allows for seamless R and C++ Integration and is ready (talk by Romain Francois).
• Markus Gesmann and Diego de Castilo held a tutorial on the Google viz package. Hans Roslingesque motion charts FTW!
• Kimberly Speerschneider held a presenation on how to vizualize likert scales using the likert package.
• Richie Cotton held an interesting talk with the equally interesting title the Secrets of inverse brogramming. Like me he touched on naming conventions but he also gave a much broader view on how to write beatuiful code in R. The essence of his talk can be found in his very sensible R code style guide.
• The upcoming version of Rstudio boasts a graphical debugger and allows you to write presentations using markdown.

# Three Ways to Run Bayesian Models in R

There are different ways of specifying and running Bayesian models from within R. Here I will compare three different methods, two that relies on an external program and one that only relies on R. I won’t go into much detail about the differences in syntax, the idea is more to give a gist about how the different modeling languages look and feel. The model I will be implementing assumes a normal distribution with fairly wide priors:

Let’s start by generating some normally distributed data to use as example data in the models.

## Method 1: JAGS

JAGS (Just Another Gibbs Sampler) is a program that accepts a model string written in an R-like syntax and that compiles and generate MCMC samples from this model using Gibbs sampling. As in BUGS, the program that inspired JAGS, the exact sampling procedure is chosen by an expert system depending on how your model looks. JAGS is conveniently called from R using the rjags package and John Myles White has written a nice introduction to using JAGS and rjags. I’ve seen it recommended to put the JAGS model specification into a separate file but I find it more convenient to put everything together in one .R file by using the textConnection function to avoid having to save the model string to a separate file. Now, the following R code specifies and runs the model above for 20000 MCMC samples:

# Bayesian estimation supersedes the t-test - Online

The t-test is probably the most used and abused statistical test in research [Citation Needed]. The t-test is used when you have two groups of measures and you want to look at the difference between the groups and the original t-test assumes that the measures are approximately normally distributed and that the two groups have equal variance. While this last assumption is relaxed by Welch’s t-test a large problem remains: The t-test isn’t Bayesian :)

John Kruschke has deviced a Bayesian model that can be used as a drop in replacement for the classical t-test and that he boastingly dubbed BEST (Bayesian EStimation Supersedes the T-test). Instead of uninformative p-values it gives you the actual probability that the two groups are different (given the model), isn’t that nice? BEST even adds some more bells and whistles, the data (not the sampling distribution as in the original t-test) is assumed to come from a t-distribution with an unknown degrees of freedom and as the t-distribution has thicker tails than the normal distribution this helps reducing the influence of outliers in the data. BEST also estimates many more parameters than just the difference between the groups, for example, the difference in variance and the effect size. The full model used by BEST is given in this diagram:

So what is my contribution to all this? Well, I’ve made an online version of BEST that lets you do Bayesian statistics in your browser! I was interested mainly in how well javascript would handle the relatively heavy Markov Chain Montecarlo simulations necessary to run many Bayesian models and BEST seemed like a good target. Turns out it works really well, javascript is pretty fast and with the help of the FLOT library it was easy to create nice looking plots of the analysis. Try it out at http://sumsar.net/best_online/!


text:
# generating a random periodic function with bounded amplitude and bounded fourier coefficients

I would like to generate (i.e. repeatedly compute via a computer) a random periodic function $f(x)$ with period $T$ such that $|f(x)| \leq M$ and the kth Fourier coefficient $|A_k| \leq g(k)$ for a given $g(k)$.

I realize this is kind of open-ended (I'm not giving any information about probability distributions), but is there any way to go about doing this in a way that makes sense?

Here's an example using IPython to plot $$f(\theta)=\cos \theta+\tfrac{1}{2}\cos(3\theta+0.23)+\tfrac{1}{2}\cos(5\theta-0.4)+\tfrac{1}{2}\cos(7\theta+2.09)+\tfrac{1}{2}\cos(9\theta-3)$$

th = np.arange(0,1,0.001)
f = lambda th: np.cos(th*2*np.pi)
plt.plot(th,f(th)+0.5*f(3*th+0.23)
+0.5*f(5*th-0.4)+0.5*f(7*th-2.09)+0.5*f(9*th-3))
plt.ylim([-3, 3])
plt.grid('on')

You'll note that $\sum |A_k| = 3$, which implies that $|f(\theta)|<3$, but here the maximum amplitude is around 2.5, because the harmonics never completely add constructively.

So suppose I just want to choose a function $f(\theta)$ such that $|f(\theta)| \leq M = 1.5$ with $|A_1| = 1$, $A_k \leq \frac{1}{2}$ for odd $3 \leq k \leq 21$, and $A_k = 0$ for all other k.

The bound for M is much smaller than the sum of the upper bound of the amplitudes (6.0), and I don't want to turn a random generation problem into a heuristic rejection algorithm.

-
What do you mean "generate"? In a computational sense? If $A_k$ is any absolutely summable sequence with $\sum |A_k| < M$, then $f(x)=\sum A_ke^{2\pi ikx/T}$ is a function with period $T$ satisfying $|f(x)|<M$. If you want $f$ to have some regularity, then choose $g(k)$ to decay sufficiently fast... math.stackexchange.com/questions/10848/… –  dls Aug 10 at 20:09
yes, a computational sense, let me elaborate; that's too loose of a bound. –  Jason S Aug 10 at 20:14
If you're going to randomly assign phase shifts, there's no way to get a better bound than what you already said/my previous comment. This is because it's possible to attain the maximum: if you have a cosine series, all phase shifts zero and set $\theta=0$. You're probably better off randomly generating the amplitudes/phase shifts, numerically determining the maximum value of the function and rescaling. But it's still not clear exactly what you're after. –  dls Aug 10 at 20:47
re: randomly generating + scaling -- that's about what I thought of, but it skews the resulting probability distribution of the coefficients. –  Jason S Aug 10 at 21:32
From the question, it's not clear to me why this is a problem. How exactly are you using the resulting function? –  dls Aug 11 at 22:19

Expecting $|f|\le 1.5$ is much too optimistic. It's right at the edge of the lower bound given by Parseval's identity, and since a trigonometric polynomial of the required form can't possibly look like a constant, its supremum will exceed its root-mean-square by some margin. It's more realistic to shoot for upper bound that's twice the root-mean-square average of $f$.
Taking a cue from Hardy-Littlewood series, I tried to shift $\cos kt$ by $k\ln k$. The results look good: harmonics fight one another all the time, pushing the function up and down. Here is the sum up to $k=11$
and here is the sum up to $k=21$ (I used $1/2$ for all coefficients after the first)
I don't offer a proof of anything, but shifting by $k\ln k$ is "a way that makes sense".
More precisely, I plotted $$\mathrm{Re} \sum A_k\exp( ikt+ik\ln k) = \sum A_k \cos(kt+k\ln k)$$