电网与障碍覆盖算法

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食物补丁模拟，你的机器人应该参观了地图上所有的广场。如果它没有这样做，它肯定不是一个好的机器人;）