第 二 章 相 關 研 究 2.1 運 動 計 畫 演 算 法 運 動 計 畫 演 算 法 是 要 替 環 境 中 的 物 體, 找 出 一 條 從 指 定 的 起 始 狀 態 到 目 標 狀 態 的 運 動 過 程 這 項 研 究 一 開 始 是 起 源 於 機 器 人 學 (Robotics), 主 要 的 目 的 是 要 讓 機 器 人 可 以 不 受 到 環 境 中 障 礙 物 的 阻 擾, 順 利 的 抵 達 目 的 地 位 置 之 後 經 過 不 斷 的 研 究 發 展, 這 些 技 術 也 被 廣 泛 的 應 用 到 許 多 不 同 領 域 的 問 題 上, 包 括 產 生 3D 虛 擬 實 境 中 的 角 色 動 作 動 畫 [19][26] 模 擬 現 實 中 的 人 群 [11][15] 以 及 輔 助 遊 戲 中 的 操 作 介 面 [4][25] 等 但 不 管 應 用 領 域 有 多 少 差 別, 其 本 上 我 們 都 還 是 可 以 把 運 動 計 畫 的 問 題 分 成 兩 部 份 來 討 論, 分 別 是 碰 撞 偵 測 (Collision Detection) 和 路 徑 搜 尋 (Path Finding) 碰 撞 偵 測 的 目 的 是 要 檢 查 出 被 規 劃 物 體 的 狀 態 是 否 合 法 例 如 在 [19] 的 研 究 裡, 他 們 希 望 規 劃 出 來 的 動 作 不 會 有 碰 撞 發 生, 所 以 當 角 色 在 某 個 狀 態 下 的 動 作 會 和 場 景 發 生 碰 撞 時, 角 色 的 這 個 狀 態 便 是 不 合 法 的 組 態 空 間 (configuration space) 是 過 去 一 種 常 見 的 碰 撞 偵 測 解 決 方 法, 這 種 方 法 會 事 先 把 物 體 的 所 有 可 能 狀 態 計 算 出 來, 並 將 它 們 是 否 合 法 的 結 果 存 在 一 張 組 態 空 間 表 裡 之 後 當 程 式 執 行 時, 它 便 可 以 直 接 用 查 表 的 方 式 來 進 行 碰 撞 偵 測 這 種 方 式 雖 然 有 著 執 行 速 度 快 的 優 點, 但 因 為 必 須 事 先 列 舉 出 物 體 的 所 有 可 能 狀 態, 並 用 記 憶 體 空 間 來 儲 存 這 些 組 態, 所 以 通 常 都 只 會 應 用 在 自 由 度 低 且 場 景 範 圍 小 的 運 動 計 畫 裡 街 景 圖 (Roadmap)[27] 是 另 一 種 常 見 的 碰 撞 偵 測 解 決 方 法, 這 種 方 法 和 組 態 空 間 的 方 法 類 似, 差 別 則 是 在 於 它 並 沒 有 計 算 出 整 個 組 態 空 間, 而 是 只 取 樣 5
(sample) 出 其 中 比 較 有 可 能 被 使 用 到 的 部 份 之 後 當 程 式 執 行 時, 程 式 便 會 盡 量 利 用 這 些 已 經 被 取 樣 到 的 狀 態 來 進 行 運 動 計 畫, 並 動 態 的 將 沒 被 取 樣 到 的 狀 態 更 新 到 街 景 圖 裡 這 種 方 式 因 為 不 須 要 列 舉 出 物 體 的 所 有 可 能 狀 態, 所 以 可 以 減 少 許 多 事 前 的 準 備 時 間 和 必 須 被 使 用 到 的 記 憶 體 空 間 但 因 為 在 執 行 時 必 須 花 費 時 間 去 更 新 它 的 組 態 空 間 表, 所 以 執 行 速 度 相 對 的 會 比 較 慢 路 徑 搜 尋 的 目 的 是 要 從 物 體 的 所 有 可 能 運 動 組 合 裡, 找 出 一 條 能 符 合 目 標 要 求 的 運 動 路 徑 常 見 搜 尋 的 方 式 有 規 則 導 向 (rule-based) 目 標 導 向 (goal-based) 和 學 習 演 算 法 (learning algorithm) 三 種 類 型 規 則 導 向 的 搜 尋 方 式, 是 根 據 程 式 設 計 者 預 先 設 定 好 的 搜 尋 順 序 來 進 行 搜 尋 這 種 方 法 有 著 容 易 實 作 的 優 點, 但 因 為 搜 尋 順 序 無 法 隨 著 環 境 而 改 變, 因 此 有 著 缺 乏 彈 性 的 缺 點 目 標 導 向 的 搜 尋 方 式, 是 由 程 式 設 計 者 根 據 所 希 望 的 目 標 狀 態 來 定 義 出 一 個 比 較 狀 態 的 演 算 法, 藉 由 這 個 演 算 法 來 計 算 出 搜 尋 目 標 的 優 先 程 度, 藉 此 來 動 態 決 定 搜 尋 的 順 序 這 種 方 法 因 為 能 根 據 不 同 的 環 境 狀 態 來 改 變 它 的 搜 尋 順 序, 所 以 有 著 較 高 的 彈 性 及 搜 尋 效 率, 缺 點 則 是 必 須 花 費 比 較 多 的 時 間 去 設 計 它 的 演 算 法 學 習 演 算 法 的 搜 尋 方 式 和 目 標 導 向 的 搜 尋 方 式 大 部 份 都 相 同, 不 同 的 部 份 是 它 還 會 把 程 式 執 行 的 結 果 當 成 一 種 經 驗 儲 存 起 來, 並 把 這 些 經 驗 納 入 演 算 法 的 考 慮 範 圍 裡 這 種 方 法 的 優 點 是 能 夠 藉 由 累 積 經 驗 的 方 式 來 增 加 智 慧, 藉 此 補 足 演 算 法 設 計 上 的 不 足 缺 點 是 當 環 境 的 狀 態 不 停 改 變 且 改 變 的 幅 度 都 很 大 時, 所 累 積 的 經 驗 可 能 會 毫 無 用 處, 甚 至 導 致 更 差 的 結 果 2.2 角 色 動 畫 的 生 成 在 3D 即 時 虛 擬 環 境 裡, 角 色 動 畫 的 生 成 方 式 基 本 上 可 以 分 成 以 動 力 學 模 型 為 基 礎 (dynamics model based) 和 以 圖 形 為 基 礎 (graph-based) 兩 種 類 型 以 動 力 學 模 型 為 基 礎 的 生 成 方 式, 是 以 動 力 學 為 依 據, 讓 程 式 透 過 即 時 計 算 的 方 式 來 產 生 角 色 的 動 畫 例 如 根 據 關 節 (joint) 之 間 的 角 度 關 節 所 支 撐 的 重 量 和 整 體 的 平 衡 感, 來 計 算 出 角 6
圖 2.1: 動 作 圖 的 範 例 [29] 色 走 路 [1][9][10] 跑 步 [12] 或 騎 車 [13] 的 動 作 這 種 方 法 的 優 點 是 能 產 生 出 許 多 複 雜 且 有 彈 性 的 動 作, 缺 點 則 是 須 要 比 較 大 的 計 算 量, 且 因 為 設 計 者 通 常 很 難 把 動 力 學 模 型 設 計 的 很 完 善, 所 以 計 算 出 來 的 結 果 往 往 會 有 著 不 真 實 或 不 自 然 的 缺 點 以 圖 形 為 基 礎 的 生 成 方 式, 是 由 程 式 設 計 者 事 先 定 義 好 一 些 動 作 片 段, 並 將 它 們 之 間 的 連 接 關 係 儲 存 成 一 個 動 作 圖 (Motion graph)[17] 之 後 當 程 式 執 行 時, 便 直 接 根 據 這 個 動 作 圖 來 決 定 所 要 產 生 動 作 的 順 序, 並 用 動 作 混 合 (motion blending) 的 方 式 來 組 成 連 續 的 動 畫 圖 2.1 是 一 個 簡 單 的 例 子, 圖 中 的 節 點 代 表 著 動 作 片 段, 程 式 可 以 用 動 作 混 合 的 方 式 來 將 兩 個 節 點 的 動 作 片 段 混 合 成 站 起 來 (STAND UP) 坐 下 (SIT DOWN) 或 其 它 不 同 種 類 的 連 續 動 作 這 種 以 圖 形 為 基 礎 的 動 畫 生 成 方 式 便 是 本 研 究 裡 所 使 用 的 方 法, 有 著 計 算 量 小 可 重 覆 利 用 和 易 於 更 新 等 優 點, 但 也 有 動 作 單 調 和 缺 乏 靈 活 性 的 問 題 動 作 單 調 和 缺 乏 靈 活 性 的 原 因, 主 要 是 因 為 動 作 圖 的 大 小 是 有 限 的 一 個 出 拳 的 動 作 在 動 作 圖 裡 可 能 只 能 找 到 兩 三 種 不 同 的 選 擇, 程 式 不 一 定 能 從 這 些 選 擇 裡 找 出 符 合 使 用 者 要 求 的 動 作, 且 當 出 拳 的 次 數 頻 繁 發 生 時, 很 容 易 就 會 被 使 用 者 發 現 是 幾 種 相 同 的 動 作 在 被 重 覆 使 用 因 此 有 研 究 提 出 以 動 態 調 整 動 作 混 合 參 數 的 方 法 將 兩 種 動 作 進 行 混 7
圖 2.2: 雙 層 架 構 的 動 作 圖 [30] 合, 藉 此 產 生 出 許 多 不 同 的 動 作 風 格 [7] 例 如 把 走 路 和 彎 腰 前 進 的 動 作 進 行 混 合, 可 以 產 生 托 著 腳 走 路 的 動 作, 而 根 據 混 合 參 數 的 不 同, 又 會 使 托 著 腳 的 動 作 有 程 度 上 的 差 別, 藉 此 增 加 動 作 圖 所 能 產 生 的 不 同 連 續 動 作 另 一 種 方 法 則 是 將 動 作 片 段 切 細, 藉 此 讓 動 作 圖 的 節 點 及 邊 變 多, 使 其 達 到 動 作 增 加 的 目 的 但 這 種 方 法 也 會 增 加 程 式 每 次 搜 尋 動 作 圖 所 須 花 費 的 時 間, 因 此 有 許 多 研 究 便 是 在 想 辦 法 減 少 程 式 搜 尋 動 作 圖 的 時 間 在 [18] 的 研 究 裡, 他 們 在 動 作 圖 裡 增 加 了 一 種 名 為 中 心 節 點 (hub nodes) 的 新 類 型 節 點, 這 種 節 點 是 動 作 圖 裡 比 較 重 要 的 節 點, 會 比 一 般 的 節 點 有 著 更 多 的 邊 這 種 只 在 部 份 節 點 增 加 邊 的 方 式, 可 以 有 效 的 增 加 動 作 圖 的 邊 數, 又 不 會 使 程 式 搜 尋 動 作 圖 的 時 間 增 加 太 多 另 外 在 [30] 的 研 究 裡, 他 們 提 出 了 一 種 雙 層 架 構 (two layer structure) 的 動 作 圖 概 念 ( 圖 2.2), 這 種 架 構 會 將 動 作 圖 分 成 高 層 (higher layer) 和 低 層 (lower layer) 兩 種 類 型 高 層 的 動 作 圖 是 以 動 作 片 段 的 類 型 去 組 織 動 作 圖, 會 有 著 比 較 少 的 節 點 及 邊 數 低 層 的 動 作 圖 則 是 相 當 於 普 通 的 動 作 圖, 會 有 著 比 較 多 的 節 點 及 邊 數 當 程 式 在 搜 尋 動 作 圖 時, 會 先 去 搜 尋 高 層 的 動 作 圖, 再 去 搜 尋 低 層 的 動 作 圖, 藉 此 減 少 程 式 搜 尋 動 作 圖 的 時 間 例 如 角 色 目 前 是 一 種 走 路 類 型 的 動 作, 當 程 式 要 搜 尋 角 色 的 下 個 動 作 時, 它 會 先 去 高 層 的 8
動 作 圖 搜 尋 走 路 類 型 的 動 作 可 以 轉 換 到 那 一 種 類 型 的 動 作, 之 後 再 到 低 層 的 動 作 圖 裡 去 找 有 那 些 動 作 片 段 符 合 這 種 類 型, 並 挑 選 出 最 適 合 的 下 一 個 動 作 但 這 兩 種 方 法 所 能 產 生 的 變 化 性 也 還 是 有 限, 有 些 動 作 可 能 再 怎 麼 組 合 也 無 法 達 成 想 要 的 結 果 例 如 當 動 作 圖 裡 的 動 作 都 是 站 著 的 姿 勢 時, 電 腦 再 怎 麼 調 參 數 也 都 無 法 產 生 坐 下 的 動 作 所 以 有 另 一 種 研 究 方 向, 是 偏 重 在 直 接 修 改 這 些 動 作 資 料 的 部 份 內 容 藉 由 只 調 整 少 數 動 作 參 數 的 方 式, 讓 修 改 後 的 動 作 除 了 能 達 到 目 標 外, 又 能 保 持 原 本 動 作 的 真 實 性 例 如 讓 演 算 法 計 算 出 手 腳 和 骨 盆 的 空 間 限 制 (spatial constraints), 並 用 反 向 運 動 (Inverse Kinematics) 的 方 程 式 來 改 變 動 作 資 料 裡 相 關 關 節 的 位 置 資 訊, 產 生 搬 箱 子 丟 球 和 走 樓 梯 的 動 作 [2][3][5] 這 種 方 法 相 當 於 以 動 力 學 模 型 為 基 礎 和 以 範 例 為 基 礎 兩 種 方 式 的 綜 合 如 果 可 調 整 的 動 作 參 數 越 多, 動 作 可 能 就 越 不 真 實 相 反 的 如 果 可 調 整 的 動 作 參 數 越 少, 動 作 的 可 變 化 性 就 越 少 2.3 反 應 機 制 的 設 計 角 色 反 應 機 制 的 設 計 相 當 於 在 設 計 角 色 的 智 慧 有 限 狀 態 機 (Finite-State Machine) 是 目 前 最 常 用 來 設 計 角 色 反 應 機 制 的 方 法, 這 種 方 法 是 把 角 色 的 狀 態 和 狀 態 轉 移 條 件 都 記 錄 在 一 個 表 格 裡, 之 後 當 角 色 要 和 使 用 者 進 行 互 動 時, 便 直 接 根 據 使 用 者 的 動 作 類 型 來 觸 發 角 色 的 狀 態 轉 移 這 種 方 法 有 速 度 快 及 容 易 實 作 的 優 點, 但 因 為 他 的 轉 移 條 件 只 會 改 變 自 己 的 狀 態, 所 以 互 動 性 比 較 差 狀 態 - 行 為 模 型 (State-Action Model)[14] 是 另 一 種 用 來 設 計 反 應 機 制 的 方 法, 這 種 方 法 除 了 角 色 的 狀 態 和 狀 態 轉 移 條 件 外, 還 記 錄 了 狀 態 轉 移 條 件 所 會 連 帶 影 響 到 的 其 它 角 色 例 如 角 色 A 目 前 的 狀 態 是 站 著, 這 個 狀 態 有 一 個 轉 移 條 件 是 看 到 石 頭, 這 個 條 件 會 連 帶 的 影 響 到 角 色 B 那 麼 當 角 色 A 站 著 且 看 到 石 頭 時, 不 管 角 色 B 有 沒 有 看 到 石 頭, 角 色 B 都 要 進 行 狀 態 的 轉 移 這 種 方 法 有 著 互 動 性 佳 的 優 點, 但 缺 點 是 增 加 了 設 計 上 的 困 難 9