MỤC LỤC

LỜI CẢM ƠN…………………………………………………………….........................…...i

TÓM TẮT NỘI DUNG ĐỒ ÁN………………………………...………..........................…..1

MỤC LỤC………………………………………………………….......................……….......2

DANH MỤC HÌNH VẼ…………………………………..………………..........................….3

DANH MỤC BẢNG…………………………………..……..……………….....................….4

CHƯƠNG 1. TỔNG QUAN ĐỀ TÀI………………………………………..........................5

1.1 Giới thiệu về bài toán đóng gói hộp (Bin packing).....................................................6

1.2 Học tăng cường - Reinforcement Learning...............................................................7

1.2.1 Tổng quan về học tăng cường...............................................................................7

1.2.2 Các thành phần trong một hệ thống học tăng cường...........................................10

1.2.3 Markov Decision Processes (MDP).......................................................................11

1.3 Mạng Multi-layer perceptron (MLP)..........................................................................19

1.3.1 Perceptrons cơ bản...............................................................................................19

1.3.2 Kiến trúc mạng Neural nhân tạo............................................................................21

1.3.3 Kiến trúc mạng Neural Multi-layer perceptron (MLP).............................................21

1.4 Graph Attention Networks.........................................................................................23

1.4.1 Scale dot prodcut attention....................................................................................23

1.4.2 Graph Attentional Layer.........................................................................................24

CHƯƠNG 2. PHƯƠNG PHÁP ĐÓNG GÓI SỬ DỤNG HỌC TĂNG CƯỜNG..............27

2.1 Thiết lập các thông số liên quan đến học tăng cường..............................................27

2.2 Packing Configuration Tree - PCT (Cấu hình cây đóng gói).....................................27

2.2.1 Cấu hình cây đóng gói...........................................................................................28

2.2.2 Các phương pháp mở rộng nút lá..........................................................................29

2.3 Triển khai thuật toán Deep Reinforcement Leaning..................................................31

CHƯƠNG 3. HỆ THỐNG ĐÓNG GÓI HỘP TỰ ĐỘNG.................................................33

3.1 Tổng quan về hệ thống.............................................................................................33

3.2 Giới thiệu về Dobot Magician...................................................................................36

3.3 Datamatrix................................................................................................................38

3.3.1 Datamatrix.............................................................................................................38

3.3.2 Camera.................................................................................................................39

CHƯƠNG 4. KẾT QUẢ NGHIÊN CỨU VÀ ĐÁNH GIÁ................................................40

4.1Giao diện mô phỏng bài toán đóng gói hộp..............................................................40

4.2 Kết quả mô phỏng bài toán đóng gói hộp................................................................41

4.2.1 Kết quả mô phỏng với Setting 1...........................................................................41

4.2.2 Kết quả mô phỏng với Setting 2...........................................................................43

4.2.3 So sánh kết quả mô phỏng các Setting...............................................................45

4.3 Thực nghiệm trên sản phẩm thực tế.......................................................................47

CHƯƠNG 5. KẾT LUẬN..............................................................................................49

TÀI LIỆU THAM KHẢO................................................................................................50

PHỤ LỤC......................................................................................................................51

TÓM TẮT NỘI DUNG ĐỒ ÁN

Ngày nay, việc tích hợp những thành tựu Trí tuệ nhân tạo như thị giác máy tính, xử lý ngôn ngữ tự nhiên hay xử lý âm thanh trong việc nghiên cứu và phát triển robot trở nên không còn xa lạ đối với chúng ta. Robot ngày một trở nên thông minh và tương tác với con người hiệu quả hơn. Bên cạnh đó, một hướng nghiên cứu mới cũng đang thu hút sự quan tâm của nhiều nhà nghiên cứu là áp dụng học tăng cường cho bài toán điều khiển robot. Học tăng cường bao gồm ba thành phần chính là trạng thái, hành động và phần thưởng. Thông qua việc tương tác giữa robot với môi trường, phương pháp cho phép robot “học” được một hoặc nhiều hàm chính sách tối ưu tương ứng với việc tối ưu giá trị kỳ vọng của tổng giá trị phần thưởng nhận được. Nhờ vậy mà sau quá trình huấn luyện, robot có thể thực hiện được nhiều nhiệm vụ khó khăn hơn, thậm chí với một số nhiệm vụ cụ thể, phương pháp cho thấy kết quả tốt hơn so với một vài phương pháp điều khiển cổ điển. Hướng nghiên cứu của đề tài nghiên cứu tập trung vào giải quyết bài toán đóng gói hộp vào thùng. Robot sẽ “học" được cách gắp và xếp các hộp cho sẵn nhằm đạt được tối đa số lượng hộp được đóng gói . Qua quá trình nghiên cứu và phát triển trên một tay máy robot mô phỏng, kết quả đầu ra chứng minh được rằng robot có thể thực hiện thành công việc đóng gói hộp hình hộp chữ nhật một cách hiệu quả. Mặc dù phương pháp tồn tại một vài hạn chế như tính ổn định chưa thực sự cao, tốn kém tài nguyên tính toán thì hướng nghiên cứu trên cũng rất đáng hứa hẹn. Trong tương lai khi đã đạt kết quả mong muốn trên môi trường mô phỏng, nhóm mong muốn có thể triển khai đề tài trên robot thật và đánh giá kết quả.

                                                                                                                                                      Hà Nội, ngày … tháng … năm 20

                                                                                                                                                        Sinh viên thực hiện

                                                                                                                                                          ……………..

CHƯƠNG 1. TỔNG QUAN ĐỀ TÀI

1.1 Giới thiệu về bài toán đóng gói hộp (Bin packing)

Bài toán đóng gói hộp (Bin Packing): Vấn đề Đóng gói thùng được công nhận rộng rãi là một thách thức tối ưu hóa thường xuyên phát sinh trong lĩnh vực robot thao tác. Mục tiêu của bài toán này là đóng gói hiệu quả càng nhiều hộp càng tốt vào một thùng duy nhất.  

Trước đây, các nhà nghiên cứu chủ yếu tập trung nghiên cứu vấn đề đóng gói hộp với giả định rằng kích thước của hộp đã được xác định trước, gọi là Offline BPP [1]. Tuy nhiên, trong các ứng dụng thực tế như hậu cần và kho bãi, không phải lúc nào cũng khả thi để có thể nhìn thấy đầy đủ tất cả các hộp trước đó. Thay vào đó, trọng tâm đã chuyển sang nghiên cứu rộng rãi vấn đề về hộp đóng gói không xác định kích thước, được gọi là Online BPP [2].

1.2 Học tăng cường - Reinforcement Learning

1.2.1 Tổng quát về học tăng cường

- Học tăng cường (Reinforcement Learning): là một lĩnh vực con của học máy (machine learning) tập trung vào cách các tác nhân (agents) hành động trong một môi trường để tối đa hóa phần thưởng tổng cộng. Trong học tăng cường, một tác nhân học cách hành động thông qua việc thử và sai, nhận phản hồi dưới dạng phần thưởng hoặc hình phạt từ môi trường. Học tăng cường được ứng dụng rộng rãi trong các lĩnh vực như trò chơi điện tử, rô bốt, tối ưu hóa hệ thống, tài chính, chăm sóc sức khỏe, hệ thống khuyến nghị, và logistics nhờ khả năng học từ tương tác và tối ưu hóa hành động để đạt mục tiêu cụ thể.

Học tăng cường (Reinforcement Learning - RL) có thể được hiểu đơn giản là "học cách hành động" [4], bằng cách ánh xạ các trạng thái với hành động (action) để tối đa hóa phần thưởng (reward). Thay vì được cung cấp sẵn hành động cần thực hiện, tác nhân (agent) phải tự khám phá xem hành động nào mang lại phần thưởng lớn nhất thông qua việc thử nghiệm. Điểm đặc biệt và cũng là thách thức lớn của học tăng cường là các hành động không chỉ ảnh hưởng đến phần thưởng tức thời mà còn tác động đến các tình huống sau này, ảnh hưởng đến toàn bộ phần thưởng trong tương lai.

Học tăng cường khác với học có giám sát. Học tăng cường tập trung vào tối ưu hóa hành động để đạt được phần thưởng lớn nhất dài hạn từ môi trường, trong khi học có giám sát học từ các cặp dữ liệu huấn luyện đã biết để dự đoán hoặc phân loại dữ liệu mới. Hai bài toán cơ bản trong học có giám sát là phân loại (classification) và hồi quy (regression). Phân loại có biến đầu ra là các giá trị rời rạc, còn hồi quy có biến đầu ra là các giá trị liên tục. 

Để học tăng cường đạt được tiến bộ, cần thiết phải thiết kế các hệ thống phần thưởng rõ ràng để hướng tới mục tiêu của tác nhân. Quá trình này cũng liên quan đến việc tối ưu hóa chính sách ra quyết định của tác nhân để tối đa hóa phần thưởng dựa trên trạng thái hiện tại và các hành động có thể thực hiện. Đồng thời, khám phá và khai thác môi trường là thách thức quan trọng, đảm bảo rằng tác nhân có đủ khả năng khám phá và học hỏi để cải thiện chiến lược của mình. Quản lý và xử lý các vấn đề liên quan đến việc học từ các phần thưởng trì hoãn cũng là yếu tố quan trọng trong quá trình này, cùng với việc tối ưu hóa hiệu suất và tính hiệu quả của thuật toán để đạt được sự hội tụ nhanh chóng và hiệu quả cao hơn trong môi trường học tăng cường.

Một trong những đặc điểm nổi bật nhất của học tăng cường hiện đại là cách nó liên kết và tương tác hiệu quả với các lĩnh vực khoa học và kỹ thuật khác. Học tăng cường không chỉ là một lĩnh vực đơn lẻ mà nó còn đóng vai trò là một công cụ mạnh mẽ để giải quyết các vấn đề phức tạp trong nhiều ngành. Ví dụ, trong robot học, học tăng cường giúp các robot tự học và cải thiện hành vi của chúng khi tương tác với môi trường xung quanh. Trong tự động hóa và điều khiển, nó có thể được sử dụng để tối ưu hóa quá trình và giảm thiểu lỗi trong hệ thống tự động. Đặc biệt, học tăng cường cũng có ứng dụng mạnh mẽ trong lĩnh vực y học, nơi nó có thể giúp trong việc phát triển các hệ thống hỗ trợ quyết định cho việc chẩn đoán và điều trị bệnh.

1.2.2 Các thành phần cơ bản của hệ thống học tăng cường

Học tăng cường (Reinforcement Learning - RL) bao gồm bốn thành phần chính: chính sách (policy), tín hiệu phần thưởng (reward signal), hàm giá trị trạng thái (value function), và mô hình môi trường (model of environment).

- Chính sách (policy) xác định cách thức hoạt động của tác nhân tại một thời điểm cụ thể. Chính sách xác định cách mà tác nhân phản ứng với trạng thái hiện tại và quyết định hành động tiếp theo dựa trên mục tiêu tối đa hóa phần thưởng trong quá trình học. Chính sách có thể được biểu diễn dưới dạng một hàm, bảng quyết định, hoặc một phương pháp quyết định khác, phụ thuộc vào bài toán cụ thể và cách mà môi trường phản hồi lại hành động của tác nhân. Trong các thuật toán học tăng cường, mục tiêu là học hoặc tìm ra chính sách tối ưu, tức là chính sách mang lại tổng giá trị phần thưởng lớn nhất có thể trong lâu dài khi tác nhân tương tác với môi trường. Chính sách là cốt lõi của một tác nhân học tăng cường vì nó quyết định hành vi của tác nhân.

- Tín hiệu phần thưởng (reward signal) xác định mục tiêu của học tăng cường. Tại mỗi bước, môi trường gửi đến tác nhân một giá trị số gọi là phần thưởng. Phần thưởng xác định sự kiện tốt hay xấu đối với tác nhân, tương tự như trải nghiệm niềm vui hoặc nỗi đau trong hệ thống sinh học. Phần thưởng là cơ sở để thay đổi chính sách, nếu một hành động nhận được phần thưởng thấp, chính sách có thể thay đổi để chọn hành động khác trong tương lai.

1.2.3 Markov Decision Processes (MDP)

1.2.3.1. Môi trường và tác nhân

MDP (Markov Decision Process) là một khung công cụ toán học được sử dụng rộng rãi trong học tăng cường để mô hình hóa quá trình ra quyết định tuân theo các nguyên tắc Markov. MDP mô tả một tác nhân (agent) tương tác với một môi trường (environment) qua một chuỗi các thời điểm rời rạc. MDP giả định rằng tất cả các thông tin quan trọng để ra quyết định ở thời điểm ttt được tóm gọn trong trạng thái hiện tại của hệ thống, không cần quan tâm đến lịch sử trước đó. Điều này gọi là tính Markov của quá trình. MDP cung cấp một cách cụ thể và toán học để mô tả và giải quyết các vấn đề quyết định trong môi trường không chắc chắn và đa dạng.

Ở đây, tác nhân và môi trường tương tác với thông qua một chuỗi độc lập theo thời gian, =1,2,3,… . Ở mỗi trạng thái t, tác tử nhận được một vài thông tin từ trạng thái của môi trường, S_t∈S , và hàm chính sách giúp xác định hành động tương ứng A_t∈ A(s)^3. Sau khi nhận hành động từ tác nhân, tác nhân nhận về một giá trị điểm thưởng R_{t+1} ∈R⊂R , và chuyển sang trạng thái kế tiếp S_(t+1). Qua đó, ta có chuỗi các trạng thái, hành động và điểm thưởng: S₀,A₀,R₁,S₁,A₁,R₂,S₂,S₂,A2,R₃,…

p(s',r│s,a)≐Pr⁡{S_t=s',R_t=r ┤| S_(t-1)=s,A(_t-1)=a }                       PT 1.1

∑(s'∈S)∑(r∈R)〖p(s',r│s,a)=1,for all s∈S,a∈A(s)                PT 1.2

MDP (Markov Decision Process) là một khung làm việc linh hoạt cho các bài toán liên quan đến tương tác nhằm đạt được mục tiêu. Trong MDP, người học và người ra quyết định được gọi là tác nhân, và những gì tác nhân tương tác với được gọi là môi trường. Quá trình tương tác này diễn ra liên tục, với tác nhân lựa chọn hành động và môi trường phản hồi bằng cách chuyển sang một trạng thái mới. Đồng thời, môi trường gửi cho tác nhân phần thưởng, là các giá trị số mà tác nhân cố gắng tối đa hóa theo thời gian thông qua các hành động của mình.

MDP rất linh hoạt và có thể áp dụng cho nhiều vấn đề khác nhau. Khoảng bước nhảy trong các phương trình không cần phải cố định. Một ví dụ tương tự có thể là về một hệ thống tự động hóa trong nhà máy sản xuất. Hệ thống này có thể có các cảm biến mức thấp để đo nhiệt độ, áp suất, hoặc dòng điện. Các hành động ở mức điều khiển cấp thấp có thể bao gồm việc điều chỉnh nhiệt độ hoặc áp suất trong các thiết bị sản xuất. Tuy nhiên, các hành động ở mức độ cao hơn có thể là quyết định về việc khởi động, dừng máy, hoặc chuyển đổi giữa các chế độ sản xuất khác nhau, dựa trên thông tin mà các cảm biến gửi đến và mục tiêu sản xuất được đặt ra.

1.3.2.2. Điểm thưởng và mục tiêu

Trong Markov Decision Process (MDP), điểm thưởng là một giá trị số học được môi trường trả về cho tác nhân sau mỗi hành động, thể hiện mức độ thành công hay không thành công của các hành động đối với mục tiêu của tác nhân. Điểm thưởng này cung cấp cho tác nhân thông tin phản hồi về hiệu quả của chiến lược hành động mà nó chọn. Mục tiêu trong MDP là xác định trạng thái hoặc tập hợp các trạng thái mà tác nhân cố gắng đạt được hoặc duy trì trong quá trình tương tác với môi trường. Mục tiêu này hướng dẫn tác nhân trong việc lựa chọn hành động và tối ưu hóa chiến lược để đạt được kết quả mong muốn trong hệ thống.

Nếu bạn muốn tác nhân thực hiện một nhiệm vụ cụ thể, bạn cần cung cấp phần thưởng sao cho việc tối đa hóa phần thưởng tương đương với việc hoàn thành nhiệm vụ. Do đó, điều quan trọng là phần thưởng phải thực sự phản ánh mục tiêu bạn muốn đạt được. Đặc biệt, tín hiệu phần thưởng không nên cung cấp thông tin chi tiết cho tác nhân về cách đạt được mục tiêu. Ví dụ, một tác nhân chơi giải đố chỉ nên được nhận thưởng khi giải được hoàn toàn câu đố, không phải cho các mục tiêu phụ như tìm kiếm bằng chứng hay giải các câu đố phụ. Nếu gán phần thưởng cho các mục tiêu phụ, tác nhân có thể cố gắng đạt được chúng mà không đạt được mục tiêu chính.

1.2.3.3. Quá trình và phần thưởng trả về

Ở phần trên ta định nghĩa mục tiêu của học tăng cường là tìm cách tối đa hóa tổng lượng điểm thưởng mà tác nhân nhận được trong suốt quá trình tương tác với môi trường. Giờ ta cần tìm cách thực hiện việc tối đa hóa này bằng cách nào? Nếu chuỗi điểm thưởng nhận được là  sau thời điểm  thì điểm thưởng trả về  sẽ được tác nhân cố gắng tìm cách tối đa hóa giá trị kì vọng của nó, với  là kí hiệu  của điểm thưởng trả về được xác định như sau:

G_t = R_(t+1)+R_(t+2)+⋯+R_T PT 1.3

1.2.3.4. Hàm giá trị trạng thái và chính sách

Các thuật toán học tăng cường thường tập trung vào tính toán các hàm giá trị trạng thái (value functions) hoặc giá trị trạng thái-hành động (state-action values) vì các hàm giá trị này cung cấp cho tác nhân thông tin về "tốt xấu" của từng trạng thái và cặp trạng thái-hành động dựa trên ước lượng về điểm thưởng mà tác nhân có thể thu được trong tương lai.

Hàm giá trị trạng thái V(s) cho biết giá trị dự kiến mà tác nhân sẽ nhận được khi bắt đầu từ trạng thái sss và tuân theo một chính sách nhất định. Đây là tổng giá trị các điểm thưởng mà tác nhân có thể nhận được từ trạng thái sss trở đi.

Về hình thức, một chính sách là ánh xạ từ các trạng thái đến xác suất của việc lựa chọn hoạt động tương ứng của nó và nếu tác nhân tuân theo chính sách Π tại thời điểm t, thì Π(a|s) là xác suất để A_t=a nếu St =s. Giống như p,Π là một hàm bình thường; dấu “|” ở giữa Π(a|s) chỉ thể hiện rằng nó xác định tỉ lệ xác suất trên a∈A(s) cho mỗi s∈S.

Tương tự như vậy, ta định nghĩa hàm giá trị hành động trạng thái (Q value) của việc thực hiện hành động  ở trạng thái  tuân theo chính sách , kí hiệu là  sẽ là kì vọng giá trị trả về khi bắt đầu từ trạng thái , thực hiện hành động  tuân theo chính sách :

q_Π (s,a)≐E_Π [G_t ┤| S_t=s,A_t=a]=E_Π [∑(_k=0)^∞γ^k R_(t+k+1) | S_t=s〗,A_t= a]                   PT 1.6

Các hàm giá trị v_Π và q_Π có thể được ước lượng từ trải nghiệm. Để minh họa, giả sử một tác nhân tuân thủ chính sách Π và ổn định ở mức giữa một cách nhất quán với giá trị trả về thực tế thu được sau khi gặp mỗi trạng thái. với giá trị trả về thực tế nhận được sau trạng thái đó, sau đó giá trị trung bình sẽ được hội tụ về giá trị của trạng thái, v_Π (s).

1.3 Mạng Multi-layer perceptron (MLP)

Học sâu (Deep Learning) đã thu hút sự chú ý lớn nhờ vào khả năng xử lý các bài toán phức tạp trong lĩnh vực như phân loại ảnh, phân đoạn hình ảnh, và nhận diện. Khác với các phương pháp học máy cơ bản, học sâu cho phép mô hình hóa và tương tác với dữ liệu phức tạp như ảnh, âm thanh, văn bản và nhiều loại dữ liệu khác.

Một trong những phương pháp học sâu phổ biến là Multi-layer Perceptron (MLP), là một mạng nơ-ron nhân tạo feedforward. Đây là một kiến trúc mạng lưới mà các nút đầu vào kết nối với các nút của lớp tiếp theo, và các lớp này lại kết nối với nhau như một đồ thị có hướng từ đầu vào đến đầu ra.

MLP đã được chứng minh là hiệu quả trong nhiều ứng dụng, nhưng cũng có hạn chế như đòi hỏi lượng dữ liệu lớn để huấn luyện một cách hiệu quả, và không thể mô hình hóa các mối quan hệ phức tạp như các mạng nơ-ron sâu (deep neural networks) khác. Tuy nhiên, nó vẫn là một công cụ quan trọng và được sử dụng rộng rãi trong các ứng dụng học máy và xử lý dữ liệu.

1.3.1 Perceptrons cơ bản

Perceptron được cấu thành bới các Neural đơn lẻ là một mạng Neural. Neural nhân tạo được lấy cảm hứng từ Neural sinh học như 1.5.

Ở hình 1.5, có thể thấy một mạng Neural cơ bản có thể có nhiều dữ liệu vào và chỉ có một dữ liệu ra duy nhất. Ở hình dưới đây, cấu trúc của perceptron cũng có những đặc điểm như vậy.

1.3.2 Kiến trúc của một mạng Neural

Mạng neural [5] bao gồm các đơn vị cơ bản gọi là neuron, được tổ chức thành các lớp:

Một mạng Neural có 3 kiểu lớp với các đặc điểm:

- Lớp đầu vào (Input layer): Đây là lớp đầu tiên của mạng, nhận dữ liệu đầu vào.

- Lớp ẩn (Hidden layers): Các lớp này nằm giữa lớp đầu vào và lớp đầu ra. Chúng thực hiện các tính toán và biến đổi trên dữ liệu để trích xuất các đặc trưng quan trọng.

- Lớp đầu ra (Output layer): Đây là lớp cuối cùng của mạng, tạo ra kết quả cuối cùng (ví dụ: phân loại hoặc dự đoán).

1.4 Graph Attention Networks

1.4.1 Scale dot prodcut attention

Scale dot product attention [6] khi mỗi nút có thể điều chỉnh trọng số của nó cho các nút trong đồ thị sao cho nút ở vị trí càng gần nó nhất thì trọng số càng lớn và càng xa thì càng nhỏ dần chính là một cơ chế self-attention. Ví dụ, xét một phép máy dịch trong câu “I study at school”. Sau khi đi qua embeding layer (lớp nhúng) ta có đầu vào của encoder và decoder là ma trận X kích thước m*n, với m, n lần lượt là chiều dài câu và số chiều của vector nhúng từ.

Ở hình trên, W_q, W_k, W_v chính là các hệ số cần huấn luyện, sau khi nhân ma trận này với ma trận đầu vào X, ta thu được ma trận Q, K, V (ma trận Query, Key và Value trong hình 1.9). Ma trận Query và Key có tác dụng tính toán ra phân phối Score cho các cặp từ, ma trận Value sẽ dựa trên phân phối Score để tính ra phân phối xác suất đầu ra. Để tính ra Score cho mỗi cặp từ (w_i, w_j), chúng ta sẽ tính toán dot-product giữa Query với Key.

1.4.2 Graph Attentional Layer

Xét đầu vào là các nút: h= {(h₁ ),   (h₂ ) ,…,(h_N ) } với (h_i ) ∈ RF, với F là số đặc trưng của mỗi nút và N là số nút. Đầu ra là tập hợp các đặc trưng của các nút: h'={(h₁' ),   (h₂' ),…,(h_N' ) } khi qua các layer với (hi' )  ∈ R(F' ).

e_ij = a(W(h_i ),W(h_j ))                    PT 1.12

Ta có thể tính hệ số được tính bởi cơ chế attention khi sử dụng hàm LeakyReLU phi tuyến với độ dốc âm là 0.2:

Nhiệm vụ quan trọng và được quan tâm  bậc nhất của bài toán đóng gói hộp vào thùng đó chính là làm sao để số hộp được đóng gói vào thùng là nhiều nhất cũng như tổng thể tích các hộp được đóng gói vào là tối đa. Sau khi đã giới thiệu về cơ sở lý thuyết được sử dụng trong nghiên cứu là Deep Reinforcement Learning, cũng như một số kiến thức cơ bản về mạng Multi-layer perceptron, ở trong bài báo cáo này, nhóm sẽ trình bày về các phương pháp đóng gói hộp sử dụng học tăng cường cũng như kết quả nghiên cứu và đánh giá tổng quan. Cụ thể, ở trong chương 2, phương pháp đóng gói hộp sẽ gồm phần quan trọng nhất cũng như cốt lõi bài báo là giới thiệu về cấu hình cây đóng gói động PCT sử dụng học sâu tăng cường và việc thiết lập các thông số liên quan đến học tăng cường. 

CHƯƠNG 2. PHƯƠNG PHÁP ĐÓNG GÓI SỬ DỤNG HỌC TĂNG CƯỜNG

2.1 Tổng quát các thông số

- Không gian hành động A: Là hành động a_t  biểu thị chỉ số nút lá l được chọn, không gian hành động A của bài toán này chỉ phụ thuộc vào biểu đồ mở rộng nút lá và các vật phẩm đã được hoàn tất đóng gói trong hộp.

- Không gian trạng thái S: Là mỗi trạng thái St ở bước thời gian t với Lt là tập hợp các nút lá gồm 2 đại lượng Tt và nt với Tt là bộ Bt là tập hợp các nút gốc và nt là vật đóng gói tiếp theo. Mỗi nút bên trong b ∈ B_t là một cấu hình không gian có tọa độ (p_b^x,p_b^y,p_b^z) và kích thước (s_b^x,s_b^y,s_b^z) tương ứng với vật phẩm đã được đóng gói. Vật phẩm hiện tại nt là một bộ kích thước (s_n^x,s_n^y,s_n^z) đã biết, nhưng vật phẩm sau nó thì có kích thước tùy ý. Các thuộc tính bổ sung sẽ tùy ý được thêm vào b và nt cho các lựa chọn đóng gói cụ thể trong từng trường hợp, ví dụ như trọng lượng, màu sắc …

- Điểm thưởng R:

r_t = {(c_r * w_t  ,nếu vật n_t  được đóng gói vào thùng. 0,nếu kết thúc quá trình đóng gói)         PT 2.1

Và w_t được ký hiệu là thể tích của n_t hay:

w_t = sⁿx^sn^y *s_n^z                           PT 2.3

2.2 Packing Configuration Tree - PCT (Cấu hình cây đóng gói)

2.2.1 Quy tắc cây đóng gói

Khi một vật phẩm nt được đưa vào đóng gói với vị trí (p_n^x,p_n^y,p_n^z) và kích thước (s_b^x,s_b^y,s_b^z), nó sẽ được đưa ra một loạt các trường hợp mà nó có thể đặt vào, được thể hiện như hình 2.1.

Xét không gian 2 chiều Oxz, tại đây, khi một vật đã được đóng gói, nó sẽ được hình thành dưới dạng của một nút gốc đã có vị trí không đổi trong thùng. Và tiếp theo đó, dựa vào vị trí của nút gốc, thùng sẽ chia ra thành 2 vùng trống tương ứng với vị trí ứng viên cho địa chỉ đặt hộp tiếp theo cũng sẽ được hình thành, đại diện cho 2 nút lá mới cũng như 2 cách đặt thùng tiếp theo.

Tương tự với những lần đóng gói sau đó, các vùng trống của thùng sẽ liên tục được thay đổi kèm theo đó là các vị trí ứng viên cho địa chỉ các nút tiếp theo.

2.2.2 Các phương pháp tạo nút lá

Khó khăn của bài toán 3D Bin packing là tìm vị trí ứng viên phù hợp nhất cho vật được đặt vào hộp vì nó ảnh hưởng rất nhiều tới hiệu năng cho các thuật toán, hay là việc tìm nút lá trong cây động PCT. Có rất nhiều phương pháp được các nhà nghiên cứu đề xuất với những ưu, nhược điểm khác nhau nhưng một số phương pháp được ứng dụng nhiều nhất là Corner point (CPs) [1], Extreme Point (Eps) [8], Empty Maximal Space (EMSs) [9] và Event point (Eps). Phương pháp Corner point dựa trên thuật toán “nhánh và cận” [1] (để giải quyết các bài toán tối ưu). Các CPs là các điểm có thể tìm thấy ở tận cùng các đường bao theo các trục dọc và ngang (hình 2.4), mỗi khi có vật mới được đặt vào, các CPs cũ không thỏa mãn điều kiện cho trước sẽ bị loại bỏ. 

Dưới đây là minh họa các phương pháp mở rộng nút lá được đề cập ở trên biểu diễn trên mặt phẳng Oxy:

2.3 Mô hình hóa thuật toán Deep Reinforcement Leaning

Dưới đây là cấu trúc được đề tài sử dụng để giải quyết bài toán:

CHƯƠNG 3. HỆ THỐNG ĐÓNG GÓI HỘP TỰ ĐỘNG

3.1 Tổng quan về hệ thống

Hệ thống được sử dụng trong nghiên cứu của nhóm bao gồm các hộp hình hộp chữ nhật được dán các mã datamatrix lên để có thể nhận biết được kích thước của từng hộp, một camera được kết nối với máy tính bằng cổng USB để đọc datamatrix và cánh tay robot Dobot Magician để gắp vật và đưa đến vị trí chỉ định.

Hệ thống thực tế của bài toán như hình 3.1.

Sơ đồ thuật toán của hệ thống được nhóm đưa ra như hình 3.2.

Trước tiên, hộp hình chữ nhật sẽ được đưa vào vị trí trước camera sao cho camera có thể chụp được datamatrix để có thể xác định được kích thước của hộp cần đóng gói. Sau khi đã có được kích thước của hộp cần đóng gói, model được huấn luyện dựa trên thuật toán Deep Reinforcement Learning sẽ xác định được vị trí cần đóng gói hộp, sau đó truyền tọa độ vị trí đóng gói hộp đến với cánh tay robot Dobot Magician để nó có thể thực hiện các thao tác gắp vật mà đặt hộp vào tọa độ vị trí đã có. Sau khi Dobot Magician hoàn thành việc đặt hộp, đèn tín hiệu trên màn hình giao diện sẽ chuyển tín hiệu sang màu xanh, khi đó các công việc trên sẽ tiếp tục lặp đi lặp lại cho tới khi không thể xác định được vị trí đóng gói nào thỏa mãn.

3.2 Giới thiệu về Dobot Magician

Dobot Magician là một cánh tay robot để bàn đa chức năng dành cho giáo dục đào tạo thực tế. Dobot magician có thể thực hiện các chức năng thú vị như in 3D, khắc laser, viết và vẽ. Nó hỗ trợ phát triển thứ cấp bởi 13 giao diện có thể mở rộng và hơn 20 ngôn ngữ lập trình. Khả năng ứng dụng của Dobot magician rất rộng và nó tích hợp khá toàn diện các chức năng của các Robot công nghiệp hiện nay như khả năng in 3D, viết, vẽ, hút các vật và di chuyển đến nơi được chỉ định. Đặc biệt là khả năng hướng dẫn chỉ bằng một tay, thao tác và lặp lại với độ lặp lại lên đến 0.02 mm.

Dobot Magician có thể kết nối với máy tính qua dây cáp USB, qua giao tiếp không dây Wifi và bluetooth, ngoài ra nó cũng có thể hoạt động offline một cách ấn tượng. Dưới đây là thông số của Dobot Magician.

Thông số của Dobot Magician như bảng 3.1.

Thông thường, việc điều khiển cánh tay robot Dobot Magician sẽ được dùng trên phần mềm DobotStudio.

3.3 Datamatrix

3.3.1 Datamatrix

Ngày nay, mã vạch xuất hiện trên mọi sản phẩm, từ bao bì đồ ăn trong siêu thị cho tới những kiện hàng tại các xướng sản xuất công nghiệp. Điều này là dễ hiểu bởi mã vạch là công cụ cực kì hữu dụng trong nhận diện hàng hóa một cách tự động. Việc quét mã vạch với máy quét sẽ nhanh hơn nhiều so với việc nhập thông tin sản phẩm thủ công cũng như tránh được những sai số về con người. Mã vạch có nhiều tiêu chuẩn, với nhiều thiết kế đa dạng. Trong công nghiệp, datamatix đang được sử dụng một cách rất rộng rãi. Dưới đây là ví dụ về một số datamatrix sử dụng trong đề tài:

3.3.2 Camera

Sau khi tạo các được các datamatrix giúp đọc kích thước các vật, nó sẽ được quét bởi một camera có trong hệ thống bài toán. Ảnh sau khi nhận được sẽ xác định vị trí của datamatrix, gọi là ảnh nhỏ. Ảnh nhỏ này được tiền xử lý trước khi giải mã để xác định kích thước của các hộp. Có hai kĩ thuật được sử dụng ở đây là làm mịn ảnh với Gaussian Blur và phân ngưỡng threshold

G(x)=1/√(2πб² ) e_x²)/(2б² ))                    PT 2.11

CHƯƠNG 4. KẾT QUẢ NGHIÊN CỨU VÀ ĐÁNH GIÁ

4.1 Giao diện mô phỏng bài toán đóng gói hộp

Sau khi đã có thuật toán huấn luyện, nhóm đã xây dựng giao diện cho bài toán bằng QT như hình dưới đây. Bên phải của giao diện là phần cài đặt môi trường và Model, tại đây có thể chọn các phương pháp mở rộng nút lá như EMSs, Evs và EPs cũng như thay đổi cài đặt về chiều xoay của các hộp được đóng gói. Với Setting 1, các hộp được đóng gói chỉ được xoay theo 2 chiều quanh trục z; còn với Setting 2, các hộp được đóng gói có thể xoay được theo 6 chiều tương ứng với 2 chiều quanh mỗi trục x, y, z. Với phần “Add new box”, các hộp được đưa vào đóng gói có thể được đưa vào ngẫu nhiên với “Ramdom Box” hoặc ta cũng có thể chọn kích thước theo ý muốn với “Custom Box”.

 Dưới đây là kết quả sau lần chạy của 2 Setting với các hộp được đưa vào đều có kích thước giống nhau, ở đây thì cả 2 Setting đều được chạy với phương pháp mở rộng nút lá EMS và Model RL.

Quá trình thực hiện việc đóng gói hộp như hình 4.2.

4.2 Kết quả mô phỏng bài toán đóng gói hộp

4.2.1Kết quả mô phỏng với Setting 1

Như đã nêu trên, đối với phần Setting 1, các hộp được đóng gói sẽ chỉ có thể xoay theo hai hướng dọc theo trục z. Ví dụ về kết quả đóng gói hộp đối với từng phương pháp mở rộng nút lá như Eps, Evs và EMSs trong Setting 1 sẽ được trình bày như hình dưới đây.

Kết quả mô phỏng Setting 1 với phương pháp Eps như hình 4.3.

Kết quả mô phỏng Setting 1 với phương pháp EMSs như hình 4.5.

4.2.2. Kết quả mô phỏng với Setting 2

Đối với Setting 2, các hộp được đóng gói sẽ có thể xoay được theo 6 hướng tương ứng với 2 chiều dọc theo mỗi trục x, y, z. Kết quả đóng gói hộp đói với từng phương pháp mở rộng nút lá như Eps, Evs và EMSs trong Setting 2 sẽ được trình bày như hình dưới đây.

4.2.3. So sánh kết quả mô phỏng các Setting

Trước hết, nhóm sẽ thực hiện việc đưa các hộp có kích thước giống hệt nhau để xem kết quả của các Setting. Kết quả được thể hiện như hình dưới đây. 

Có thể thấy với các hộp giống nhau thì tỉ lệ lấp đầy của Setting 1 là tốt hơn so với Setting 2. Tuy vậy, với việc có thể xoay theo nhiều hướng hơn, qua các lần huấn luyện thì có thể thấy Setting 2 hầu như đều cho kết quả tốt hơn Setting 1. Dưới đây là kết quả sau lần chạy của cả 2 Setting với các hộp đưa vào đóng gói có kích thước ngẫu nhiên.

Có thể thấy, so với Setting 1 thì các phương pháp mở rộng nút lá dùng Setting 2 sẽ cho kết quả tốt hơn trong quá trình huấn luyện. Và phương pháp mở rộng nút lá Empty Maximal Space (EMSs) đạt kết quả tốt hơn nhiều so với các phương pháp khác được sử dụng như là Eps hay Evs. Trong Setting 2, phương pháp mở rộng nút lá EMSs sau khi đã huấn luyện 5000 episodes đạt tỉ lệ lấp đầy thùng khoảng 80%.

4.3 Thực nghiệm trên sản phẩm thực tế

Đối với thực nghiệm trên cánh tay Dobot magician, nhóm sẽ tạo ra các hộp là các hộp hình hộp chữ nhật với các loại kích thước 4*3*2, 3.5*2.5*2, 3*3*2.5, 3*2*2, 2*2*2 (cm), để tránh việc va chạm của cánh tay robot với thùng nên việc thực nghiệm của nhóm sẽ không sử dụng thùng, thay vào thùng được xác định bằng việc kẻ cố định trên bàn. Dưới đây là kết quả của việc đóng gói hộp trong thực tế với cánh tay robot Dobot magician và kết quả mô phỏng.

Kết quả thực nghiệm ở hình bên trái có được sau khi đưa các hộp đã có trước nêu trên vào lần lượt một cách ngẫu nhiên. Để kiểm tra lại kết quả, nhóm thực hiện kiểm tra bằng mô phỏng với việc đưa lần lượt các hộp có kích thước tương tự như thực nghiệm (bằng cách sử dụng Custom Box). Hình bên trên cho thấy kết quả mô phỏng hoàn toàn khớp đối với kết quả thực nghiệm, mặc dù các hộp ở thực nghiệm cũng có sai lệch nhỏ (do sai số của cánh tay robot) nhưng nó cũng đã cho thấy được sự chính xác của thuật toán.

CHƯƠNG 5. KẾT LUẬN

5.1 Kết luận

Kết quả nghiên cứu bước đầu đã thành công áp dụng học tăng cường trong bài toán đóng gói hộp vào thùng. Sau khi áp dụng phương pháp này, thuật toán đã có thể thực hiện được việc lấp đầy khá tốt, mặc dù tỉ lệ lấp đầy này còn chưa thể gần với mức tuyệt đối. Nguyên nhân đến từ việc tăng số lượng các nút lá trong cây động PCT dẫn đến việc tăng không gian trạng thái - hành động dẫn đến việc đòi hỏi phải tính toán nhiều hơn và khó khăn hơn trong việc tìm được giá trị tối ưu tương ứng với chính sách tối ưu.

Nhận thấy những khó khăn kể trên, nhóm đã đề ra phương án để giải quyết vấn đề trên. Cụ thể, nhóm sẽ sử dụng camera để quét ra thông tin của một số vật trước khi đóng gói , qua đó có thể chọn ra được hộp cho kết quả tốt hơn so với việc chỉ quét được duy nhất thông tin một hộp. Trong việc huấn luyện thì phương pháp này cho ra tỷ lệ lấp đầy thùng tốt hơn và nó cũng có tốc độ nhanh hơn so với các phương pháp đã trình bày. Tuy vậy phương pháp vừa nêu ra cũng còn một số nhược điểm chưa khắc phục được trong thực tế như nó sẽ khiến cho cánh tay robot thực hiện việc gặp và di chuyển vật vào trị trí chỉ định cần có không gian làm việc rộng hơn đáng kể, cũng như sẽ tốn thêm chi phí để tạo ra các vị trí đặt camera mới sao cho nó có thể quét được thông tin của nhiều hộp so với trước đó chỉ cần một camera để quét thông tin của một hộp duy nhất. Và việc tăng tỷ lệ lấp đầy nhờ phương pháp này cũng sẽ làm giảm tốc độ quá trình đóng gói do băng chuyền sẽ phải tạm dừng trong khoảng thời gian lâu hơn để cánh tay robot thực hiện thao tác. Một hướng nghiên cứu cũng rất hứa hẹn sẽ đưa ra được kết quả tốt hơn đó là việc kết hợp Multi-Bin, thay vì đóng gói trong một thùng duy nhất, số lượng thùng có thể tăng lên là 2 hoặc 3 để có thể có nhiều lựa chọn đóng gói hộp hiệu quả hơn.

Trong tương lai nhóm sẽ nghiên cứu và cải thiện thêm thuật toán để đạt được kết quả như mong muốn. Xa hơn là có thể chuyển kết quả nghiên cứu sang ứng dụng thực tế.

5.2 Hướng phát triển của đồ án trong tương lai

Cần có chương trình nghiên cứu rộng hơn và áp dụng cụ thể vào mô hình sau đó đưa vào thị trường tại các xí nghiệp vận chuyển, đóng gói.

TÀI LIỆU THAM KHẢO

[1]. Silvano Martello, David Pisinger, and Daniele Vigo, The three-dimensional bin packing problem, 2000.

[2]. S. Seiden, On the online bin packing problem, 2002.

[3]. Hang Zhao, Qijin She, Chenyang Zhu, Yin Yang, and Kai Xu, Online 3D bin packing with constrained deep reinforcement learning, In Thirty-Fifth AAAI Conference on Artificial Intelligence, 2021.

[4]. Andrew Barto, Richard S.Sutton, Reinforcement Learning: An Introduction, 2019.

[5]. Nikolaus Kriegeskorte, Tal Golan, Neural Netwwork models and deep learning, 2019.

[6]. Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Attention is all you need, 2017.

[7]. Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua , Graph attention networks, In 6th International Conference on Learning Representations, 2018.

[8]. Teodor Gabriel Crainic, Guido Perboli, and Roberto Tadei, Extreme point-based heuristics for three dimensional bin packing, 2nd International Conference on Learning Representations, 2008.

"TẢI VỀ ĐỂ XEM ĐẦY ĐỦ ĐỒ ÁN"