1
$\begingroup$

I'm on a research of problem, when there is $N$ agents, that work together as a team. Let's assume that they try to destroy as much targets as possible while having limited ammunition. There is also $M$ targets with unknown positions.

Any of agents has limited visibility range. Any member of the team can locate target, when latter got in a visibility range. When agent locates the target, he can take one of two actions: attack or continue searching.

The main point is to make target assignment in a way, that no target would be attacked by more than one agent (I'm not sure if it must be strict requirement). I think, that target selection must be based on some payoffs, for example: probability of destroying target, probability of successful search of new targets, etc.

For simplicity, I assume, that this problem is solved as static: we models some situation, when each team member stands in certain position and observers some targets.

I think that it's an optimization problem, where agents not only maximize their own payoff-functions, but also global (or team) payoff.

Also, one important restriction must be total absence of communication between agents. Consequently, any agent has information only about positions of other team members and targets that fall into his own visibility zone.

My intuition suggests me, that this problem falls into game theoretical field. Because any agent must "play" with his neighbors to decide, who must attack concrete target. As for restriction on communication, it might be game with imperfect information, but my knowledge in this field is very little. I started studying game theory not so long ago.

For today, I found an article on this topic. It's very similar to my research, but, if I understood it correctly, they assume communication during negotiation rounds.

I would be very happy, if anybody points me at concrete literature, researches or topics on this problem. Any suggestions on a problem formulation are welcome.

| cite | improve this question | | | | |
$\endgroup$
2
$\begingroup$

As a first step, model your problem mathematically. You now have a long text, but things are not yet well-defined in this way. For example, how do you measure time? Does an agent have to make a choice the very instant he sees a target, or can he wait a given time for what his neighbors do? Do you assume time to react/aim/notice a target or not? Does your time flow continuously or do you think of discrete time steps?

You are looking for a strategy that allows for minimal amount (=0) of wasted ammunition. But how do you want to plan this strategy? Do you want a predefined algorithm that all agents follow, do you want to make dynamic choices during the running time of your experiment, do you want to introduce probability?
In the last case, you would need to redefine your desired outcome from "no one hit more than once" to "the probability that someone gets hit more than once is $\leq p$ for some given $p$".

It might help to forget about agents and weapons and try to model this as a purely theoretical model, maybe a graph and the time as discrete "steps" that can be taken on there?

In your current form, your problem doesn't seem to be solvable; but that is mostly due to the fact that you yourself don't know yet what exactly you want to solve. If you have that figured out and have it all formally correct, try small examples (two agents, one target) and then take it from there.

| cite | improve this answer | | | | |
$\endgroup$
  • $\begingroup$ First of all, thank you for quick reply. $\endgroup$ – Egor Panfilov Sep 21 '18 at 12:10
  • $\begingroup$ Main concerns I have about time. In my point of view, this problem could be solved from dynamic approach (when we model movement of every agent in time) and from static (when we have fixed positions of all agents and targets). I think, that dynamic approach is more about path planning, rather than about strategy. So, the problem in my opinion should be modeled as static. Thus, we can model it in two phases: actual visibility of targets (with some probability) and then target assignment. $\endgroup$ – Egor Panfilov Sep 21 '18 at 12:19
  • $\begingroup$ Might be, I don't know what fits your problem best. But finding that out and finding the right model in which you can actually employ algorithms or known results is a big task; sometimes even the major part of the work to be done. $\endgroup$ – Dirk Sep 21 '18 at 12:25
  • $\begingroup$ As stated in previous comment, we assume that situation beeing modeled doesn't need take into account "time on react/aim/notice". If you think, this not right approach, please share your thoughts about this $\endgroup$ – Egor Panfilov Sep 21 '18 at 12:26
  • $\begingroup$ Sorry, I answer your questions with a delay, I have bad internet connection now $\endgroup$ – Egor Panfilov Sep 21 '18 at 12:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.