Logistieke Robots/les 5

Les 5 - Robots laten samen werken

In de vorige les heb je een controller gemaakt voor 1 robot om bestellingen te kunnen verzamelen. In deze les leer je om een team van twee robots samen te laten werken om mogelijk sneller de bestellingen te laten verzamelen.

Je kan een team van twee robots op veel verschillende manieren met elkaar samen laten werken. In de praktijk heb je vaak te maken met beperkingen zoals het maximale gewicht wat een robot kan tillen. Wij gaan in onze simulatie uit van de volgende restrictie:

Robots kunnen in één keer meerdere artikelen meenemen uit een kast indien deze artikelen dezelfde zijn. Dit geldt niet voor verschillende artikelen.

Bij een enkele robot kunnen we ons dus voorstellen dat hij eerst de hele bestelling doorneemt om te kijken of er dezelfde artikelen in zitten. Wanneer dit het geval is loopt de robot naar de juiste kast en pakt een pakket waar al twee dezelfde artikelen in zitten. Een efficiëntie verbetering kunnen we vervolgens uitdrukken als het aantal minder gelopen meters.

We implementeren in deze les het volgende scenario: 2 robots werken samen om 2 bestellingen op te halen waarbij de bovengenoemde voorwaarde nog steeds geld en waarbij de robots niet naar dezelfde kasten lopen. We richten ons in deze les vooral op de programmering dan op de visualisatie.

embedvideo http://youtu.be/nEgubbYwRy0 /embedvideo

Bijhouden van de gelopen afstand

Voordat we efficiëntie verbeteringen kunnen detecteren, moeten we eerst de huidige situatie kunnen meten. Dit doen we aan de hand van de gelopen afstand in meters van de robot. Hoe je dit doet leer je in deze paragraaf.

Verandering robot controller

Logisch is dat we een extra variabele gaan creëren die de gelopen afstand van de robot opslaat. Minder logisch is dat we ook de 3 verschillende coördinaten bijhouden van de robot. De coördinaten van de x,y en z as kun je ophalen met de functie positon. Waarom dit nodig is zien we zo. De variabelen declareer je op de volgende positie:

def get_order():
    # get articles from central controller
    robot["articles"] = start_sens.bodies[0][1:]
    print(robot["articles"])
    # set game properties
    robot["article_number"] = 1 
    robot["target_desk"] = False 
    robot["robot_id"] = start_sens.bodies[1]
    # distance variables
    robot["distance"] = 0.0
    robot["location1"] = robot.position[0]
    robot["location2"] = robot.position[1]
    robot["location3"] = robot.position[2]

Wanneer de order ingepakt is geef je niet alleen de robot id mee aan de centrale controller maar ook de gelopen afstand. Wanneer de robot een nieuwe order krijgt wordt de afstand namelijk weer op 0 gezet. Hoe de centrale controller omgaat met dit bericht zien we in de volgende paragraaf.

GameLogic.sendMessage("Done", robot["robot_id"] , "Ground", "")
GameLogic.sendMessage("Done", str(robot["distance"]) , "Ground", "")

Het updaten van de gelopen afstand gaat op de volgende manier:

main()
robot["distance"] += robot.getVectTo([robot["location1"], robot["location2"], robot["location3"]])[0]
loc1 = robot.position[0]
loc2 = robot.position[1]
loc3 = robot.position[2]
robot["location1"] = loc1
robot["location2"] = loc2
robot["location3"] = loc3

Iedere keer als je de controller aanroept gebruik je de functie getVectTo() om de afstand te berekenen tussen de locatie waar de robot op dat moment is en de laatst opgeslagen locatie. Vervolgend update je de locatie coördinaten naar degene waar de robot nu staat. Zo kan je de totaal gelopen afstand van de robot bijhouden.

Verandering centrale controller

De robot moet zijn eigen gelopen afstand bij houden maar de centrale controller moet dit voor alle robots doen. Hiervoor is dus ook een variabele nodig:

if sens.positive:
    robot = "11"
    central["distance"] = 0
    Send_order(robot)

De waarde van de variabele wordt aangepast als de centrale controller een message krijgt. De gelopen afstand is het tweede bericht gestuurd door de robot en deze is dus te vinden in message.bodies[1]. Wanneer alle orders zijn vervuld, kun je de totale afstand van de robot printen op de volgende manier:

if message.positive:
    central["boxes_done"] +=1
    print("number of boxes done:")
    print(central["boxes_done"])
    central["distance"] += float(message.bodies[1])
    if central["boxes_done"] < central["boxes_tot"]
        robot = message.bodies[0]
        Send_order(robot)
    else:
        print("Total walked distance:")
        print(central["distance"])

Experiment

Nu kunnen we gaan meten hoe efficiënt de robot is in de huidige situatie. Dit doen we door het huidige algoritme een aantal keer te draaien: we gaan een experiment doen. Meerder runs zijn nodig omdat de bestelling steeds verschilt. Op basis van één run kunnen we niet zeggen hoe het algoritme gemiddeld presteert. Het kan namelijk zo zijn dat je alleen naar de dichtstbijzijnde kast hoeft te lopen. Dit is geen goede representatie van een gemiddelde bestelling. Daarom doen we nu 5 runs.

Hieronder staan de uitkomsten van een experiment:

Run	Afstand
Run 1	615
Run 2	709
Run 3	683
Run 4	698
Run 5	719
Gemiddelde	684,8

Doe zelf ook een experiment met minimaal 5 runs en bekijk of het gemiddelde overeenkomt met de resultaten in bovenstaande tabel. Hoe meer runs je hebt, hoe preciezer je schatting van de prestatie van de robot.

Efficiëntie verbetering voor 1 robot

In het vorige algoritme kon het zo zijn dat de robot 2 keer naar dezelfde kast moest lopen. Het gevolg van de voorwaarde die we in het begin van deze les introduceerden is dat dit niet meer hoeft. We gaan nu zien hoe we dit moeten veranderen en wat het gevolg is op de prestatie.

Verandering centrale controller

We moeten nu gaan bedenken wat de beste manier is om deze opzet te implementeren in het systeem. Logischer is dat de robot de order doorgaat en zoekt naar dubbelen. Maar dit is programmeer technisch gezien meer werk. Daarom laten we de centrale controller kijken of er dubbele in de order zitten. We hoeven dan geen aanpassingen te doen in de robot controller en maar een kleine aanpassing in de centrale controller:

def Send_order(robot_team):
    pre_order = [random.choice(box_articles) for t in range(central["box_size"])]
    pre_order = list(set(pre_order))
    order = ""
    for j in range(len(pre_order)):
            order += " " + pre_order[j]
    GameLogic.sendMessage("Start", order , "Robot_"+robot, "Ground")
    GameLogic.sendMessage("Start", robot , "Robot_"+robot, "Ground")

Zoals je kunt zien moet je nu gebruik maken van een array voor het aanmaken van de bestelling. Dan kun je namelijk de functie list() en set() gebruiken voor het eruit halen van dubbele artikelen. Aan de robot kunnen we alleen een string meegeven en daarom moeten we de array nog omzetten in een string. De grootte van de order kan nu 1, 2 of nog steeds 3 zijn.

Experiment

De resultaten zijn nu als volgt:

Run	Afstand
Run 1	495
Run 2	592
Run 3	599
Run 4	437
Run 5	648
Gemiddelde	554,2

Te zien is dat de gemiddelde afstand van een run naar beneden is gegaan met 130,6 meter. Als je deze afstand omzet naar de tijd die de robot daardoor sneller is kun je nadenken of je moet investeren in robots die meer artikelen uit een kast kunnen halen. Wanneer de investering namelijk kleiner is dan de opbrengt zal dit voor extra winst zorgen.

Efficiëntie verbetering door samenwerking

Dat we een verbetering zouden zien is natuurlijk begrijpelijk omdat de robots ineens meer kunnen tillen. Interessanter is dat we met deze simulatie hebben kunnen zien wat de efficiëntie winst precies zal zijn en of het zin heeft om in deze complexere machines te investeren.

We gaan nu kijken naar de efficiëntie verbetering is door met een team van 2 robots te werken. Naast de vermindering in totaal gelopen meters gaan we nu ook kijken naar de tijd die het kost om de orders in te pakken.

Creëren team

De robots gaan nu in tweetallen werken om de artikelen op te halen. Er zijn veel mogelijkheden hoe de robots samen kunnen werken. Verdelen van soorten artikelen, eerstvolgende artikel op de lijst ophalen, eerst de verste artikelen etc. Omdat de robots naast elkaar staan maakt het qua gelopen afstand niet veel uit welke robot welk artikel haalt. Het gaat hier dus vooral om de winst in tijd. We gaan twee verschillende algoritmen implementeren. Eerst geven we de robots verantwoordelijkheid over de helft van de artikelen en vervolgens kijken we naar een goede verdeling op basis van de binnengekregen order.

Om een team aan het werk te kunnen zetten, moeten we wel een team hebben. Selecteer Robot_11 en kopieer de robot (ctrl+c, ctrl+v voor Windows en cmd+c, cmd+v voor Mac) druk op de toets G en de toets X en sleep robot naar achter. Je hebt nu twee robots:

Verander de naam van de tweede robot in Robot_10 op de volgende manier:

Verwijder de extra python controllers door deze te selecteren en op ‘x’ te drukken. Zorg ervoor dat je alleen de twee onderstaande controllers overhoudt:

Voeg de robot controller toe aan Robot_10:

Veranderingen centrale controller

We nemen de code weer stap voor stap onder handen. Bij het definiëren van de box_articles is het nu handiger als de “Shelf_” er niet voor staat. Waarom zien we zo.

# define game properties
central["boxes_tot"] = 5
central["box_size"] = 3
box_articles = [1,2,3,4,5,6,7,8]

In plaats dat we nu een robot meegeven aan Send_order() geven we een team mee. We moeten nu ook bijhouden of de robots op hun teammaatje aan het wachten zijn voordat een nieuwe order kan gaan starten. Hiervoor maken we een array aan met de waarden 0/1 voor 11 robots. Naast de afstand houden we ook de tijd bij.

if sens.positive:
    robot_team = ["10","11"]
    central["active_robots"] = [0,0,0,0,0,0,0,0,0,0,0]
    central["distance"] =0
    central["time"] = 0.0
    Send_order(robot_team)

De order wordt nu twee keer zo lang omdat de robots samen werken. We knippen de order op bij artikel 4. Robot 10 gaat dus artikelen 1, 2, 3 en 4 ophalen en Robot 11 de rest:

def Send_order(robot_team):
    pre_order = [random.choice(box_articles) for t in range(len(robot_team)*central["box_size"])]
    pre_order = list(set(pre_order))
    pre_order.sort()
    order = ""
    order2= ""
    
    for j in range(len(pre_order)):
        if j <= len(pre_order)/2 -1 :
            order += " Shelf_" + str(pre_order[j])
        else:
            order2 += " Shelf_" + str(pre_order[j])
    GameLogic.sendMessage("Start", order , "Robot_"+robot_team[0] , "Ground")
    GameLogic.sendMessage("Start", robot_team[0] , "Robot_"+robot_team[0] , "Ground")
    central["active_robots"][int(robot_team[0])-1]=1
    GameLogic.sendMessage("Start", order2 , "Robot_"+robot_team[1] , "Ground")
    GameLogic.sendMessage("Start", robot_team[1] , "Robot_"+robot_team[1] , "Ground")
    central["active_robots"][int(robot_team[1])-1]=1

Wanneer de robot klaar is met zijn deel van de bestelling moet hij wachten op zijn teamgenoot voordat er een nieuwe order kan starten. Dit kan op de volgende manier geprogrammeerd worden:

if message.positive:
    central["active_robots"][int(message.bodies[0])-1]=0
    central["distance"] += float(message.bodies[1])
    if central["boxes_done"] < central["boxes_tot"]-1 and central["active_robots"][10-1]+central["active_robots"][11-1]==0:
        central["boxes_done"] +=1
        print("number of boxes done:")
        print(central["boxes_done"])
        Send_order(["10","11"])
    if sum(central["active_robots"]) == 0: 
        print("Total walked distance:")
        print(central["distance"])
        print(central["time"])
 
central["time"]+= 1/60

De tijd wordt bijgehouden met central[“time”]. Hiervoor moet je een Always sensor toevoegen met een pulse. Deze geeft 60 keer per seconde een pulse aan de central controller. Door bij iedere pulse 1/60 toe te voegen aan de variabele, kunnen we de tijd bijhouden.

In de robot.py kun je print(“done robot 11”) vervangen door onderstaande regel:

print("done robot "+ str(robot["robot_id"]))

Experiment

Hieronder staan de resultaten van een experiment.

Experiment 1

Run	Afstand	Tijd
Run 1	929	124
Run 2	879	134
Run 3	1092	154
Run 4	863	121
Run 5	805	109
Gemiddelde	913,6	128,4

Als we de gemiddelde afstand willen vergelijken met de afstanden uit de vorige experimenten moeten we dit getal eerst delen door 2 omdat er nu 2 keer zoveel bestellingen gedaan worden. We zien dan weer een verbetering in het totaal gelopen meters. Omdat dit niet erg verassend is gaan we nu kijken naar het tweede algoritme. Hier bekijken we een slimmere aanpak voor het verdelen van de artikelen in de order zodat de robots minder lang op elkaar wachten. We kunnen zo een winst in tijd behalen.

Experiment 2

Nu kan het voorkomen dat het aantal op te halen artikelen erg verschillend is doordat de artikelen alleen in kast 1 t/m 4 of 5 t/m 8 staan. Dit willen we gaan verbeteren. Dit kun je op de volgende manier doen: kijk naar het aantal artikelen in de array pre_order en deel dit door 2. Bij een oneven aantal artikelen krijgt Robot 11 het extra artikel. De code ziet er dan als volgt uit:

def Send_order(robot_team):
    pre_order = [random.choice(box_articles) for t in range(len(robot_team)*central["box_size"])]
    pre_order = list(set(pre_order))
    pre_order.sort()
    order = ""
    order2= ""
    
    for j in range(len(pre_order)):
        if j <= len(pre_order)/2 -1 :
            order += " Shelf_" + str(pre_order[j])
        else:
            order2 += " Shelf_" + str(pre_order[j])

De resultaten van het experiment zijn nu:

Run	Afstand	Tijd
Run 1	950	114
Run 2	940	111
Run 3	940	112
Run 4	993	117
Run 5	996	116
Gemiddelde	963,8	114

We zien dat, ondanks de verhoging van het aantal gelopen meters, de totale tijd afgenomen is. Dit is dus een echte verbetering van het algoritme omdat dezelfde opstelling gebruikt wordt maar er slimmer gebruik wordt gemaakt van de robots.

Plusopdracht

Bedenk andere manieren om de taken tussen de robots te verdelen om de gelopen afstand of tijd naar beneden te krijgen. Doe hier experimenten mee