電網與障礙覆蓋算法

Question

我必須找到一個機器人代理做以下（對不起，我真的不知道該怎麼稱呼它）的算法：

• 的機器人在有障礙物的10×10格（每個方格是障礙物或可穿越的）

• 機器人有一個碰撞傳感器：它在機器人碰到障礙物時激活。

• 在網格上有胡蘿蔔是連續增長。有快速增長的正方形和緩慢增長的正方形。

• 每一步，機器人可以：提前或轉90°左右或留在地方

• 胡蘿蔔的位置和障礙物不知道前手

• 胡蘿蔔繼續增長而機器人（即使收穫後）移動

• 胡蘿蔔生長在沒有障礙

• 機器人承擔了大部分的廣場不知道廣場是快速還是緩慢增長

• 在每個廣場可以有0到20個胡蘿蔔。在每個時間點，對於一個正方形的胡蘿蔔數量，有一個概率p = 0.01（或快速增長的正方形的p = 0.02）

• 你可以測量你收穫的胡蘿蔔數量。

目標是在2000步驟中獲得最大量的胡蘿蔔。

會有一個懶/簡單的方法來做到這一點？

到目前爲止，我有點失落，因爲它不是迷宮解決問題。它會是一種排洪算法嗎？有什麼更簡單的嗎？

我不一定搜索以「解決」的問題，而是一個簡單的近似，如果可能的

Answer 1

這確實有點工作要找到它具有完美的策略給它一個機器人實施，不知道食物來源的位置和數量。

任何給定的機器人策略可能不會在每次運行中產生最大可能的收穫。所以問題在於，在多次模擬運行中哪種策略最爲成功。

要找到適合方形類型的給定的統計分佈體面策略（P（快餐），P（slowFood），P（障礙）），人們可能會想出以下的想法：

讓博特（ npatch）是一個尋找npatch食物斑點的機器人。在第一次食物補丁找到第二次食物補丁之前，這種策略會消耗掉它發現的東西，依此類推。當它訪問npatch食物來源（或沒有發現更多食物補丁）時，它會返回到第一個找到並重新收穫的食物來源。

這類殭屍工具（Bot（npatch））現在可以在統計相關數量的仿真運行中相互競爭。最好的機器人是比賽的勝利者。

這種方法可以被認爲是基於遺傳算法的啓發，但沒有混合任何基因，而只是迭代所有基因（1..npatch）。也許有人有一個想法如何把這個想法變成一個完全的遺傳算法。這可能涉及轉向Bot（npatch，searchStrategy），然後有多個基因來應用遺傳算法。

每當模擬參數發生變化時，競爭必須重複，顯然取決於世界上的食物補丁數量，如果某些食物補丁可能會或可能無法獲得又一個食物補丁已知。

下面的代碼是用F＃編寫的，它是這個問題的模擬器（如果我的要求正確，那就是......）。寫一個新的機器人就像編寫一個函數一樣簡單，然後傳遞給模擬器。

想想這個我的復活節彩蛋，適合那些想嘗試自己的機器人的人。

我寫的2個機器人被稱爲「marvinRobot」，它可以做Marvin會做的事情，而「lazyRobot」是一個在它找到的第一個食物來源營地的機器人。

type Square = 
    | Empty 
    | Obstacle 
    | Food of float * (float -> float) // available * growth 
    | Unknown 

let rnd = new System.Random() 
let grow p a = 
    let r = rnd.NextDouble() 
    if r < p then a + 1.0 
    else a 

let slowGrowth a = grow 0.01 a 
let fastGrowth a = grow 0.02 a 

let eatPerTick = 1.0 
let maxFoodPerSquare = 20.0 

let randomPick values = 
    let count = List.length values 
    let r = rnd.Next(0,count-1) 
    values.Item(r) 

type World = Square[,] 

let randomSquare pobstacle pfood = 
    let r = rnd.NextDouble() 
    match r with 
    | x1 when x1 < pobstacle -> Obstacle 
    | x2 when x2 < (pobstacle + pfood) && x2 >= pobstacle -> 
     Food(rnd.NextDouble() * maxFoodPerSquare, randomPick [slowGrowth; fastGrowth]) 
    | _ -> Empty 

let createRandomWorld n pobstacle pfood = 
    Array2D.init n n (fun col row -> randomSquare pobstacle pfood) 

let createUnknownWorld n = 
    Array2D.create n n Unknown 

type Position = { Column : int; Row : int } 

type RoboState = { Memory : Square[,]; Pos : Position; Heading : Position } 
type RoboAction = 
    | TurnRight 
    | TurnLeft 
    | MoveOne 
    | Eat 
    | Idle 

type RoboActor = World -> RoboState -> RoboAction 

let right heading : Position = 
    match heading with 
    | { Column = 0; Row = 1 } -> { Column = -1; Row = 0 } 
    | { Column = -1; Row = 0 } -> { Column = 0; Row = -1 } 
    | { Column = 0; Row = -1 } -> { Column = 1; Row = 0 } 
    | { Column = 1; Row = 0 } -> { Column = 0; Row = 1 } 
    | _ -> failwith "Invalid heading!" 

let left heading : Position = 
    match heading with 
    | { Column = -1; Row = 0 } -> { Column = 0; Row = 1 } 
    | { Column = 0; Row = -1 } -> { Column = -1; Row = 0 } 
    | { Column = 1; Row = 0 } -> { Column = 0; Row = -1 } 
    | { Column = 0; Row = 1 } -> { Column = 1; Row = 0 } 
    | _ -> failwith "Invalid heading!" 

let checkAccess n position = 
    let inRange v = v >= 0 && v < n 
    (inRange position.Column) && (inRange position.Row) 

let tickWorld world = 
    world 
    |> Array2D.map 
     (fun sq -> 
      match sq with 
      | Empty -> Empty 
      | Obstacle -> Obstacle 
      | Food(a,r) -> Food(min (r a) maxFoodPerSquare, r) 
      | Unknown -> Unknown 
     ) 

let rec step robot world roboState i imax acc = 
    if i < imax then 
     let action = robot world roboState 
     match action with 
     | TurnRight -> 
      let rs1 = { roboState with Heading = right roboState.Heading } 
      let wrld1 = tickWorld world 
      step robot wrld1 rs1 (i+1) imax acc 
     | TurnLeft -> 
      let rs1 = { roboState with Heading = left roboState.Heading } 
      let wrld1 = tickWorld world 
      step robot wrld1 rs1 (i+1) imax acc 
     | MoveOne -> 
      let rs1 = 
       let c = 
        { Column = roboState.Pos.Column + roboState.Heading.Column 
         Row = roboState.Pos.Row + roboState.Heading.Row 
        } 
       if checkAccess (Array2D.length1 world) c 
       then 
        match world.[c.Column,c.Row] with 
        | Obstacle -> 
         roboState.Memory.[c.Column,c.Row] <- Obstacle 
         roboState 
        | _ -> { roboState with Pos = c } 
       else 
        roboState 
      let wrld1 = tickWorld world 
      step robot wrld1 rs1 (i+1) imax acc 
     | Eat -> 
      let eat,acc1 = 
       match world.[roboState.Pos.Column,roboState.Pos.Row] with 
       | Empty -> Empty,acc 
       | Obstacle -> Obstacle,acc 
       | Food(a,r) -> 
        let eaten = if a >= eatPerTick then eatPerTick else 0.0 
        printfn "eating %f carrots" eaten 
        Food(a - eaten, r),eaten + acc 
       | Unknown -> Unknown,acc 
      world.[roboState.Pos.Column,roboState.Pos.Row] <- eat 
      let wrld1 = tickWorld world 
      step robot wrld1 roboState (i+1) imax acc1 
     | Idle -> 
      step robot (tickWorld world) roboState (i+1) imax acc 
    else 
     acc 

let initRoboState n = 
    { Memory = createUnknownWorld n; 
     Pos = { Column = 0; Row = 0;}; 
     Heading = {Column = 1; Row = 0} 
    } 

let simulate n pobstacle pfood imax robot = 
    let w0 = createRandomWorld n pobstacle pfood 
    let r0 = initRoboState n 
    printfn "World: %A" w0 
    printfn "Initial Robo State: %A" r0 
    let result = step robot w0 r0 0 imax 0.0 
    printfn "Final Robo State: %A" r0 
    result 

// Not that Marvin would care, but the rule for this simulator is that the 
// bot may only inspect the square in the world at the current position. 
// This means, IT CANNOT SEE the neighboring squares. 
// This means, that if there is a obstacle next to current square, 
// it costs a simulation tick to find out, trying to bump against it. 
// Any access to other squares in world is considered cheating! 
// world is passed in spite of all said above to allow for alternate rules. 
let marvinRobot world roboState = 
    Idle 

// Tries to find a square with food, then stays there, eating when there is something to eat. 
let lazyRobot (world : World) (roboState : RoboState) = 
    let search() = 
     let status action : RoboAction = 
      match action with 
      | TurnLeft -> printfn "%A TurnLeft at %A (heading: %A)" world.[roboState.Pos.Column,roboState.Pos.Row] roboState.Pos roboState.Heading 
      | TurnRight -> printfn "%ATurnRight at %A (heading: %A)" world.[roboState.Pos.Column,roboState.Pos.Row] roboState.Pos roboState.Heading 
      | MoveOne -> printfn "%A MoveOne at %A (heading: %A)" world.[roboState.Pos.Column,roboState.Pos.Row] roboState.Pos roboState.Heading 
      | Idle -> printfn "%A Idle at %A (heading: %A)" world.[roboState.Pos.Column,roboState.Pos.Row] roboState.Pos roboState.Heading 
      | Eat -> printfn "%A Eat at %A (heading: %A)" world.[roboState.Pos.Column,roboState.Pos.Row] roboState.Pos roboState.Heading 
      action 
     let neighbors = 
      [ roboState.Heading, MoveOne; 
       (roboState.Heading |> right),TurnRight; 
       (roboState.Heading |> left),TurnLeft; 
       (roboState.Heading |> right |> right),TurnRight 
      ] 
      |> List.map (fun (p,a) -> (p.Column,p.Row),a) 
      |> List.map (fun ((c,r),a) -> (roboState.Pos.Column + c,roboState.Pos.Row + r),a) 
      |> List.filter (fun ((c,r),a) -> checkAccess (Array2D.length1 world){Position.Column = c; Row = r}) 
      |> List.sortBy (fun ((c,r),a) -> match roboState.Memory.[c,r] with | Food(_,_) -> 0 | Unknown -> 1 | Empty -> 2 | Obstacle -> 3) 
      |> List.map (fun ((c,r),a) -> { Column = c; Row = r},a) 
     if neighbors.IsEmpty then failwith "It's a trap!" // can happen if bot is surrounded by obstacles, e.g. in a corner 
     else 
      let p,a = neighbors.Head 
      status a 
    roboState.Memory.[roboState.Pos.Column, roboState.Pos.Row] <- 
      world.[roboState.Pos.Column,roboState.Pos.Row] 
    match world.[roboState.Pos.Column,roboState.Pos.Row] with 
    | Food(a,_) -> 
     printfn "Found food at %A" roboState.Pos 
     Eat 
    | _ -> 
     search() 

//simulate 10 0.1 0.05 2000 marvinRobot 
simulate 10 0.1 0.1 2000 lazyRobot 

最後不是至少提示：如果您0.0食物補丁模擬，你的機器人應該參觀了地圖上所有的廣場。如果它沒有這樣做，它肯定不是一個好的機器人;）