System Architecture

System Architecture:

Connecting to Multiple Neatos:

A key part of our challenge with this project was talking to multiple Neatos. We created a launch file that automatically creates new connections to multiple Neatos given IP addresses. To interact with these Neatos, each of their topics are now pre-pended with their name (i.e. instead of publishing to `cmd_vel`, we publish to `paul/cmd_vel` if the name of the Neato is "paul". The IP addresses of these Neatos can be written once in the configuration and run multiple times (as opposed to a command line argument passed in every time). 

Agent Motion: 

The videos below show our iterative testing as we first got the code working in simulation, then a single robot, before we integrated it with our launch file to run two neato sat the same time. While debugging the code in the simulation, we learned that the even assuming perfect odom, the code was still moving past the limits. To fix this, we started using proportional control with the velocity, so the max_velocity is multiplied by the distance left to go. Therfore as the robot gets closer to the limits, it starts to slow down and is more accurate. 

Map Server:

1. Map Generation (map_gen.py)

   • This script is responsible for generating the map used in the search and rescue simulation. It uses OpenCV and NumPy libraries to create a grayscale image representing the map. Certain pixels are colored black to simulate obstacles or walls. This script also generates a corresponding YAML file that describes the map's properties, such as resolution and origin, which are essential for the map server to interpret the map correctly.

   • Here's a brief overview of the process:

     • A numpy array is created to represent the map, with white pixels (value 255) indicating free space and black pixels (value 0) indicating obstacles.

     • The map is saved as a PGM (Portable Gray Map) file, and a corresponding YAML file is generated.

2. Launching the Map Server (launch_map_server.py)

   • This script is used to launch the map server, which serves the generated map to other components of the ROS system. The map server is a crucial part of the ROS navigation stack, providing the necessary map data for path planning and navigation.

   • Key aspects of this script include:

     • It sets up a ROS node to run the map server.

     • The map server is configured to use the generated map (PGM and YAML files) as its source.

     • The script includes necessary ROS parameters and configurations for the map server to function correctly.

3. Loading the Map (load_map.py)

   • This script is directly used by the main brain of the system to get information from and to interact with the map. It uses ROS services to retrieve the map from the map server and processes it to create an occupancy field. The occupancy field is a data structure that represents the map in a way that is useful for path planning and navigation algorithms.

   • This script performs the following functions:

     • Retrieves the map from the map server using ROS services.

     • Processes the map data to create an occupancy field, which includes calculating the distance to the nearest obstacle for each cell in the grid.

     • Provides utility functions to interact with the map data, such as getting the closest obstacle distance or the bounding box of obstacles.

Graph Based Multi-agent Navigation:

Our stretch goal for this project was implementing a multi-agent navigation system on a graph based representation of a map. We were able to get started on a proof of concept which can be integrated with our ROS system for future work. Here is a summary of our approach of modifying shortest-path finding algorithms to work with multiple agents.

Multi-Agent A* Implementation Overview

The multi-agent A* algorithm is an extension of the classic A* pathfinding algorithm, adapted to handle multiple agents in a shared environment. The primary challenge in a multi-agent system is to ensure that agents do not interfere with each other's paths, especially in scenarios like search and rescue where efficient coverage of the area is crucial.  In our implementation, we used the Euclidean distance as the heuristic. This choice is based on its simplicity and effectiveness in a grid-based map, providing a direct line-of-sight estimate to the goal.

Modifications for Multi-Agent Search

To adapt A* for multiple agents, we introduced a shared state that tracks the nodes already visited by any agent. This state ensures that once a node is visited by one agent, it is marked as unavailable for others, preventing overlapping paths.

• Graph Creation: When converting the map to a graph, we do not include the obstacles as nodes. This allows us to focus on the agents avoiding each other without worrying about obstacles.

• Shared Visited Nodes: A global set of visited nodes is maintained, which is checked before adding a node to the frontier in the A* algorithm.

• Sequential Processing: Agents are processed one after the other, with each agent's path considering the paths of previously processed agents to avoid overlaps.

Results:

The algorithm seems to perform well with any given number of search agents. For the 2 agent cases the agents successfully traverse from the start to the final goal points without conflicting with each other. Although when we force them to cross paths, they end up traversing really close to each other which is not ideal for searching a space. Similar results are achieved with more than 2 agents.

Multiple agents are able to find the shortest path to their goal while avoiding obstacles

Future Work

The current implementation serves as a foundational framework for multi-agent search in a graph-based environment. Since it focuses on finding the shortest path, the agents can sometimes end up exploring really close to each other while trying to avoid conflicts. But the conflict avoiding aspect of the algorithm can be used as a starting point for future work.

• Dynamic Goal Positions: The current setup does not dynamically define goal positions for each agent. Future work will involve developing a strategy to assign and adapt goal positions based on the search area and the agents' current positions.

• Independent Searching: The algorithm currently does not support independent searching by agents. Implementing a more sophisticated coordination mechanism that allows agents to search different areas independently while avoiding overlaps is a key area for future development.

• Optimization and Scalability: The current sequential approach may not be the most efficient, especially for a large number of agents or a vast search area. Optimizing the algorithm for better performance and scalability is necessary for practical applications.