MnRI Newsletter — July 2021
From the Director
As we approach the second anniversary of the Minnesota Robotics Institute, we want to highlight the accomplishments of our students in the M.S. in Robotics program. This graduate program is vital to our operations and fulfills one of the tenets of our mission—intertwining high-quality research with high-quality education.
The Master’s of Science Degree in Robotics (Plan A or B) is an interdisciplinary program requiring 31 credits, including completion of a capstone project. Each student is required to take one foundational class from each of the following key areas:
- Cognition (e.g., artificial Intelligence, knowledge representation, planning, decision-making)
- Perception (e.g., computer vision, sensing)
- Robot Modeling and Control (e.g., kinematics, dynamics, locomotion, manipulation)
The remaining credits include the capstone project (3–6 credits) or thesis (10 credits), with the rest coming from a list of elective courses in participating departments that span several different colleges. The program primarily uses existing courses and instructors.
Contrary to other similar programs, our M.S. degree is heavily focused on research. The first cohort, in academic year 2020/2021, included 30 students, and they came from all over the world. Despite the COVID-19 impediments, our retention rate exceeded 95%. Students from this first cohort now work or are doing internships in a variety of companies and entities including HistoSonics, Sentera, Honeywell, Medtronic, Amazon, Northrop Grumman, and the Minnesota Dept. of Transportation, and some are active participants in local robotics start-ups.
Some notable facts about our program:
- Junlin Wu is the first recipient of our M.S. in Robotics degree. He graduated in Spring 2021. We wish him the best.
- More than 70% of students in our first cohort have a cumulative GPA that exceeds 3.6.
- We had 140 applicants and 45 students who committed to attend the M.S. program as part of the second cohort in academic year 2021/2022. One area of concern is that, with some embassies closed due to COVID-19, several incoming international students face difficulties getting visas due.
- More than 15% of our students are from underrepresented groups.
Our program is very proud of the accomplishments of these students and we are eager to welcome our second cohort. We are also happy to see our students playing key roles in several research groups and taking active roles not only in research but in outreach by working with local high school students and groups.
Have a great summer,
Nikos Papanikolopoulos
Minnesota Robotics Institute Director
What would you do if you had 10 robots, 1,000 robots, or 10,000 robots?
If you had a bunch of tasks to accomplish and you could use robots, how many robots would you use? Does the answer depend on the tasks? Are the tasks independent of each other, so they can be done in parallel with no coordination, or do they have precedence or temporal constraints? Do the robots need a central controller to coordinate their work, or could each robot work independently? Who will decide which robot does what task? These are central questions that have been addressed in the work of my research group.
Task allocation to robots
Department of Computer
Science and Engineering
We have worked on a class of task assignment problems where there are constraints on when, where, and in what order tasks need to be executed. We have defined this class of problems, that we call Multi-robot Task Allocation with Temporal and Ordering Constraints (MRTA/TOC) and examined the approaches that have been taken to address it [1]. For scalability and robustness reasons we have focused our work on decentralized approaches, where the allocation of tasks is done using auctions. Robots bid on tasks based on the amount of effort they need to complete each task or the amount of time it will take to do them. We have proposed the Temporal Sequential Single-Item auction (TeSSI) algorithm [2], which uses as the main cost function the makespan (i.e., the time the last robot finishes its final task). Each robot maintains the schedule for the tasks assigned to it. Before bidding on a new task, each robot finds the optimal place in its schedule for that task and uses the makespan of the resulting schedule for its bid. The algorithm supports both offline allocation of tasks, when all the tasks are known upfront, and online allocation, when tasks arrive dynamically. The algorithm has been tested in simulation on multiple problems with up to 100 tasks and up to 50 robots in different environments, both indoors and outdoors [2]. We have extended TeSSI to include ordering constraints in addition to temporal constraints and studied how to model risks in the schedule caused by uncertainty about the time needed to execute the tasks [6].
between tasks: the precedence order is red, blue, green, and yellow. The goal is
to minimize the time to complete the last task.
Swarm robotics
What if we had many more robots, in the order of 1,000 or more? At very large scales, different types of algorithms are needed. Here is where swarm robotics gets into the picture. Swarm robotics aims at using many simple robots to do the tasks. The inspiration comes from nature, in particular insects like ants, bees, and termites that can accomplish complex tasks, such as food collection or nest construction, by contributing individually to the task. There are many reasons why the approach looks intriguing. After all, if small insects can do complex tasks, robots should be able to do the same.
Swarms of robots have four main valuable properties: scalability, emergent self-organization, flexibility, and robustness. We have studied how to measure precisely these properties and use them to provide ways to predict the behavior of a swarm of robots without having to run extensive simulations but using the mathematical characterization of their properties [4, 5].
physical robot experiments for the tasks and
environment shown.
To measure scalability, we compute how much of the observed behavior is due to robots cooperating as opposed to avoiding running into each other. To measure emergent self-organization, we measure if doubling the swarm size in a confined space results in doubling the inter-robot interference when robots are moving randomly. Sub-linear increases in interference indicate self-organization. Third, to measure flexibility, we compare swarm performance in changing environmental conditions to ideal conditions to quantify the ability of the swarm to adapt to changes. Finally, to measure robustness the swarm is modeled as a queue and the rates at which robots enter/leave the queue when they malfunction are used to measure the consistency of swarm performance despite changes in the swarm size.
The traditional task studied for swarms of robots is foraging, which can be used to study real world tasks, such as search and rescue, warehouse transport of objects, garbage collection, and exploration. We have studied how giving the robots the ability to decide how to decompose the foraging task can produce performance improvements [6]. In this case, instead of collecting food and bringing it directly to the nest, robots can partition themselves into “gatherers” and “collectors” and create one or more temporary locations to where gatherers will drop the food and the collectors will take it from there to the nest. We have also studied how to compute the distribution of the “first passage time”, which is the first time when a robot doing correlated random walk reaches a specific location, in this case the nest area, and have extended the results, with some additional assumptions, to multiple robots [7].
References
[1] Ernesto Nunes, Maria Manner, Hakim Mitiche, and Maria Gini. A Taxonomy for Task Allocation Problems with Temporal and Ordering Constraints. Robotics and Autonomous Systems, pp. 55–70, April 2017.
[2] Ernesto Nunes and Maria Gini. Multi-robot auctions for allocation of tasks with temporal constraints. In Proc. of the AAAI Conference on Artificial Intelligence, pp. 2110–2116, 2015.
[3] Ernesto Nunes, Mitchell McIntire, and Maria Gini. Decentralized Multi-Robot Allocation of Tasks with Temporal and Precedence Constraints. Advanced Robotics, 31(22):1193–1207, 2017.
[4] John Harwell and Maria Gini. Swarm engineering through quantitative measurement of swarm robotic principles in a 10,000 robot swarm. In Proc. Twenty-Eighth Int’l Joint Conference on Artificial Intelligence, IJCAI-19, pages 336–342, 7 2019.
[5] John Harwell, London Lowmanstone, and Maria Gini. Demystifying emergent intelligence and its effect on performance in large robot swarms. In Proc. Autonomous Agents and Multi-agent Systems (AAMAS), pages 474–482, 2020.
[6] John Harwell and Maria Gini. Broadening applicability of swarm-robotic foraging through constraint relaxation. Int’l Conf. on Simulation, Modeling, and Programming for Autonomous Robots (SIMPAR), pages 116–122, 2018.
[7] Minyoung Jeong, John Harwell, and Maria Gini. Analysis of Exploration in Swarm Robotic Systems. 16th Int'l Conf. on Intelligent Autonomous Systems (IAS), June 2021.
The Unmanned Aerial Vehicle Laboratory
Gebre-Egziabher —
Department of Aerospace
Engineering and Mechanics
The Unmanned Aerial Vehicle (UAV) Laboratory is part of Aerospace Engineering & Mechanics at the University of Minnesota. Its research primarily deals with guidance, navigation and control (GNC) issues associated with the operation of UAVs (or “drones” as they are referred to in the popular press). The laboratory develops and supports a world-class, low-cost, open-source avionics platform enabling aerospace research and education. The research and education products are all open source and thus, used by other researchers and educators around the world. The laboratory collaborates and works with researchers around the U.S. and internationally. Work is mostly open within the department and worldwide. The UAV Laboratory supports education by bringing real-world aircraft development and flight-testing experiences into undergraduate and graduate level courses available to all students in the college of science and engineering.
While most of the UAVs used for research in the lab are off-the-shelf platforms, the lab has designed aircraft from scratch for some special projects. For example, the airplane shown in Figure 1 and Figure 2 is called the mAEWing-2 was designed and built by the UAV laboratory. This was done under a NASA-sponsored research project known as Performance Adaptive Aeroelastic Wing (PAAW). The goal of the research was to understand how to control aircraft with large and very flexible wings. This research question is the result of the significant current research interest in producing environmentally friendlier aircraft. One of the ways to achieve this is by making aircraft lighter (less weight means less fuel burned) but this results in the structure of the aircraft (especially the wings) being very flexible. A high-speed aircraft with flexible wings can experience a phenomenon known as aerodynamic flutter which is akin to structural resonance seen in large civil structures such as suspension bridges. However, unlike civil structures, the onset of aerodynamic flutter is sudden and normally results in catastrophic structural failure. The PAAW project explored sensing the onset of flutter and then using an array of control surfaces on the trailing edge of the wing (kind of like the feathers on the backside of an eagle’s wing) to suppress the flutter.
tunnel. Figure 2 (right): mAEWing-2 getting ready for flight-testing. The UAV Laboratory does all its flight testing at UMore park on a site that is approved for flight testing of UAVs.
At the heart of the aircraft flown by the UAV laboratory is an open-source flight control system known as Goldy. This flight controller was designed and built by the UAV laboratory and is currently in its third revision (Goldy 3.0). When conducting research, one can load in their own custom controllers, guidance algorithm, sensor fusion algorithms on Goldy. For example, researchers interested in GPS-denied navigation algorithms have used Goldy to test out novel sensor fusion algorithms. Since Goldy is an open source system, it has been used by researchers world-wide including NASA-Armstrong on their Prandtl-D UAV and DLR in Germany. A variant of Goldy (shown in Figure 3) has been spun-off into a commercial venture by a company (Bolder Flight Systems) and is used as the core of custom data collection systems for flight-testing.
A big part of the UAV laboratory’s work is in support and collaboration with local industry, research centers and government agencies. These will be discussed in a future article in the newsletter.
For more information about the research and work done in the UAV Laboratory at the University of Minnesota please contact Chris Regan (rega0051@umn.edu) or Demoz Gebre-Egziabher (gebre@umn.edu).
Awards and Major Grants
Ryan Caverly (top left) and Maziar Hemati (top right), from the Department of Aerospace Engineering and Mechanics, received a U.S. Department of Defense DEPSCoR award of $600,000 for the research project "On-the-Fly Flight Test Maneuver Optimization and Nonlinear Modeling of Hypersonic Systems." The goal of the project is to develop a unified testing and evaluation approach for hypersonic flight systems that involves optimizing both the design of flight test maneuvers and the extraction of reliable control-oriented models.
Researchers led by Professor Suhasa Kodandaramiah (middle left), from the Department of Mechanical Engineering, have developed a unique head-mounted mini-microscope device that allows them to image complex brain functions of freely moving mice in real time over a period of more than 300 days. The device, known as the mini-MScope, offers an important new tool for studying how neural activity from multiple regions of the outer part of the brain, called the cortex, contribute to behavior, cognition, and perception. The research was published in April in the peer-reviewed journal Nature Methods.
Ognjen Ilic (middle right), from the Department of Mechanical Engineering, is a recipient of the 2021 3M Non-Tenured Faculty Award. This award recognizes faculty for outstanding research and leadership and is intended to help young faculty achieve tenure.
Rajesh Rajamani (bottom left), from the Department of Mechanical Engineering, has been appointed Senior Editor of the IEEE Transactions on Intelligent Transportation Systems (T-ITS). T-ITS is the flagship journal of the IEEE Intelligent Transportation Systems Society.
Daniel F. Keefe (bottom right), from the Deparment of Computer Science & Engineering, received the 2021 Bowers Faculty Teaching Award. Each year, the Bowers Award recognizes one outstanding professor who has demonstrated exceptional interest and commitment to the teaching of students in the College of Science and Engineering. This award recognizes Professor Keefe's dedication to teaching, advising and mentoring, curriculum development, and broadening participation in computing.