Nhiệm vụ cuối cùng của bạn là lập trình cho một "duo cooperative harvester rovers", \(A\) và \(B\), thực hiện một hoạt động quét địa lý đồng bộ phức tạp.
Các "rover" hoạt động trên cùng một "grid", và "movement" của chúng là "random", giống hệt như problem "AI Rover" trước đó. Tuy nhiên, mục tiêu về cơ bản là đã thay đổi. Lưới chứa hai vị trí mục tiêu, \(T_1\) và \(T_2\). Mission chỉ thành công nếu Rover \(A\) ở \(T_1\) VÀ Rover \(B\) ở \(T_2\) trong cùng một "time step" chính xác.

Bài toán này là một trò chơi ngẫu nhiên hợp tác. Bạn phải tìm ra một "optimal joint" \(\pi\) \(*\) \(S_A\), \(S_B\) quy định hành động tốt nhất cho mỗi rover, dựa trên vị trí hiện tại của cả hai.

Dynamics và Rewards:

"Movement": Mỗi rover cố gắng di chuyển "(UP, DOWN, LEFT, RIGHT)". Kết quả là xác suất:
\(P_{fwd}\) cho hướng dự định, \(P_{left}\) cho 90 độ sang bên trái, và \(P_{right}\) cho 90 độ sang bên phải. Va chạm với (#) hoặc "grid edge" khiến rover dừng lại tại chỗ cho đến khi đạt được kết quả đó.

Team Reward Func:

• Team nhận được reward dựa trên "outcome joint action" chung của rover ở mỗi time step.

• Một reward lớn +100 chỉ được trao khi các rover đồng thời chiếm giữ target của nó (A ở \(T_1\), B ở \(T_2\). State này là state "terminal"; mission kết thúc.

• Một reward âm nhỏ "(time cost)" = \(-1\) được áp dụng ở mỗi "time step".

• Một "collision penalty" = \(-5\) được áp dụng cho Team nếu các rover cố gắng di chuyển đến hoặc lọt vào cùng một ô vuông. Nếu xảy ra "collision", cả hai rover sẽ trở lại vị trí trước đó của chúng.

Mục tiêu:

• "Program" của bạn phải giải quyết "multi-agent problem" này, có thể bằng cách điều chỉnh một "algorithm" như "Value Iteration" để hoạt động trên không gian "joint state" \((S_A, S_B)\). Giá trị của một "joint state", \(V * (S_A, S_B)\), là "maximum expected cumulative discounted reward" mà nhóm có thể đạt được. Bạn sẽ phải tính toán giá trị này cho "joint state" ban đầu.

Input:

• Dòng đầu tiên chứa hai số nguyên \(R, C\) tương ứng với số hàng và số cột \((1 ≤ R, C ≤ 15)\)
• Dòng thứ hai chứa ba số thực \(\gamma\) (discount factor), \(P_{fwd}\) và \(P_{left}\)
• Dòng thứ ba chứa bốn số nguyên \(SA_{row}\), \(SA_{col}\), \(SB_{row}\), \(SB_{col}\) (vị trí ban đầu của rover \(A\) và \(B\)).
• \(R\) dòng tiếp theo mô tả "grid layout". Các ký tự có thể là:
  

  '.': (Khoảng trống)
  '#': (Tường không thể vượt qua)
  'T1': (Mục tiêu cho rover \(A\))
  'T2': (Mục tiêu cho rover \(B\))
  

Output:

• Một số thực duy nhất biểu thị giá trị của "joint state" ban đầu, \(V * (S_A, S_B)\). Câu trả lời của bạn phải chính xác đến chữ số thứ 3 sau dấu phẩy.

Example

4 4
0.9 0.8 0.1
0 0 3 3
.  .  . T1
#  #  . .
.  .  # #
T2 .  . . 

66.300