This　paper　proposes　a　path　planning　algorithm　for　determining　an　optimal　path　with　respect　to　the　costs　of　a　dual　graph　on　the　Constrained　Delaunay　Triangulation　(CDT)　of　an　environment.　The　advantages　of　using　triangles　for　environment　expression　are:　less　data　storage　required,　available　mature　triangulation　methods　and　consistent　with　a　potential　motion　planning　framework.　First　we　represent　the　polygon　environment　as　a　planar　straight　line　graph　(PSLG)　described　as　a　collection　of　vertices　and　segments,　and　then　we　adopt　the　CDT　to　partition　the　environment　into　triangles.　Then　on　this　CDT　of　the　environment,　a　dual　graph　is　constructed　following　the　target　attractive　principle　in　order　to　avoid　the　nonoptimal　paths　caused　by　the　different　geometric　size　of　the　triangles.　Correspondingly,　a　path　planning　algorithm　via　A*　search　algorithm　finds　an　optimal　path　on　the　real-time　building　dual　graph.　In　addition,　completeness　and　optimization　analysis　of　the　algorithm　is　given.　The　simulation　results　demonstrate　the　effectiveness　and　optimization　of　the　algorithm.