Heterogeneous UGV-MAV exploration using integer programming

This paper presents a novel exploration strategy for coordinated exploration between unmanned ground vehicles (UGV) and micro-air vehicles (MAV). The exploration is modeled as an Integer Programming (IP) optimization problem and the allocation of the vehicles(agents) to frontier locations is modeled using binary variables. The formulation is also studied for distributed system, where agents are divided into multiple teams using graph partitioning. Optimization seamlessly integrates several practical constraints that arise in exploration between such heterogeneous agents and provides an elegant solution for assigning task to agents. We have also presented comparison with previous methods based on distance traversed and computational time to signify advantages of presented method. We also show practical realization of such an exploration where an UGV-MAV team efficiently builds a map of an indoor environment.

Authors

• Ayush Dewan
• Aravindh Mahendran
• Nikhil Soni
• K. Madhava Krishna

Keywords

• Cameras
• Optimization
• Robot kinematics
• Equations
• IP networks
• Linear programming
• Computation Time
• Distribution System
• Indoor Environments
• Practical Constraints
• Exploration Strategy
• Graph Partitioning
• Ground Vehicles
• Multiple Teams
• Heterogeneous Agents
• Micro Air Vehicles
• Unmanned Ground Vehicles
• Point Cloud
• Linear Problem
• Performance Gain
• Optimal Formulation
• Problem Description
• Previous Forms
• Simultaneous Localization And Mapping
• Camera Pose
• Integer Programming Formulation
• Integer Programming Problem
• Occupancy Grid
• Absence Of Constraints
• Linear Programming Relaxation
• Branch-and-cut
• Integer Constraints
• Laser Ranging
• Feasible Space
• Facility Location Problem