title: how to collaborate multiple pacman agents in a maze without ghosts to eat all food pellets in a time-constrained environment?
body: <p>The problem is actually of a minicontest from the course CS188(intro to AI), UC,berkeley for fall 2018.Here is the link to the minicontest1.</p>
  
  <p>(<a href="https://inst.eecs.berkeley.edu/~cs188/fa18/minicontest1.html/" rel="nofollow noreferrer">https://inst.eecs.berkeley.edu/~cs188/fa18/minicontest1.html/</a>)</p>
  
  <p>In this mini-contest, we have to apply the search algorithms and problems implemented in Project 1(A*,ucs,bfs,dfs) to handle more difficult scenarios that include controlling multiple pacman agents and planning under time constraints(and without ghosts) to eat all foods in the maze before score dropping to 0.There are also penalties for decision time taken,and score boosts up for eating food pellets and more for completing all pellets.</p>
  
  <p>I tried some ways to solve the problem.</p>
  
  <ol>
  <li>Agents which always go towards the closest dot computed by bfs.</li>
  <li>Agents which always turns left whenever there is a chance.</li>
  <li>Agents which keep track of locations they have been to in last 7 chances and don't repeat.(using fixed size queue) and randomly choose an action from the legal actions possible.
  But these agents are not efficient enough as it(last one) gives wins in only 11 or 12 mazes out of 71 mazes with a average score of around 262 on autograder provided for the contest.</li>
  </ol>
  
  <p>I am somehow not able to make these pacman agents collaborate for fast retrieval of all food pellets. </p>
  
  <p>I want some ideas on how to go ahead with this assignment.</p>