Multiagent Learning

Repairmen and Trees

I think I have finally found a problem that has not been studied and is important.  I’m calling it the K-D-Traveling Repairman Problem.  K, the number of repairmen, D, the number of types of repairmen.  The repairman problem is a NP-hard problem and therefore heurstics are used to solve it.  The Predictics group at CMU used Machine learning to approximate solutions to the TRP.  I’ve found one other author that has looked at the K-TRP problem.  I can’t find anyone that has looked at the K-D-TRP.  This is a heterogeneous extension.  Basically I’m saying that there are different types of repairmen that may need to overlap at nodes such in order to perform the repair.

Another interesting extension is a dynamic graph.  Also, I’m interested in looking at saturation levels of repairmen.  Non-deterministic repair times would also be another aspect to look at.  The nice thing with this problem is that it is based on a real world problem that really needs to be solved.

Also, want to look Game theory, optimization theory and expander graphs seem like they will be useful in the theoretic aspect of the problem.  I want to then develop a multi-agent learning algorithm where the agents learn how to solve the problem.

Also, I have been reading about some cool trees: KD-Trees and KD-B-Trees.  They are pretty cool.

Human Trafficking Simulation

Need a game that people play that simulates human trafficking without it actually being human trafficking (since that would just be wrong).  It could be a MMO strategy game that requires the players to distribute mail in a war zone.  So, you can choose  to be the good guy, the mail distributor (which corresponds to the human trafficker and the mail is like the humans).  Or the bad guy and try and stop the mail men.

We can then use machine learning to identify trends in the strategies, social networks and roles that form as the game progresses.  Using this data along with real world human trafficking data we can create a multiagent simulation that can predict the effects of various decisions.

GE on the Future of Manufacturing

I listened to Stephan Biller‘s talk on the future of manufacturing at GE.  I was saddened to hear that like Boeing GE also doesn’t have many of things that I thought they would have.

GE and Boeing both make jet engines and neither has the software to do the rescheduling and re-planning and renegotiation of process when bad things happen.  If something bad happens, people have to either re-plan or just wait for the part. Both options can costs a lot of money.

Also, they don’t have “smart” robots in their manufacturing plants. If one of them stops working then those robots that collaborate with that robot also must stop working. There is no fault tolerance when there should be. This also costs a lot of money.

Many AI and MAS/MAL type things that I am very interested in could be applied to solve these problems.  However, for these companies there would be a huge up-front cost in developing these systems since they would be state-of-the-art.

http://www2.technologyreview.com/emtech/13/

 

Builder Broker

I would imagine that building a house from scratch is pretty difficult for the regular lay person. It would be for me. Making the blue prints, figuring out the permits, what contractors I need and when. Especially if I want to change something or money changes etc there are many dynamic unpredictable things that can change the whole plan. Just think of what happened in Spain when they increased the number of floors during the building stage and they didn’t include a powerful enough elevator to go up the whole way (http://tinyurl.com/kx4jbyh)! I want to create planner and scheduler that will directly connect to the broker that will be dealing with the contractors.

One really has no hope of doing it on there own if you don’t know how a house is put together.

To tackle this problem I would need a someone that is familiar with dealing with contractors and building houses.
At first would most likely have to market this to larger projects. I think that this is necessary for the future of smart cities. Eventually the system would be able to plan how to put together a whole city.

http://www.esri.com/ products would be to figure out the layout of the city. Would want to work with them to make it more collaborative. The whole city planning thing needs to deal with a ton of data. That would be an awesome place to incorporate multiagent learning. Various entities will need to cooperate to decide on things. If we have a system that can ingest the preferences and distribute them across agents in the system then the agents can learn to cooperate to better.

This guy came up with my idea for the instant city in early January 2013!!!! http://video.esri.com/watch/2116/the-instant-citygeodesign-and-urban-planning around 19:32. I am sooo glad its not just me. He thinks it is possible. I not only want what he wants the creation of the plans of how it will look like to be automatic I also want the actually plans and schedules for caring out the “Master Plan” to be automated as well. So I had his idea and took it a step farther. Not only that I think that probably we could then simulate the entire city with the people in it and make improvements to the designs.

Prisons as multiagent systems

Wonder how prisoner transport routes are created and scheduled.  Maybe the whole prison system could be a test bed for “smart cities”.  They are just the controlled environment we need.  Wonder how much tech is involved in prisons currently.

Probably MAL could be applied somewhere.  Might be an application area worth looking into.

Maybe the prisoners, guards, cleaning people, ie the people in the building.  Maybe create a simulation of a prison and create a multiagent planner to assist the decision making regarding prisoner transport.  Maybe a social network.  CV for monitoring prisoner rehabilitation process.    With that data a better simulation can be produced. CV can already spot riots before they happen.

MATSim

Really cool multiagent transportation simulator.  Maybe I will be able to use this in the future.  I want to scale multiagent learning to large number of agents.  I also want to have autonomous vehicles.  So, maybe I can simulate scenarios like finding a parking spot to meet someone, driving in traffic, cooperation between traffic signals and cars, the elimination of traffic lights, stop signs, lanes and the concept of driving on the “right” side of the road (exploring the edge of chaos concept here), ….  Maybe the last idea would be able to locate where traffic concepts should be applied.

Seems like a fun summer project idea.

Bayesian game?

What if we have a stochastic game S and a set of agents A and in each game s we might have a different subset of A playing?  What type of game is that?  This of course is only relevant when dealing with |A| > 2 agents.  Also, the agents that play in each s could be stochastic or fixed. Of course we can always make it harder by making the number actions varied for the agents.

This seems like it could model tournaments if the games are competitive or stochastic coalition games.

This seems sort of like a Bayesian game…  Not sure though.

Stochastic Coalitional Game Theory

In my MAS class I am creating a stochastic normal-form game engine and one of the suggested elaborations is to look at coalitional  games.  So, I was like what if the coalition games were played in a stochastic game setting?

So what is that? Well based on these people at USC it is:

A real-world adversary is often a collection of distributed agents that must communicate and coordinate to enact a joint action and whose the [sic] motivations may not be perfectly aligned. This coordination in particular introduces new issues of stochasticity involving coalition structures, information uncertainty, imperfect execution and robustness.

So, it seems they took the location of the stochasticity further than just the games themselves, but to the robustness of the coalition structures as well.  This is one of their technical approaches to their research.  However, they seem to be the only ones looking at this type of game theory and they have not mentioned it in any of there papers that I can tell.

Co-Opetition!

I finally found the name that describes what I wanted to know if agents could do back in 2010!!!!  My original question was:

I was wondering: if multiple cooperative agent teams are competing, could they learn when it would be in their best interest to cooperate with a competitor.

Now I know I was really wondering if learning agents could learn coopetition!!!

 

I always love to find the right terminology.  It makes life so much easier when doing research.