General Information

---

Project Description

Over the course of this program I will use Python to simulate a system of multiple agents performing several specific group tasks (i.e. surrounding and closing in on a target, patrolling a perimeter, dispersion and grouping of agents). I will use algorithms published by my advisor and his colleague to create scheduled paths for each agent. The set of all such paths is guaranteed to optimize the total distance travelled by the Hungarian algorithm, and a sequential transfer schedule is used to determine start times of each agent and avoid collisions.

---

Weekly Log

Week 1:

This week I focused on familiarizing myself with the Breadth-First Search (BFS) and Hungarian algorithms. BFS is used to calculate the distance from initial positions of each agent to every possible final position. The Hungarian algorithm is then used to determine which agents should be assigned to which target position so as to minimize total distance travelled by all agents. Referring to the results of BFS, we may then extract the shortest path(s) for each assignment.

Week 2:

After learning the algorithms necessary for optimal assignment and path planning, I created classes in Python to represent a graph and its vertices - where each instance of a vertex has attributes representing its position on the graph and adjacent vertices. After implementing BFS and the Hungarian algorithm, my program outputs the path from each initial vertex to its optimal goal vertex. I am now working to develop a GUI with PyGame to aid with visualization. Next, I will begin scheduling these paths and moving agents from their initial to target positions.

Week 3:

In the third week I worked to build a GUI using PyGame to visualize the movements of agents from their initial to goal positions. I then worked to schedule agent paths to avoid collision. I did not make much progress, however.

Week 4:

After discussing my path scheduling issues with my mentor, he showed me that I needed to change my approach and reorganize the problem using Python dictionaries to represent a Directed Acyclic Graph and the nodes occupied at each time step. After building these I still had trouble unfortunately. I've decided to implement a slightly easier scheduling strategy, where each agent begins travelling at a different time step. This way, I might be able to make some progress on the specific group strategies as discussed with my mentor. I may then implement a more preferable scheduling algorithm in the future.

Week 5:

On friday I met my mentor and discovered that I still misunderstood the path scheduling strategy. I previously believed that the start/goal assignment given by the Hungarian Algorithm determined which goal node each agent should travel to and that the paths these agents should take were determined by the subsequent BFS. However, these methods are only used to induce a directed acyclic graph on the grid. My mentor explained that I should then perform a BFS from standalone goal nodes until an initial node is reached. The previously processed node is then ignored or removed from the graph. I repeat this process until all goal nodes have been scheduled. I worked over the weekend to reorganize my code and implement this strategy. I am nearly there; I only need to refine my method for identifying new standalone goals. Thankfully, I will be able to start working on group strategies in the near future.

Week 6:

After working to reorganize my code and construct a new path scheduling algorithm, I had achieved success with some initial and target formations. However, as I tried new formations, I always encountered new bugs. After seeking out my mentor's grad student for help, he advised to me to begin again with a 3-by-3 grid and two randomly generate initial and goal positions for only two agents. Upon success I should add more agents- the maximum number possible for the size of the grid being eight. This small problem size and increasing complexity should help me to be able to isolate and fix flaws in my algorithm.

Week 7:

Over the weekend and in the first half of this week I followed the advice I had recieved and was able to contruct a scheduling algorithm that works for most (but not all) initial and goal formations. Upon achieving partial success, I was able create some videos to showcase my simulation for the final presentations. In the latter half of the week, I created and practiced my presentation. Over the weekend I hope to refine my path scheduling algorithm. The problem stems from the function which updates the DAG once an initial/goal node pair has been scheduled, and I believe I will be able to resolve this by creating a data structure which keeps track of which goal nodes have been scheduled. I already have a similar structure for initial nodes, and my original thoughts were that I could simply remove previously scheduled goal nodes. However, there are some instances where an unscheduled goal node, a, lies between the interested goal node, b, and some unscheduled initial node, c. In this instance c is the only initial node that the DAG allows to travel to node a. Therefore, we must make node c unavailable for node b.

Week 8:

Finally, with more help from the graduate student, I was able to build a scheduling algorithm which worked for all cases. Instead of merely truncating the DAG or flagging inital/goal nodes as they were processed, I systematically deleted the paths between standalone goal nodes and their assigned initial nodes. Thus, I eliminated problems I was having where initial nodes were assigned such that there existed no feasible paths to some goal nodes. In addition, this approach proved to be much simpler to implement: there were less conditional cases to consider and I was able to eliminate about 300 lines of code. With my program now working smoothly, I was able to begin writing my final report.

Week 9:

This week I continued to write my report. As I did not meet the goal of implementing specific group strategies, my report focuses on my understanding and implementation of the formation control and path scheduling policies presented to me by my mentor.

---

Presentations

• First Presentation
• Final Presentation

---

Additional Information

• My Mentor
  • Dr. Jingjin Yu